最近在准备找工作，跟着代码随想录上的刷题顺序刷一遍LeetCode。虽然也刷过几百道LeetCode题了，但是没有按照题目的类别去刷，这次系统地刷一遍题目，总结一下方法和套路。
原网站的题解是C++版本的，我使用的是Python，会额外记录Python刷题时一些坑以及技巧。
数组
数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合。
Python中的list不要求相同类型。 Python中的array.array中的元素是相同类型的。
二分查找(704)
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid+1 elif nums[mid] >target: right = mid-1 return -1
移除元素(27)
#双指针
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
方法一：双指针。（覆盖）
class Solution: def removeElement(self, nums: List[int], val: int) -> int: fast = 0 slow = 0 while fast < len(nums): if nums[fast] == val: fast += 1 else: nums[slow] = nums[fast] fast += 1 slow += 1 return slow
方法二：pop。
class Solution: def removeElement(self, nums: List[int], val: int) -> int: for i in range(len(nums)-1, -1, -1):# 注意顺序 if nums[i] == val: nums.pop(i) return len(nums)
有序数组的平方(977)
#双指针
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: res = [0]*len(nums) i = 0 j = len(nums) - 1 end = len(nums)-1 while j >= i: if abs(nums[i]) > abs(nums[j]): res[end] = nums[i]**2 i += 1 else: res[end] = nums[j]**2 j -= 1 end -= 1 return res
长度最小的子数组(209)
#滑动窗口
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: res = 10**6 s = 0 i = 0 # 窗口左边界 for j in range(len(nums)): # j是窗口的右边界 s += nums[j] # 每次更新i(起始位置) while s >= target: subLength = j-i+1 res = res if res < subLength else subLength s -= nums[i] i += 1 return res if res != 10**6 else 0
如果使用暴力搜索，是O(n^2)。
而窗口法只遍历右边界j，左边界i通过（s >= target）条件下向右滑。
python 缩进好容易看错，尤其是在leetcode的编辑器中。
螺旋矩阵(59)
#模拟
模拟在矩阵里行走的过程。
class Solution: def generateMatrix(self, n: int) -> List[List[int]]: def next_(i,j,direction): if direction == 'right': if j < n-1 and mat[i][j+1] == 0 : j += 1 else: direction = 'down' i += 1 elif direction == 'down': if i < n-1 and mat[i+1][j] == 0: i += 1 else: direction = 'left' j -= 1 elif direction == 'left': if j > 0 and mat[i][j-1] == 0: j -= 1 else: direction = 'up' i -= 1 elif direction == 'up': if i > 0 and mat[i-1][j] == 0: i -= 1 else: direction = 'right' j += 1 return i, j, direction mat = [[0 for j in range(n)] for i in range(n)] i,j = 0,0 direction = 'right' for x in range(1, 1+n**2): mat[i][j] = x i,j,direction = next_(i,j,direction) print(i,j,direction) return mat
LeetCode官网给出的题解更简洁。参考官网的解后优化了一下自己的代码：
class Solution: def generateMatrix(self, n: int) -> List[List[int]]: directions = [(0,1), (1,0), (0,-1), (-1,0)] # 右 下 左 上 def next_(i,j,directionIndex): direction = directions[directionIndex] t_i, t_j = i + direction[0], j + direction[1] if not (0<= t_i <= n-1) or not (0<= t_j <= n-1) or mat[t_i][t_j] != 0: directionIndex = (directionIndex +1) % 4 direction = directions[directionIndex] t_i, t_j = i + direction[0], j + direction[1] return t_i, t_j, directionIndex mat = [[0 for j in range(n)] for i in range(n)] i,j = 0,0 directionIndex = 0 # 右 for x in range(1, 1+n**2): mat[i][j] = x i,j,directionIndex = next_(i,j,directionIndex) return mat
数组小结
数组是一种基础的数据结构，在Python中一般用list来实现。
LeetCode中的题目需要注意给出的数组是否有序。通常会用到双指针、滑动窗口等技巧。
长度最小的子数组(209)比较有难度，要想到滑动窗口，还要想到遍历窗口的终止位置j，滑动起始位置i。
