classSolution: deftwoSum(self, nums: List[int], target: int) -> List[int]: hashtable = {} for index, num inenumerate(nums): if (target-num) in hashtable: return [index, hashtable[target-num]] hashtable[num] = index
字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
1 2 3 4 5 6 7 8 9 10
classSolution: defgroupAnagrams(self, strs: List[str]) -> List[List[str]]: ans = {} for s in strs: key = ''.join(sorted(s)) if key notin ans: ans[key] = [s] else: ans[key].append(s) returnlist(ans.values())
class Solution: def longestConsecutive(self, nums: List[int]) -> int: ans = 0 st = set(nums) for x in st: if x-1 in st: continue y = x+1 while y in st: y = y + 1 ans = max(ans,y -x) return ans
双指针
移动0
1 2 3 4 5 6 7 8 9 10 11
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ left = right = 0 while right < len(nums): if nums[right]!=0: nums[left],nums[right]=nums[right],nums[left] left += 1 right += 1
盛水最多容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。
1 2 3 4 5 6 7 8 9 10 11 12 13
class Solution: def maxArea(self, height: List[int]) -> int: left = ans = 0 right = len(height) - 1 while left < right : if height[left] < height[right]: ans = max(ans,height[left]*(right-left)) left += 1 else: ans = max(ans,height[right]*(right-left)) right -= 1 return ans
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
classSolution: defthreeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() ans = [] n = len(nums) for i inrange(n - 2): x = nums[i] if i > 0and x == nums[i - 1]: # 跳过重复数字 continue if x + nums[i + 1] + nums[i + 2] > 0: # 优化一 break if x + nums[-2] + nums[-1] < 0: # 优化二 continue j = i + 1 k = n - 1 while j < k: s = x + nums[j] + nums[k] if s > 0: k -= 1 elif s < 0: j += 1 else: # 三数之和为 0 ans.append([x, nums[j], nums[k]]) j += 1 while j < k and nums[j] == nums[j - 1]: # 跳过重复数字 j += 1 k -= 1 while k > j and nums[k] == nums[k + 1]: # 跳过重复数字 k -= 1 return ans
left, right = 0, len(height) - 1# 两个指针 left_max, right_max = height[left], height[right] # 左右最大边界 ans = 0# 结果累加器
while left < right: if height[left] < height[right]: left += 1 if height[left] > left_max: left_max = height[left] else: ans += left_max - height[left] else: right -= 1 if height[right] > right_max: right_max = height[right] else: ans += right_max - height[right]
return ans
滑动窗口
无重复字符的最长字串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution: deflengthOfLongestSubstring(self, s: str) -> int: d = {} res = 0 start = -1 for index, c inenumerate(s): if c notin d: res = max(res, index-start) else: if d[c] > start: start = d[c] else: res = max(res, index-start) d[c] = index return res
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
classSolution: defmaxSlidingWindow(self, nums: List[int], k: int) -> List[int]: # 如果数组为空或窗口大小为0，直接返回空列表 ifnot nums or k == 0: return []
# 使用双端队列来存储当前窗口中的元素索引 deque = collections.deque()
# 未形成窗口时的处理 for i inrange(k): # 如果队列不为空且队列末尾的元素小于当前元素，则弹出队列末尾的元素 # 这样可以保证队列中的元素是递减的 while deque and deque[-1] < nums[i]: deque.pop() # 将当前元素加入队列 deque.append(nums[i])
# 将当前窗口的最大值（即队列的第一个元素）加入结果列表 res = [deque[0]]
# 形成窗口后的处理 for i inrange(k, len(nums)): # 如果队列的第一个元素是窗口最左边的元素，则将其从队列中移除 # 因为这个元素即将离开窗口 if deque[0] == nums[i - k]: deque.popleft()
# 如果队列不为空且队列末尾的元素小于当前元素，则弹出队列末尾的元素 # 这样可以保证队列中的元素是递减的 while deque and deque[-1] < nums[i]: deque.pop()
# 将当前元素加入队列 deque.append(nums[i])
# 将当前窗口的最大值（即队列的第一个元素）加入结果列表 res.append(deque[0])
# 返回结果列表 return res
最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
class Solution: def minWindow(self, s: str, t: str) -> str: ans_left, ans_right = -1, len(s) cnt = defaultdict(int) # 比 Counter 更快 for c in t: cnt[c] += 1 less = len(cnt)
left = 0 for right, c in enumerate(s): cnt[c] -= 1 if cnt[c] == 0: less -= 1 while less == 0: if right - left < ans_right - ans_left: ans_left, ans_right = left, right x = s[left] if cnt[x] == 0: less += 1 cnt[x] += 1 left += 1
class Solution: def maxSubArray(self, nums: List[int]) -> int: count = 0 result = -99999 for i in nums: count += i if count > result: result = count if count < 0: count = 0 return result
merged = [] for interval in intervals: # 如果列表为空，或者当前区间与上一区间不重合，直接添加 if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: # 否则的话，我们就可以与上一区间进行合并 merged[-1][1] = max(merged[-1][1], interval[1])
return merged
轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
class Solution: def rotate(self, nums: List[int], k: int) -> None: def reverse(i: int, j: int) -> None: while i < j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1
n = len(nums) k %= n # 轮转 k 次等于轮转 k % n 次 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: # 如果有0，可以简化运算 total = math.prod(nums) ans = [] for i, num in enumerate(nums): if num != 0: ans.append(total // num) else: ans.append(math.prod(nums[:i] + nums[i+1:])) return ans
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
1 2 3 4 5 6 7 8 9 10 11 12 13
class Solution: def firstMissingPositive(self, nums: List[int]) -> int: N = len(nums) num_list = [0]*(N+1) for num in nums: if num>N or num<=0: continue num_list[num] = 1 for i in range(1,N+1): if num_list[i] == 0: return i return N+1
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ m, n = len(matrix), len(matrix[0]) row = [False] * m col = [False] * n
for i in range(m): for j in range(n): if matrix[i][j] == 0: row[i], col[j] = True, True
for i in range(m): for j in range(n): if row[i] or col[j]: matrix[i][j] = 0
螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: result = [] while matrix : result.extend(matrix.pop(0)) if matrix : if matrix[0]: for i in range(len(matrix)): result.append(matrix[i].pop()) if matrix : k = matrix.pop() result.extend(k[::-1]) if matrix : if matrix[0]: for i in range(len(matrix)-1,-1,-1): result.append(matrix[i].pop(0)) return result
class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: A, B = headA, headB while A != B: A = A.next if A else headB B = B.next if B else headA return A
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: cur ,pre = head, None while cur: temp = cur.next cur.next = pre pre = cur cur = temp return pre
class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
# 遍历整个网格 for i in range(len(grid)): for j in range(len(grid[0])): # 如果当前单元格是陆地（'1'），则开始 DFS 遍历 if grid[i][j] == '1': self.landpaint(grid, i, j) # 标记当前岛屿的所有陆地 n_l += 1 # 岛屿数量加 1
class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: m,n=len(grid),len(grid[0]) fresh=0 q=[] for i,row in enumerate(grid): for j,x in enumerate(row): if x==1: fresh+=1 elif x==2: q.append((i,j))
ans=0 while q and fresh: ans+=1 tmp=q q=[] for x,y in tmp: for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1): # 四方向 if 0 <= i < m and 0 <= j < n and grid[i][j] == 1: # 新鲜橘子 fresh -= 1 grid[i][j] = 2 # 变成腐烂橘子 q.append((i, j)) return -1 if fresh else ans
class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: # 获取矩阵的行数和列数 m, n = len(matrix), len(matrix[0]) # 初始化二分查找的左右边界 l, r = 0, m * n # 将二维矩阵视为一维数组 # 开始二分查找 while l < r: # 计算中间位置 mid = (l + r) >> 1 # 等价于 (l + r) // 2 # 将一维索引 mid 转换为二维索引 x = matrix[mid // n][mid % n] # 判断中间元素与目标值的关系 if x == target: return True # 找到目标值，返回 True if x < target: l = mid + 1 # 目标值在右半部分 else: r = mid # 目标值在左半部分 # 未找到目标值，返回 False return False
栈
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
1 2 3 4 5 6 7 8 9 10 11
class Solution: def isValid(self, s: str) -> bool: dic = {')':'(',']':'[','}':'{'} stack = [] for i in s: if stack and i in dic: if stack[-1] == dic[i]: stack.pop() else: return False else: stack.append(i) return not stack
class Solution: def canJump(self, nums: List[int]) -> bool: if not nums :return False maxlong,n= 0,len(nums) for i in range(n): if i>maxlong: return False maxlong= max(i+nums[i],maxlong) return True
动态规划
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
1 2 3 4 5 6
class Solution: def climbStairs(self, n: int) -> int: a, b = 1, 1 for _ in range(n - 1): a, b = b, a + b return b
杨辉三角
给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。
1 2 3 4 5 6 7 8
class Solution: def generate(self, numRows: int) -> List[List[int]]: c = [[1] * (i + 1) for i in range(numRows)] for i in range(2, numRows): for j in range(1, i): # 左上方的数 + 正上方的数 c[i][j] = c[i - 1][j - 1] + c[i - 1][j] return c
多维动态规划
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
1 2 3 4 5 6 7
class Solution: def uniquePaths(self, m: int, n: int) -> int: f = [1] * n for i in range(1, m): for j in range(1, n): f[j] += f[j - 1] return f[n - 1]
最小路径和
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。**说明：**每次只能向下或者向右移动一步。
