取巧
1. 扫描时只养一个变量
这一家的共同点:从左往右一趟扫过去,全程只维护一个极值,它概括了前缀里所有需要知道的信息。
跳跃游戏:维护最远可达位置 max。
成立的根基是可达集合一定是连续区间 $[0, max]$,因为从任何可达位置 p 出发能到 p+1 到 p+nums[p] 的每一格,区间不会有洞。
于是”i 可达”等价于 i <= max,一个变量就装下了全部历史。
代码块收起展开
public boolean canJump(int[] nums) {
int max = 0; // 目前能踩到的最远下标
for (int i = 0; i < nums.length; i++) {
if (i > max) return false; // 我站不到 i, 后面更别提
max = Math.max(i + nums[i], max);
}
return true;
}跳跃游戏 II:求最少跳几次,口诀是隐式 BFS 分层。
cr 是当前这一跳能覆盖的边界,扫描途中用 nr 记下一跳能到的最远处,走到 cr 说明这一跳能到的位置全扫完了,必须起跳。
每一”层”就是 BFS 的一圈,只是不用真开队列。
代码块收起展开
// len-1!!!!!!!!!!!!!!!!!!!!!!!!!!
public int jump(int[] nums) {
int ans = 0, cr = 0, nr = 0; // cr=当前跳的边界, nr=下一跳最远
for (int i = 0; i < nums.length - 1; i++) { // n-1 是终点, 到了就不用再跳
nr = Math.max(nr, i + nums[i]);
if (i == cr) { // 这一跳的地盘走完了
cr = nr;
ans++;
}
}
return ans;
}买卖股票的最佳时机:维护历史最低价。今天卖出的最优利润 = 今天价格减历史最低买入价,扫一遍全程取 max。两个变量把二重循环压成一趟。
代码块收起展开
public int maxProfit(int[] prices) {
int min = prices[0], ans = 0;
for (int x : prices) {
ans = Math.max(ans, x - min); // 今天卖, 配历史最低买入
min = Math.min(min, x);
}
return ans;
}划分字母区间:先记下每个字母的最远出现位置 last[c]。
扫描时当前段的右边界 end 要不断吞进段内每个字母的 last,走到 i == end 说明段内所有字母的余生都被装下了,切一刀。
代码块收起展开
public List<Integer> partitionLabels(String s) {
List<Integer> ans = new ArrayList<>();
Map<Character, Integer> last = new HashMap<>();
for (int i = 0; i < s.length(); i++) last.put(s.charAt(i), i); // 每个字母最后出现处
int end = 0, pre = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, last.get(s.charAt(i))); // 段界吞进段内字母的最远出现
if (i == end) { // 段内字母的余生都装下了, 切
ans.add(i - pre + 1);
pre = i + 1;
}
}
return ans;
}2. 抵消
把无关的东西两两消掉,剩下的就是答案。抵消类的证明都靠一条:目标元素消不完。
多数元素:Boyer-Moore 投票。
维护一个候选人和票数,遇到同类加票,异类减票,票归零就换人。两个不同元素互相抵消,而多数派超过一半,跟所有异类一换一都杀不完,最后站着的必是它。
代码块收起展开
public int majorityElement(int[] nums) {
int cand = 0, votes = 0;
for (int x : nums) {
if (votes == 0) cand = x; // 前面全抵消完了, 换候选人
votes += (x == cand) ? 1 : -1;
}
return cand; // 多数派杀不完
}只出现一次的数字:全员异或。x ^ x = 0,成对的自我湮灭,顺序无所谓(交换律),最后剩下的就是落单的那个。
代码块收起展开
public int singleNumber(int[] nums) {
int ans = 0;
for (int x : nums) ans ^= x; // 成对湮灭
return ans;
}相交链表:指针 A 走完自己的链就转到 B 的头,B 同理。
两个指针各走 a + c + b 和 b + c + a 步,长度差被换道吸收,第二圈必然同步,在交点相遇,不相交则同时落到 null。口诀:走完你的路,再走我的路,路程就平了。
代码块收起展开
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = (a == null) ? headB : a.next; // 走到 null 才换道, 提前换会死循环
b = (b == null) ? headA : b.next;
}
return a; // 交点, 或共同的 null
}3. 值就是下标
数组的值域刚好落在 $[1, n]$ 或 $[0, n]$ 一类范围时,数组自己就能当哈希表用:值 v 的”家”是下标 v-1。这也是”不许开额外空间”约束下最常被暗示的一招。
缺失的第一个正数:把每个落在范围内的值 swap 回它的家(nums[i] 送去下标 nums[i]-1),送到不能送为止。
每次交换至少让一个数回家,所以均摊还是 $O(n)$。之后第一个”家里住错人”的下标 i,答案就是 i+1。
nums[x-1]=x
代码块收起展开
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// 值在 [1,n] 内, 且它家里住的还没归位, 就一直送回家
while (1 <= nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int t = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = t;
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) return i + 1; // 第一个住错人的家
}
return n + 1; // 全住对了, 如 [1,2] 答 3
}寻找重复数:把下标 i 到 nums[i] 看成 next 指针,数组变成链表。
重复的值意味着某个节点有两条入边,也就是环的入口,于是题目变成 环形链表 II,上 Floyd 快慢指针。
这题是”建模取巧”的极致,找重复数和找环入口表面毫无关系。
代码块收起展开
public int findDuplicate(int[] nums) {
int fast = nums[0], slow = nums[0];
do { // 阶段一: 快慢指针找相遇点
fast = nums[nums[fast]];
slow = nums[slow];
} while (fast != slow);
fast = nums[0]; // 阶段二: 一个回起点, 同速齐走
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow; // 再会处 = 环入口 = 重复值
}4. 前后缀分解
答案在每个位置上都能拆成”左边的贡献 × 右边的贡献”时,两趟扫描分别攒出前缀量和后缀量,逐位一拼就完了。
除自身以外数组的乘积:answer[i] = i 左边全部的积 × i 右边全部的积。
先从左往右把前缀积写进输出数组,再从右往左用一个变量滚后缀积乘上去,额外空间 $O(1)$。
代码块收起展开
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
ans[0] = 1;
for (int i = 1; i < n; i++) ans[i] = ans[i-1] * nums[i-1]; // 左边的积
int suf = 1; // 右边的积, 滚动
for (int i = n - 1; i >= 0; i--) {
ans[i] *= suf;
suf *= nums[i];
}
return ans;
}接雨水:每根柱子头顶的水 = min(左边最高, 右边最高) - 自身高度,木桶效应。
前后缀 max 各扫一趟就出答案;双指针版更进一步,哪边的 max 小就先结算哪边,把两个数组也省了。
代码块收起展开
public int trap(int[] height) {
int l = 0, r = height.length - 1;
int lMax = 0, rMax = 0, ans = 0;
while (l < r) {
lMax = Math.max(lMax, height[l]);
rMax = Math.max(rMax, height[r]);
if (lMax < rMax) ans += lMax - height[l++]; // 矮的一侧封顶已定, 直接结算
else ans += rMax - height[r--];
}
return ans;
}乘积最大子数组:答案必然是某一段的前缀积或后缀积。
0 把数组切段;段内负数个数为偶整段最优,为奇则只能砍掉头或尾的某个负数,砍完剩下的恰好是前缀或后缀。
于是枚举所有前缀积和后缀积就覆盖了全部候选,撞到 0 重置为 1 开新段。
代码块收起展开
public int maxProduct(int[] nums) {
int len = nums.length, ans = nums[0];
int prefix = 1, suffix = 1;
for (int i = 0; i < len; i++) {
prefix *= nums[i]; // 从左啃: 所有前缀积
suffix *= nums[len - 1 - i]; // 从右啃: 所有后缀积
ans = Math.max(ans, Math.max(prefix, suffix));
if (prefix == 0) prefix = 1; // 撞 0 切段, 重开
if (suffix == 0) suffix = 1;
}
return ans;
}5. 翻转魔法
旋转、轮转这类操作,都能拆成几次翻转或镜像的组合。翻转是 $O(1)$ 空间里最强的重排原语。
轮转数组:右移 k 位 = 整体翻转,再翻前 k 个,再翻剩下的。三次翻转,零额外空间。
代码块收起展开
public void rotate(int[] nums, int k) {
k %= nums.length; // k 可能大于数组长度
reverse(nums, 0, nums.length - 1); // 全翻
reverse(nums, 0, k - 1); // 前 k 个翻回来
reverse(nums, k, nums.length - 1); // 剩下的翻回来
}
private void reverse(int[] nums, int l, int r) {
while (l < r) {
int t = nums[l];
nums[l++] = nums[r];
nums[r--] = t;
}
}旋转图像:顺时针转 90 度 = 沿主对角线转置 + 每行左右翻转。两次镜像合成一次旋转,原地完成。
代码块收起展开
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) { // 转置: 只走下三角, 走满会换回去
int t = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = t;
}
}
for (int[] row : matrix) { // 每行左右翻转
int l = 0, r = n - 1;
while (l < r) {
int t = row[l];
row[l++] = row[r];
row[r--] = t;
}
}
}下一个排列:从右找第一个升序拐点,右侧捞出刚好更大的数换上来,再把后缀翻转成升序。原则一句话:改动尽量靠右,改完的后缀归最小。
代码块收起展开
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // 找拐点: 右边是纯降序
if (i >= 0) { // i=-1 说明已是最大排列
int j = n - 1;
while (nums[j] <= nums[i]) j--; // 右边第一个比 nums[i] 大的
swap(nums, i, j); // 降序里从右数第一个就是最小的
}
reverse(nums, i + 1, n - 1); // 后缀降序翻成升序(最小)
}
// swap / reverse 两个辅助方法同轮转数组6. 对撞指针的淘汰论证
左右指针往中间收,每步淘汰一个”再也用不上”的端点。这家题的核心是淘汰的正确性证明,而口诀通常就是”动谁”。
盛最多水的容器:动短板。短板和更靠内任何一块板的组合,宽度更窄、高度封顶在短板,不可能更好,所以短板这个端点可以放心退场。
代码块收起展开
public int maxArea(int[] height) {
int l = 0, r = height.length - 1, ans = 0;
while (l < r) {
ans = Math.max(ans, (r - l) * Math.min(height[l], height[r]));
if (height[l] < height[r]) l++; // 动短板, 它已到极限
else r--;
}
return ans;
}颜色分类:荷兰国旗三指针,一趟把 0 扔左边、2 扔右边。唯一的坑:和右指针交换完 i 不能前进,换过来的元素还没验过货;和左指针换完可以前进。
代码块收起展开
public void sortColors(int[] nums) {
int p0 = 0, p2 = nums.length - 1;
for (int i = 0; i <= p2; ) {
if (nums[i] == 0) swap(nums, i++, p0++); // 0 扔左, 换来的已验过, i 走
else if (nums[i] == 2) swap(nums, p2--, i); // 2 扔右, 换来的没验过, i 不动!
else i++;
}
}移动零:快慢指针,非零元素往前压实,剩下的位置补零。同族里最朴素的一个。
代码块收起展开
public void moveZeroes(int[] nums) {
int pos = 0;
for (int x : nums) {
if (x != 0) nums[pos++] = x; // 非零往前压实
}
Arrays.fill(nums, pos, nums.length, 0); // 注意这个 api 左闭右开
}7. 哈希把”找”变成 O(1)
内层循环在”找一个配对”的,都可以边扫边把见过的东西塞进哈希表,把二重循环拍扁成一趟。
两数之和:表里存”我出现过”,每到一个数查 target - x 在不在。
代码块收起展开
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(); // 值 -> 下标
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (map.containsKey(need)) return new int[]{map.get(need), i};
map.put(nums[i], i);
}
return new int[0];
}和为 K 的子数组:子数组和 = 两个前缀和之差,S[i] - S[j] = k 变成查 S[i] - k 出现过几次。
枚举区间的两个端点被压成了查一个数,记得先放进 {0: 1} 兜住从头开始的段。树上版本就是路径总和 III,多一步回溯撤销。
代码块收起展开
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1); // 空前缀, 兜住从头开始的段
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += cnt.getOrDefault(sum - k, 0); // 有几个前缀和等于 sum-k
cnt.merge(sum, 1, Integer::sum);
}
return ans;
}最长连续序列:全塞进 Set,只在 x - 1 不存在时才从 x 起跑往右数。
每个连续段只会被它的起点完整走一遍,其他元素查一下就闪,总量 $O(n)$。没有起点剪枝这题就退化成 $O(n^2)$。
代码块收起展开
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
int ans = 0;
for (int x : set) {
if (set.contains(x - 1)) continue; // 有 x-1 在, 轮不到我起跑
int len = 1;
while (set.contains(++x)) len++;
ans = Math.max(ans, len);
}
return ans;
}8. 快速复述表
复习方法:遮住右列,对每题先把那句话说出来,说不出就回上面看为什么。
| 题目 | 一句话口诀 |
|---|---|
| 跳跃游戏 | 可达集是连续前缀,养一个最远可达 |
| 跳跃游戏 II | 隐式 BFS,到边界就跳数加一 |
| 买卖股票的最佳时机 | 今天卖,减历史最低价 |
| 划分字母区间 | 段界吞进每个字母的最远出现 |
| 多数元素 | 一换一抵消,过半者杀不完 |
| 只出现一次的数字 | 异或成对湮灭 |
| 相交链表 | 走完你的路再走我的路,路程就平了 |
| 缺失的第一个正数 | 值 v 的家是下标 v-1,swap 回家 |
| 寻找重复数 | 下标连成链表,重复值 = 环入口,Floyd |
| 除自身以外数组的乘积 | 前缀积乘后缀积 |
| 接雨水 | 头顶的水 = min(左最高, 右最高) - 自身 |
| 乘积最大子数组 | 答案必是前缀积或后缀积,0 切段 |
| 轮转数组 | 全翻,再分两段各翻 |
| 旋转图像 | 转置加行翻转 |
| 下一个排列 | 拐点,捞刚好更大的,后缀翻升序 |
| 盛最多水的容器 | 动短板,短板已到极限 |
| 颜色分类 | 三指针,和右边换完不挪 i |
| 两数之和 | 边走边存,查 target 减我 |
| 和为 K 的子数组 | 前缀和之差,查表计数 |
| 最长连续序列 | x-1 不在才起跑 |
这张表的正确用法:卡在某道新题、看完题解恍然大悟的时候,把”那句观察”提炼出来续在表尾。结论攒多了,取巧题就全变成了送分题。