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 <= 500
word1 和 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 <= 104
s 包含英文大小写字母、数字和空格 ' '
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
