目录
1. 三数之和 🌟🌟
2. 编辑距离 🌟🌟🌟
3. 翻转字符串里的单词 🌟🌟
1. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
提示：
0 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
出处：
https://edu.csdn.net/practice/26654052
代码：
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return []
result = []
unique = {}
inv = {}
left = None
right = None
nums.sort()
i = 0
while i < len(nums):
if left == None and nums[i] >= 0:
left = i
if right == None and nums[i] > 0:
right = i
inv[nums[i]] = i
i += 1
if left == 0:
right = len(nums)
if right is None:
return []
i = 0
while i < right:
j = i+1
while j < len(nums) and (-nums[i] >= nums[j] * 2):
last = 0-nums[i]-nums[j]
k = inv.get(last)
if k and k > j:
list = [nums[i], nums[j], last]
hash = f'{list[0]}_{list[1]}_{list[2]}'
if unique.get(hash) is None:
unique[hash] = True
result.append(list)
j += 1
i += 1
return result
# %%
s = Solution()
print(s.threeSum(nums = [-1,0,1,2,-1,-4]))输出：
[[-1, -1, 2], [-1, 0, 1]]
2. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
以下程序实现了这一功能，请你填补空白处内容：
```python
class Solution(object):
def minDistance(self, word1, word2):
ls_1, ls_2 = len(word1), len(word2)
dp = list(range(ls_1 + 1))
for j in range(1, ls_2 + 1):
pre = dp[0]
dp[0] = j
for i in range(1, ls_1 + 1):
temp = dp[i]
if word1[i - 1] == word2[j - 1]:
dp[i] = pre
else:
____________________________;
pre = temp
return dp[ls_1]
if __name__ == '__main__':
s = Solution()
print (s.minDistance("horse","ros"))
print (s.minDistance("intention","execution"))
```
出处：
https://edu.csdn.net/practice/26654053
代码：
class Solution(object):
def minDistance(self, word1, word2):
ls_1, ls_2 = len(word1), len(word2)
dp = list(range(ls_1 + 1))
for j in range(1, ls_2 + 1):
pre = dp[0]
dp[0] = j
for i in range(1, ls_1 + 1):
temp = dp[i]
if word1[i - 1] == word2[j - 1]:
dp[i] = pre
else:
dp[i] = min(pre + 1, dp[i] + 1, dp[i - 1] + 1)
pre = temp
return dp[ls_1]
if __name__ == '__main__':
s = Solution()
print (s.minDistance("horse","ros"))
print (s.minDistance("intention","execution")) 输出：
3
5
3. 翻转字符串里的单词
给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：
- 输入字符串
s可以在前面、后面或者单词间包含多余的空格。 - 翻转后单词间应当仅用一个空格分隔。
- 翻转后的字符串中不应包含额外的空格。
示例 1：
输入：s = "the sky is blue" 输出："blue is sky the"
示例 2：
输入：s = " hello world " 输出："world hello" 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
示例 3：
输入：s = "a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
示例 4：
输入：s = " Bob Loves Alice " 输出："Alice Loves Bob"
示例 5：
输入：s = "Alice does not even like bob" 输出："bob like even not does Alice"
提示：
1 <= s.length <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词
进阶：
- 请尝试使用
O(1)额外空间复杂度的原地解法。
出处：
https://edu.csdn.net/practice/26654054
代码：
class Solution:
def reverseWords(self, s: str) -> str:
str_list = s.split()
s1 = ""
for n, i in enumerate(str_list[::-1]):
if n == len(str_list) - 1:
s1 = s1 + i
else:
s1 = s1 + i + " "
return s1
if __name__ == '__main__':
s = Solution()
print(s.reverseWords("the sky is blue"))
print(s.reverseWords(" hello world "))
print(s.reverseWords("a good example"))
print(s.reverseWords(" Bob Loves Alice "))
print(s.reverseWords("Alice does not even like bob"))输出：
blue is sky the
world hello
example good a
Alice Loves Bob
bob like even not does Alice
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/