53. 最大子数组和 - 力扣（LeetCode）
空间复杂度：O(N)，需要额外的空间来存储哈希表。def firstMissingPositive(nums): n = len(nums) # 将所有的负数和零替换为n+1，n+1是一个不可能出现在合法输出中的数字 for i in range(n): if nums[i] <= 0: nums[i] = n + 1 # 使用数组索引作为哈希键，通过置负标记存在的数字 for i in range(n): num = abs(nums[i]) if num <= n: nums[num - 1] = -abs(nums[num - 1]) # 寻找第一个大于0的索引位置，即是缺失的最小正数 for i in range(n): if nums[i]> 0: return i + 1 # 如果数组中包含了1到n的所有数字，则缺失的第一个正数是n+1 return n + 1# 示例调用print(firstMissingPositive([1, 2, 0])) # 输出: 3print(firstMissingPositive([3, 4, -1, 1])) # 输出: 2print(firstMissingPositive([7, 8, 9, 11, 12])) # 输出: 1
矩阵
73. 矩阵置零 - 力扣（LeetCode）
空间复杂度为 O(m+n) 的解法
在这种解法中，我们使用两个集合（或列表）来分别记录需要置零的行和列。
1.将所有非正整数（负数和零）替换为一个不可能出现在结果中的数字（n + 1）
2.遍历数组，将每个数字对应的索引位置的值置为负数，表示该数字存在。但是，我们需要先检查第一行和第一列本身是否包含0。
def setZeroes(matrix): if not matrix or not matrix[0]: return m, n = len(matrix), len(matrix[0]) first_row_zero = any(matrix[0][j] == 0 for j in range(n)) first_col_zero = any(matrix[i][0] == 0 for i in range(m)) # 使用第一行和第一列作为标记 for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = 0 matrix[0][j] = 0 # 根据第一行和第一列的标记来置零 for i in range(1, m): if matrix[i][0] == 0: for j in range(1, n): matrix[i][j] = 0 for j in range(1, n): if matrix[0][j] == 0: for i in range(1, m): matrix[i][j] = 0 # 如果第一行原本有0，则将第一行置零 if first_row_zero: for j in range(n): matrix[0][j] = 0 # 如果第一列原本有0，则将第一列置零 if first_col_zero: for i in range(m): matrix[i][0] = 0# 示例matrix = [ [1, 1, 1], [1, 0, 1], [1, 1, 1]]setZeroes(matrix)print(matrix) # 输出: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
48. 旋转图像 - 力扣（LeetCode）
矩阵顺时针旋转相当于先沿着对角线交换元素，然后反转每一行
class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ n = len(matrix) for i in range(n): # 注意这里j的范围 如果j的范围也是0到n-1那么会出现交换后又交换回来 等于没有交换 for j in range(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] for line in matrix: line.reverse()
逆时针旋转90度
class Solution: def rotate(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ n = len(matrix) # 既然副对角线为主那么i的范围就是从n-1到0啦 因为python的range是左闭右开所以是n-1和-1 for i in range(n-1,-1): # 注意这里j的范围 如果j的范围也是0到n-1那么会出现交换后又交换回来 等于没有交换 for j in range(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] for line in matrix: line.reverse()
54. 螺旋矩阵 - 力扣（LeetCode）
class Solution(object): def spiralOrder(self, matrix): """ :type matrix: List[List[int]] :rtype: List[int] """ result = [] while matrix: # 取出矩阵的第一行 result += matrix.pop(0) # 旋转矩阵使其再次符合顺时针顺序 #zip(*matrix)会将矩阵的行转换为列，#并返回一个迭代器，而list()将其转换为列表，[::-1]将列表中的元素逆序，从而实现逆时针旋转90度。class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: if len(intervals) == 0: return intervals intervals.sort(key=lambda x: x[0]) result = [] for i,num in enumerate(intervals): if len(result)==0 or num[0]>result[-1][1]: result.append(num) else: result[-1][1]=max(result[-1][1],num[1]) return result
相似题目：
435. 无重叠区间 - 力扣（LeetCode）
根据区间右边界升序排列；
维护right，代表已留下区间的最大右边界；
遍历排序后的区间：
如果当前区间的左边界 ≥ right，该区间可以留下，更新right
如果当前区间的左边界 < right，该区间去除，更新结果res
class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: if not intervals: return 0 intervals.sort(key = lambda x : x[1]) res = 0 right = intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] < right: res += 1 else: right = intervals[i][1] return resa=Solution()a. eraseOverlapIntervals(intervals =[[1,2],[2,3],[3,4],[1,3]])
189. 轮转数组 - 力扣（LeetCode）
class Solution: def rotate(self, nums: List[int], k: int) -> None: # 定义反转函数：原地反转 nums[i..j] 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 >= n 的情况（如 k=10, n=7 → k=3） reverse(0, n - 1) # 整体反转 reverse(0, k - 1) # 反转前 k 个元素 reverse(k, n - 1) # 反转剩余元素
切片
class Solution: def rotate(self, nums: List[int], k: int) -> None: k %= len(nums) nums[:] = nums[-k:] + nums[:-k]
相似题目:
151. 反转字符串中的单词 - 力扣（LeetCode）
class Solution: def reverseWords(self, s: str) -> str: return " ".join(reversed(s.split()))
238. 除自身以外数组的乘积 - 力扣（LeetCode）
这个属于动态规划中的前后缀分解问题
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) pre = [1] * n for i in range(1, n): pre[i] = pre[i - 1] * nums[i - 1] suf = [1] * n for i in range(n - 2, -1, -1): suf[i] = suf[i + 1] * nums[i + 1] return [p * s for p, s in zip(pre, suf)]
41. 缺失的第一个正数 - 力扣（LeetCode）
哈希表方法：将所有正数存储在哈希表中，从 1 开始递增寻找不在哈希表中的最小正数。双指针。
def firstMissingPositive(nums): num_set = set(nums) target = 1 while target in num_set: target += 1 return target# 示例调用print(firstMissingPositive([1, 2, 0])) # 输出: 3print(firstMissingPositive([3, 4, -1, 1])) # 输出: 2print(firstMissingPositive([7, 8, 9, 11, 12])) # 输出: 1
- 时间复杂度：O(N)，虽然使用了哈希表，但构建哈希表和查询的总时间仍是线性的。
