算法专项
算法专项
从力扣刷题中提炼的算法知识点、Python 语法技巧和常见模式,按知识点分类整理。
每条标注来源题目,方便回溯查看完整笔记。
一、遍历技巧
enumerate():同时获取下标与元素
1 | for i, ch in enumerate(s): |
反向遍历
1 | for i in range(len(digits) - 1, -1, -1): |
二、列表操作
append 与 extend 的区别
来源:1768.交替合并字符串
1 | ans.append(word1[i]) |
列表负下标
来源:682.棒球比赛
1 | points.append(points[len(points) - 1] + points[len(points) - 2]) |
嵌套列表推导式
1 | ls = [[' ' for _ in range(3)] for _ in range(3)] |
列表原地修改:nums[:] vs nums
来源:189.轮转数组
题目要求原地修改时,nums = nums[-k:] + nums[:-k] 会创建新列表并重新绑定变量,不修改原数组;必须用切片赋值:
1 | nums[:] = nums[-k:] + nums[:-k] # 原地修改 |
同理,nums.reverse() 是原地方法,而 reversed(nums) 返回迭代器。
三、字符与字符串转换
ord() 与 chr() 及转换表
来源:389.找不同
| 转换方向 | 函数 |
|---|---|
| 字符 → 整数 | ord(c) |
| 整数 → 字符 | chr(n) |
| 字符 → 字节 | "x".encode() |
| 字节 → 字符 | b"...".decode() |
| 整数 → 十六进制 | hex() |
| 整数 → 二进制 | bin() |
| 字符串数字 → 整数 | int() |
str.count():统计字符出现次数
1 | count_ch1 = string.count(ch) |
str.find():查找子串位置
来源:459.重复的子字符串
1 | s1.find(s2, 1) |
四、链表操作
dummy 哑节点
创建哨兵节点,统一处理头节点插入,避免对空链表/头节点的特殊判断,最后返回 dummy.next:
1 | dummy = ListNode(0) # 哑节点 |
反转链表的两种写法
来源:206.反转链表
迭代(三指针 + 暂存后继):
1 | curr, prev = head, None |
递归:
1 | def recur(cur, pre): |
用栈逆序处理链表
来源:445.两数相加 II
链表只能单向遍历,需要”从尾部开始”时,可先压栈再 pop() 实现逆序:
1 | while l1: |
本质是「两数之和 + 反转链表」的组合技。
加法模拟:carry 进位
两数相加类题目的统一框架:total = a + b + carry,total % base 存当前位,total // base 产生进位,循环条件必须包含 carry:
1 | carry = 0 |
五、双指针
左右指针(有序数组)
有序数组求和问题,左右指针相向移动,根据当前和与目标的大小决定移动方向,O(n):
1 | left, right = 0, len(numbers) - 1 |
双指针原地交换
来源:283.移动零
left 指向待写入位置,right 遍历;非零元素直接交换到前面,保持相对顺序:
1 | left = right = 0 |
倒序双指针(原地合并)
来源:88.合并两个有序数组
两个有序数组要合并到其中一个数组的尾部空间时,从后往前填充可以避免覆盖未处理元素:
1 | pos1, pos2 = m - 1, n - 1 |
快慢指针(覆盖式原地移除/去重)
write 指向待写入位置,read 遍历原数组;遇到符合条件的元素覆盖到 write 并前进。与「原地交换」(283)的区别:这里无需保留被覆盖的旧值,直接覆盖更简单:
1 | # 27. 移除元素(通用:按值过滤) |
滑动窗口(哈希表 + 左指针更新)
来源:3.无重复字符的最长子串
右指针 j 遍历,哈希表记录字符最近出现位置;左指针 i 维护窗口起点。关键:i = max(dic[ch], i) 必须取 max,否则窗口左边界可能回退:
1 | dic, res, i = {}, 0, -1 |
六、哈希表(字典)
计数列表经典写法
来源:242.有效的字母异位词
1 | count = [0] * 26 |
值→下标字典,边查边存
来源:1.两数之和
用字典以「值→下标」存储已遍历元素,每步只查 target - num 是否已出现,O(n):
1 | hashtable = dict() |
注意「先查后存」的顺序,防止同一个元素被用两次。
判重、最近索引与频次统计
来源:217.存在重复元素、219.存在重复元素 II、350.两个数组的交集 II
哈希表三种常见用途:
- 判重:
if num in hashtable判断是否出现过 - 最近索引:值→最近下标,配合
i - hashtable[num] <= k判断窗口距离 - 频次统计:值→出现次数,交集时取
min(count1, count2)
多维哈希判重(数独)
来源:36.有效的数独
用行、列、宫三个哈希结构分别判重。宫坐标 (i//3, j//3) 可压缩为一维 (i//3)*3 + j//3,避免三维数组:
1 | row = [[False] * 9 for _ in range(9)] |
七、位运算
异或抵消法
来源:389.找不同
相同数异或为 0,遍历两串全部字符做异或,剩下的就是多出的那一个:
1 | ans = 0 |
快速幂(二分幂)
来源:50.Pow(x, n)
把指数 n 看作二进制,底数每轮自乘,遇到 n 的二进制位为 1 时累乘,O(log n):
1 | result = 1.0 |
/ 与 // 的区别
1 | # // 计算只会得到向 -∞ 方向取整的 int 型 |
八、矩阵操作
O(1) 空间标记法(第一行/列作标记)
来源:73.矩阵置零
不额外开行/列标记数组,直接利用原矩阵的第一行、第一列记录是否含 0;注意先用变量保存第一行/列的原始状态:
1 | flag_col0 = any(matrix[i][0] == 0 for i in range(m)) |
主副对角线下标关系
n×n 矩阵中:主对角线满足 i == j,副对角线满足 i + j == n - 1;中心元素(n 为奇数时)两对角线交点,勿重复累加:
1 | for i, row in enumerate(mat): |
螺旋遍历:directions 转向法
来源:54.螺旋矩阵
二维矩阵模拟一类的解法:用 directions + dir_idx 控制移动方向,配合哈希表(或 visited 矩阵)确认未走过的路径,撞墙/回头时转向。此方法在螺旋题与路径规划题中通用:
1 | class Solution: |
要点:
dir_idx = (dir_idx + 1) % 4实现循环转向visited用于记录已走过的格子,避免走回头路- 撞墙判断(越界)与回头判断(visited)合并为同一个条件
原地旋转矩阵(四元素循环交换)
来源:48.旋转图像
顺时针 90° 映射:(i, j) → (j, n-1-i)。原地做法每次循环交换四个元素,只需遍历左上角 (n//2) × ((n+1)//2) 区域:
1 | for i in range(n // 2): |
要点:
- 只遍历左上角四分之一区域,避免重复交换
- 四个元素按「下→右→上→左」顺序循环赋值,
tmp暂存起点 - 先写辅助矩阵版本(额外空间)再优化成原地,是清晰的两步走路径
九、常用内置函数
map():对可迭代对象批量应用函数
1 | map(func, iterable1, iterable2, ...) |
典型用法:
1 | max(map(sum, matrix)) # 二维数组按行求和取最大 |
divmod():同时取商和余数
1 | d, r = divmod(c, d) |
any():任一元素满足条件
来源:73.矩阵置零
1 | with_zero = any(lis[i] == 0 for i in range(len(lis))) |
lambda 匿名函数
1 | pre = lambda x: (x + 1) >> 1 |
三元表达式
1 | return True if a == b else False |
for-else 结构
来源:28.找出字符串中第一个匹配项的下标、459.重复的子字符串
for 循环正常结束(未被 break 打断) 时执行 else 分支,常用于”全部满足/找到”的判断:
1 | for j in range(i, n): |
十、算法思想
KMP 字符串匹配
- 核心思路:利用已匹配部分的信息避免重复比较——之前位置的后缀相当于后面位置的前缀
- 预处理:构建 next 数组,next[i] 记录 needle[0:i] 的最长公共前后缀长度
- 匹配:字符不匹配时,j 回退到 next[j - 1] 位置
贪心算法
来源:860.柠檬水找零
- 在每一步选择中都采取当前状态下”最优”的选择,不考虑整体后果
- 在某些问题中,这种”短视”策略恰好能推出全局最优解
买卖股票类贪心
来源:121.买卖股票的最佳时机、122.买卖股票的最佳时机 II
- 单次交易(121):遍历时维护最低价
minprice,每步更新最大利润max(profit, price - minprice) - 多次交易(122):只要今天比昨天涨,就累加差价
if prices[i] > prices[i-1]: ans += prices[i] - prices[i-1]
1 | # 121 |
摩尔投票(Boyer-Moore)
来源:169.多数元素
找出现次数超过 ⌊n/2⌋ 的元素,O(n) 时间、O(1) 空间:
1 | ans = hp = 0 |
复数坐标系模拟
1 | a = 0 + 0j |
十一、数学小技巧
前缀函数统计奇数个数
定义前缀函数 pre(x) 为 [0, x] 内奇数个数 (x + 1) // 2,区间答案 = 前缀差:
1 | pre = lambda x: (x + 1) >> 1 |
符号翻转,避免大数溢出
只需判断乘积符号,不必真算乘积:遇 0 直接返回 0,遇负数翻转符号(等价于统计负数个数奇偶):
1 | sign = 1 |
重复子串的字符串技巧
来源:459.重复的子字符串
若 s 由子串重复构成(s = t+t+…),则 s’ = s + s 中必然在中间某处能找到 s:
1 | return (s + s).find(s, 1) != len(s) |
(从下标 1 开始找,若找到的 s 不在第 2 个 s 的位置即 len(s),说明是重复子串构成)