/* 滑动窗口算法框架 */ voidslidingWindow(string s, string t){ unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 右移窗口 right++; // 进行窗口内数据的一系列更新 ...
比如给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
状态转移方程：
自顶向下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
defcoinChange(coins: List[int], amount: int): defdp(n): # base case if n == 0: return0 if n < 0: return-1 # 求最小值，所以初始化为正无穷 res = float('INF') for coin in coins: subproblem = dp(n - coin) # 子问题无解，跳过 if subproblem == -1: continue res = min(res, 1 + subproblem) return res if res != float('INF') else-1 return dp(amount)
自底向上：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
defcoinChange(coins: List[int], amount: int): # 备忘录 memo = dict() defdp(n): # 查备忘录，避免重复计算 if n in memo: return memo[n] if n == 0: return0 if n < 0: return-1 res = float('INF') for coin in coins: subproblem = dp(n - coin) if subproblem == -1: continue res = min(res, 1 + subproblem) # 记入备忘录 memo[n] = res if res != float('INF') else-1 return memo[n] return dp(amount)
dp 遍历存在技巧：
遍历的过程，所需的状态必须是计算出来的。
遍历的终点必须是存储结果的位置。
背包问题
背包分多种，首先是01背包，给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
1 2 3 4 5 6 7
Input： N = 3, W = 4 wt = [2, 1, 3] val = [4, 2, 3]
// 子集背包状态压缩模板 boolcanPartition(vector<int>& nums){ int sum = 0, n = nums.size(); for (int num : nums) sum += num; if (sum % 2 != 0) returnfalse; sum = sum / 2; vector<bool> dp(sum + 1, false); // base case dp[0] = true; for (int i = 0; i < n; i++) for (int j = sum; j >= 0; j--) if (j - nums[i] >= 0) dp[j] = dp[j] || dp[j - nums[i]]; return dp[sum]; }
// 最短编辑距离模板 intminDistance(String s1, String s2){ int m = s1.length(), n = s2.length(); int[][] dp = newint[m + 1][n + 1]; // base case for (int i = 1; i <= m; i++) dp[i][0] = i; for (int j = 1; j <= n; j++) dp[0][j] = j; // 自底向上求解 for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min( dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i-1][j-1] + 1 ); // 储存着整个 s1 和 s2 的最小编辑距离 return dp[m][n]; } intmin(int a, int b, int c){ return Math.min(a, Math.min(b, c)); }
可以将这里的 int[] dp 实现一个类比如 Node[][] dp，其中保存 val 为具体操作，可以以此反推编辑细节。
扔鸡蛋问题
题目是这样：你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层 F 呢？
m = dp[K, N] 表示当前状态为 k 个鸡蛋，面对 n 层楼，这个状态下最少的扔鸡蛋次数 m。
min(res, max(dp,dp) + 1) 的含义是最坏情况下的最少次数，外层 for 枚举的是 N ，选择出尝试次数最少的哪一层。
// 股票买卖模板 dp[i][k][0 or 1] 0 <= i <= n-1, 1 <= k <= K // n 为天数，大 K 为最多交易数 // 此问题共 n × K × 2 种状态，全部穷举就能搞定。 for0 <= i < n: for1 <= k <= K: for s in {0, 1}: dp[i][k][s] = max(buy, sell, rest)
// 二分模板 intbinarySearch(int[] nums, int target){ int left = 0, right = ...;
while(...) { int mid = left + (right - left) / 2; if (nums[mid] == target) { ... } elseif (nums[mid] < target) { left = ... } elseif (nums[mid] > target) { right = ... } } return ...; }
不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。
计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。这样算的是左中位数。
Java 中可以用 (left + right) >>> 1 来防止溢出，这样算的是右中位数。
whilie 中的内容与 right 的初始值关系到区间的开闭，如果用 left < right 同时 right 是 nums.length 则区间是 (left, right] ；如果使用 left <= right 同时 right 是 nums.length - 1 则区间是 [left, right] 。 推荐用后一种。
如果当前 mid 不对，那么就要根据区间来改 right 和 left ，如果区间是 [] (推荐)，那么自然下一个就是 left = mid + 1 或 right = mid - 1 ；如果区间是 [) ，那么下一个就是 left = mid + 1 或 right = mid 。
知道了这些，来看左边界二分查找：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// 左边界二分，左闭右开 intleft_bound(int[] nums, int target){ if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意
while (left < right) { // 注意 int mid = (left + right) / 2; if (nums[mid] == target) { right = mid; } elseif (nums[mid] < target) { left = mid + 1; } elseif (nums[mid] > target) { right = mid; // 注意 } } return left; }
// 求吃香蕉速度，左边界二分解 intminEatingSpeed(int[] piles, int H){ // 套用搜索左侧边界的算法框架 int left = 1, right = getMax(piles) + 1; while (left < right) { // 防止溢出 int mid = left + (right - left) / 2; if (canFinish(piles, mid, H)) { right = mid; } else { left = mid + 1; } } return left; } // 时间复杂度 O(N) booleancanFinish(int[] piles, int speed, int H){ int time = 0; for (int n : piles) { time += timeOf(n, speed); } return time <= H; } // 当前堆耗费时间 inttimeOf(int n, int speed){ return (n / speed) + ((n % speed > 0) ? 1 : 0); } intgetMax(int[] piles){ int max = 0; for (int n : piles) max = Math.max(n, max); return max; }
// 二分判断子串模板 booleanisSubsequence(String s, String t){ int m = s.length(), n = t.length(); // 对 t 进行预处理 ArrayList<Integer>[] index = new ArrayList[256]; for (int i = 0; i < n; i++) { char c = t.charAt(i); if (index[c] == null) index[c] = new ArrayList<>(); index[c].add(i); }
// 串 t 上的指针 int j = 0; // 借助 index 查找 s[i] for (int i = 0; i < m; i++) { char c = s.charAt(i); // 整个 t 压根儿没有字符 c if (index[c] == null) returnfalse; int pos = left_bound(index[c], j); // 二分搜索区间中没有找到字符 c if (pos == index[c].size()) returnfalse; // 向前移动指针 j j = index[c].get(pos) + 1; } returntrue; } // 查找左侧边界的二分查找 intleft_bound(ArrayList<Integer> arr, int tar){ int lo = 0, hi = arr.size(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (tar > arr.get(mid)) { lo = mid + 1; } else { hi = mid; } } return lo; }
重点是用一个字典 index 将每个字符出现的索引位置按顺序存储下来，然后二分搜索 index[c] 中比 j 大的那个索引，即左边界二分。
双指针技巧
快慢指针都比较简单，比较难理解的是有环链表判断环起点。直接上代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
ListNode detectCycle(ListNode head){ ListNode fast, slow; fast = slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) break; } // 上面的代码类似 hasCycle 函数 slow = head; while (slow != fast) { fast = fast.next; slow = slow.next; } return slow; }
q.offer(start); // 将起点加入队列 visited.add(start); int step = 0; // 记录扩散的步数
while (q not empty) { int sz = q.size(); /* 将当前队列中的所有节点向四周扩散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 划重点：这里判断是否到达终点 */ if (cur is target) return step; /* 将 cur 的相邻节点加入队列 */ for (Node x : cur.adj()) if (x not in visited) { q.offer(x); visited.add(x); } } /* 划重点：更新步数在这里 */ step++; } }
cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；
// 链表反转前 n 个节点模板 递归 ListNode successor = null; // 后驱节点 // 反转以 head 为起点的 n 个节点，返回新的头结点 ListNode reverseN(ListNode head, int n){ if (n == 1) { // 记录第 n + 1 个节点 successor = head.next; return head; } // 以 head.next 为起点，需要反转前 n - 1 个节点 ListNode last = reverseN(head.next, n - 1); head.next.next = head; // 让反转之后的 head 节点和后面的节点连起来 head.next = successor; return last; }
和完整的反转基本相同，这里不同的地方在于 successor 节点，它需要被 head.next 引用，后续的节点顺序不变。
如果是反转一部分节点呢？
1 2 3 4 5 6 7 8 9 10 11
// 链表反转部分节点模板 递归 ListNode reverseBetween(ListNode head, int m, int n){ // base case if (m == 1) { // 相当于反转前 n 个元素 return reverseN(head, n); } // 前进到反转的起点触发 base case head.next = reverseBetween(head.next, m - 1, n - 1); return head; }
对于 m = 1 相当于反转前 n 个节点；
而当 m != 1 时，如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；
// 链表反转模板 迭代 // 反转以 a 为头结点的链表 ListNode reverse(ListNode a){ ListNode pre, cur, nxt; pre = null; cur = a; nxt = a; while (cur != null) { nxt = cur.next; // 逐个结点反转 cur.next = pre; // 更新指针位置 pre = cur; cur = nxt; } // 返回反转后的头结点 return pre; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// 链表反转区间模板 迭代 /** 反转区间 [a, b) 的元素，注意是左闭右开 */ ListNode reverse(ListNode a, ListNode b){ ListNode pre, cur, nxt; pre = null; cur = a; nxt = a; // while 终止的条件改一下就行了 while (cur != b) { nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } // 返回反转后的头结点 return pre; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// 链表反转 k 个一组模板 迭代 ListNode reverseKGroup(ListNode head, int k){ if (head == null) returnnull; // 区间 [a, b) 包含 k 个待反转元素 ListNode a, b; a = b = head; for (int i = 0; i < k; i++) { // 不足 k 个，不需要反转，base case if (b == null) return head; b = b.next; } // 反转前 k 个元素 ListNode newHead = reverse(a, b); // 递归反转后续链表并连接起来 a.next = reverseKGroup(b, k); return newHead; }
如何判断回文链表？一种思路是递归入栈，用后序遍历进行对比：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// 回文链表递归模板 // 左侧指针 ListNode left;
booleanisPalindrome(ListNode head){ left = head; return traverse(head); }
booleantraverse(ListNode right){ if (right == null) returntrue; boolean res = traverse(right.next); // 后序遍历代码 res = res && (right.val == left.val); left = left.next; return res; }
// 字符串乘法模板 stringmultiply(string num1, string num2){ int m = num1.size(), n = num2.size(); // 结果最多为 m + n 位数 vector<int> res(m + n, 0); // 从个位数开始逐位相乘 for (int i = m - 1; i >= 0; i--) for (int j = n - 1; j >= 0; j--) { int mul = (num1[i]-'0') * (num2[j]-'0'); // 乘积在 res 对应的索引位置 int p1 = i + j, p2 = i + j + 1; // 叠加到 res 上 int sum = mul + res[p2]; res[p2] = sum % 10; res[p1] += sum / 10; } // 结果前缀可能存的 0（未使用的位） int i = 0; while (i < res.size() && res[i] == 0) i++; // 将计算结果转化成字符串 string str; for (; i < res.size(); i++) str.push_back('0' + res[i]);
for i in range(1, len(intervals)): curr = intervals[i] # res 中最后一个元素的引用 last = res[-1] if curr[0] <= last[1]: # 找到最大的 end last[1] = max(last[1], curr[1]) else: # 处理下一个待合并区间 res.append(curr) return res
区间合并对于几个相交区间合并后的结果区间 x，x.start 一定是这些相交区间中 start 最小的，x.end 一定是这些相交区间中 end 最大的。
先定下 start ，如果有相交更新 end 位，如果没有相交如数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# 区间交集模板 # A, B 形如 [[0,2],[5,10]...] defintervalIntersection(A, B): i, j = 0, 0# 双指针 res = [] while i < len(A) and j < len(B): a1, a2 = A[i][0], A[i][1] b1, b2 = B[j][0], B[j][1] # 两个区间存在交集 if b2 >= a1 and a2 >= b1: # 计算出交集，加入 res res.append([max(a1, b1), min(a2, b2)]) # 指针前进 if b2 < a2: j += 1 else: i += 1 return res
区间交集同样是规律问题，不存在交集是 b2 < a1 or a2 < b1 因此取反即 b2 >= a1 and a2 >= b1 。
// 第一种写法 voidshuffle(int[] arr){ int n = arr.length(); /******** 区别只有这两行 ********/ for (int i = 0 ; i < n; i++) { // 从 i 到最后随机选一个元素 int rand = randInt(i, n - 1); /*************************/ swap(arr[i], arr[rand]); } }
// 第二种写法 for (int i = 0 ; i < n - 1; i++) int rand = randInt(i, n - 1);
// 第三种写法 for (int i = n - 1 ; i >= 0; i--) int rand = randInt(0, i);
// 第四种写法 for (int i = n - 1 ; i > 0; i--) int rand = randInt(0, i);
publicstaticvoidsort(Comparable[] a){ aux = new Comparable[a.length]; sort(a, 0, a.length - 1); }
privatestaticvoidsort(Comparable[] a, int lo, int hi){ if (lo >= hi) return; int mid = lo + (hi - lo) / 2; sort(a, lo, mid); sort(a, mid + 1, hi); merge(a, lo, mid, hi); }
privatestaticvoidmerge(Comparable[] a, int lo, int mid, int hi){ int i = lo, j = mid + 1; // 对两个归并对象的起点指针 for (int k = lo; k <= hi; k++) aux[k] = a[k]; // 归并前的原始顺序 for (int k = lo; k <= hi; k++) { if (i > mid) { a[k] = aux[j++]; } elseif (j > hi) { a[k] = aux[i++]; } elseif (less(aux[j], aux[i])) { a[k] = aux[j++]; } else { a[k] = aux[i++]; } } }
intmypow(int a, int k){ if (k == 0) return1; a %= base;
if (k % 2 == 1) { // k 是奇数 return (a * mypow(a, k - 1)) % base; } else { // k 是偶数 int sub = mypow(a, k / 2); return (sub * sub) % base; } }
intsuperPow(int a, vector<int>& b){ if (b.empty()) return1; int last = b.back(); b.pop_back();
int part1 = mypow(a, last); int part2 = mypow(superPow(a, b), 10); // 每次乘法都要求模 return (part1 * part2) % base; }
对于数组转数字， a^1564 = a^4 * (a^156)^10 ，这就可以写成递归了。
对于模运算， (a * b) % k = (a % k)(b % k) % k ，将每一步都进行取模，就不会数值越界了。
对于快速幂， a^b = a x a^(b-1) (b 为奇数) || (a^(b/2))^2 (b 为偶数) ，也可以进行递归了。
贪心算法
一种跳跃游戏是判断是否可以达到数组尾部，另一种跳跃游戏是得出到达数组尾部的最小步数。
1 2 3 4 5 6 7 8 9 10 11 12
// 是否达到尾部贪心 boolcanJump(vector<int>& nums){ int n = nums.size(); int farthest = 0; for (int i = 0; i < n - 1; i++) { // 不断计算能跳到的最远距离 farthest = max(farthest, i + nums[i]); // 可能碰到了 0，卡住跳不动了 if (farthest <= i) returnfalse; } return farthest >= n - 1; }
这种非常简单，用一个 farthest 变量就能说明问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 达到尾部最小步数贪心 intjump(vector<int>& nums){ int n = nums.size(); int end = 0, farthest = 0; int jumps = 0; for (int i = 0; i < n - 1; i++) { farthest = max(nums[i] + i, farthest); if (end == i) { jumps++; end = farthest; } } return jumps; }
这个需要一定的思考，时间复杂度 O(N) ，空间复杂度 O(1) ，很强。
i 和 end 标记了可以选择的跳跃步数，farthest 标记了所有选择 [i..end] 中能够跳到的最远距离，jumps 记录了跳跃次数。
// 随机抽出 1 个数模板 /* 返回链表中一个随机节点的值 */ intgetRandom(ListNode head){ Random r = new Random(); int i = 0, res = 0; ListNode p = head; // while 循环遍历链表 while (p != null) { // 生成一个 [0, i) 之间的整数 // 这个整数等于 0 的概率就是 1/i if (r.nextInt(++i) == 0) { res = p.val; } p = p.next; } return res; }
publicintsearch(String txt){ int M = pat.length(); int N = txt.length(); // pat 的初始态为 0 int j = 0; for (int i = 0; i < N; i++) { // 当前是状态 j，遇到字符 txt[i]， // pat 应该转移到哪个状态？ j = dp[j][txt.charAt(i)]; // 如果达到终止态，返回匹配开头的索引 if (j == M) return i - M + 1; } // 没到达终止态，匹配失败 return -1; }
