算法
快来分享你的内容吧～
2 天前·Java后端- 3 天前·Java后端
5 天前·后端开发
6 天前·@编程小助手 微信: leikooo_每周完成一个 ARTS： 至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。查看全文加油鸭：ARTS打卡太扎实了！算法思路清晰、论文解读深刻、技巧实用、分享有洞见——坚持输出就是最硬核的成长！531分享- 6 天前·Java后端
- 10-23 23:36·Java后端
- 10-19 10:59·Java后端啊啊啊啊啊啊！宝宝！你是一个香香软软甜甜糯糯蜂蜜奶油甜甜腻腻酥酥脆脆滑滑嫩嫩绵绵密密蓬蓬松松香香甜甜细细软软酥酥软软的 LRU 缓存！查看全文面试鸭9182：老吴，你个你个你个你个ner～461分享
【数论】求两个正整数的最大公因数与最小公倍数
[B3634 最大公约数和最小公倍数 - 洛谷](https://www.luogu.com.cn/problem/B3634) 概念梳理： - 最大公约数：两个正整数的 `m`、`n` 的**最大公约数（greatest common divisor）** 是指能同时整除 `m` 和 `n` 的最大因子，记为$\gcd(m, n)$。特别地，若 $\gcd(m,n)=1$，则我们称 `m` 和 `n` 互素。 - 最小公倍数：两个正整数 `m`、`n` 的**最小公倍数（least common multiple）** 是指同时被 `m` 和 `n` 整除的最小倍数，记为 $\operatorname{lcm}(m,n)$。 二者存在如下关系： $$ m \times n = \gcd(m,n) \times \operatorname{lcm}(m,n) $$ 求解 $\mathrm{lcm}(m, n)$ 的经典方法是：先求出 $\gcd(m, n)$，再利用公式： $$ \operatorname{lcm}(m,n)=\frac{m \times n}{\gcd(m,n)} $$ 计算得到。 编程实现时需要注意：直接计算 $m \times n$ 可能会导致整数溢出，因此应调整计算顺序，先做除法再做乘法，即： $$ \operatorname{lcm}(m,n)=\frac{m}{\gcd(m,n)} \times n $$ 那 $\gcd(m,n)$ 又该怎么求？一个经典方法是**欧几里得算法（辗转相除法）**。 欧几里得算法基于一个核心结论：**两个正整数的最大公约数，等于较小数与较大数除以较小数所得余数的最大公约数。** 假设 $m \ge n$，上述结论可表示为： $$ \gcd(m,n)=\gcd(n,m\bmod n) $$ 因为 $m\bmod n$ 的结果 $r$ 满足 $0 \le r < n$，所以新问题 $\gcd(n,r)$ 的第二个参数严格小于原来的第二个参数 $n$。因此，**每次迭代都会使问题的规模进一步缩小**。 如此反复操作，直到第二个参数变为 0。此时，问题变为 $\gcd(a,0)$，其中 $a>0$。由于任意正整数都是 0 的因数，因此 $\gcd(a,0)=a$，也就是说，此时的第一个参数就是我们要求的最大公约数。 这里分别给出 `gcd` 方法的递归和迭代实现。考虑到迭代版的空间复杂度更低，后续将优先使用迭代版。 递归版： ```java public int gcd(int m, int n) { if (m < n) { int t = m; m = n; n = t; } if (n == 0) { return m; } return gcd(n, m % n); } ``` 时间复杂度为 $O(\log n)$，其中 $n$ 为两个输入中较小的正整数；空间复杂度为 $O(\log n)$，主要来自递归调用栈。 迭代版： ```java public int gcd(int m, int n) { if (m < n) { int t = m; m = n; n = t; } while (n > 0) { int r = m % n; m = n; n = r; } return m; } ``` 时间复杂度同上，空间复杂度 $O(1)$。 最后，便可以利用最大公约数实现 `lcm` 方法： ```java public long lcm(int m, int n) { return (long) m / gcd(m, n) * n; } ``` > **注意**：这里有两个坑点。 > > 1. 最小公倍数的结果可能超过 `int` 的最大值，因此方法的返回类型必须使用 `long`。 > 2. 计算时需要先将 `m` 转换为 `long`。如果不进行转换，表达式 `m / gcd(m, n) * n` 中的操作数均为 `int` 类型，因此除法和最后的乘法都会以 `int` 类型进行计算，**最后一步乘法可能发生溢出**。表达式计算完成后，Java 才会将最终的 `int` 结果自动转换为 `long` 并返回，但此时溢出已经发生，类型转换也无法挽回已经溢出的结果。
【栈模拟】字符串解码
# 字符串解码 [394. 字符串解码](https://leetcode.cn/problems/decode-string/) 本题是一道**模拟题**。 题目给定一个编码字符串 `s`，要求我们将其解码并返回解码后的字符串。 编码规则为：`k[encoded_string]` 表示将方括号内的 `encoded_string` 重复 `k` 次，其中 `k` 是正整数，`encoded_string` 是需要重复的字符串。**编码字符串可以嵌套**，即 `encoded_string` 内部还可以包含其他编码字符串。 例如： - `3[a]` 解码为 `aaa`。 - `2[abc]` 解码为 `abcabc`。 - `3[a2[c]]` 解码为 `accaccacc`。 此外，题目保证输入中的数字只表示重复次数 `k`，**不会出现 `3a` 或 `2[4]` 这样的输入**。 那么，我们应该如何解码这样的字符串呢？ 对于不包含嵌套结构的编码字符串，例如 `3[a]`，我们只需要将方括号内的字符串 `a` 重复三次，就能得到解码结果 `aaa`。 然而，如果编码字符串包含嵌套结构，例如 `3[a2[c]]`，情况就有所不同了。 在这个例子中，内层的 `2[c]` 需要先解码为 `cc`，然后才能将外层的 `3[a2[c]]` 转换为 `3[acc]`，最终得到 `accaccacc`。 这说明，**当编码字符串存在嵌套时，我们需要先完成内层的解码，再继续处理外层的编码结构。** 以 `3[a2[c]]` 为例，处理内层的 `2[c]` 时，外层的重复次数 `3` 和已有字符串 `a` 还不能用于完成解码，需要等内层解码完成后，才能继续处理外层。 因此，处理内层结构时，我们需要**暂存外层的信息**，等内层解码完成后，再继续处理外层。 那么，外层具体需要暂存哪些信息呢？ 仍以 `3[a2[c]]` 为例，在开始处理内层的 `2[c]` 时，我们需要暂存两项信息： - **重复次数** `3`：内层解码完成后，需要将外层的解码结果重复三次。 - **已有字符串** `a`：内层解码完成后，需要将其解码结果拼接到 `a` 后面。 保存好这两项信息后，我们便可以独立处理内层结构，并在内层解码完成后，利用之前保存的信息继续处理外层。 那么，我们应该如何管理这些暂存的信息呢？ 以 `2[a3[b4[c]]]` 为例，当我们开始处理最外层的 `2[...]` 时，已经知道重复次数为 `2`，但其中的字符串还没有解码完成。接下来遇到 `3[...]`，我们又需要暂时保留这一层的重复次数 `3` 和已有字符串 `a`；继续深入到 `4[c]` 时，也需要保存当前这一层的信息。 可以看到，随着解码过程不断深入，我们需要依次保存各层的信息。而解码时，需要先完成最内层，再逐层向外处理。因此，取出这些信息的顺序，应该与保存顺序相反。 这种信息管理方式恰好符合栈的**后进先出**特性：后保存的信息先取出，先保存的信息后取出。因此，我们可以使用栈来保存各层尚未处理完毕的信息。 这种暂存当前状态、处理内层问题、再恢复外层状态的过程，是不是与函数调用栈有些相似呢？ 明确了使用栈保存外层信息后，我们再来看如何遍历字符串，并完成解码。 遍历过程中，我们需要维护两个状态： - `repeatCount`：记录当前正在解析的重复次数。 - `curString`：记录当前正在构建的字符串。 然后，根据遍历到的字符类型，分别进行处理： - 当遇到数字时，我们需要计算当前的重复次数。由于重复次数可能包含多位数字，因此需要逐位累积。 - 当遇到字母时，直接将其追加到 `curString` 中。 - 当遇到左方括号 `[` 时，说明即将进入内层结构。此时，我们需要将当前的重复次数和已经构建好的字符串保存到栈中，然后重置这两个状态，以便独立处理内层字符串。 - 当遇到右方括号 `]` 时，说明当前层的解码已经完成。此时，我们从栈中取出之前保存的外层信息，将当前字符串重复指定次数，并拼接到外层已有的字符串后面，得到新的当前字符串。 基于以上思路，我们可以写出以下代码： ```java public String decodeString(String s) { Deque<State> stack = new ArrayDeque<>(); StringBuilder curString = new StringBuilder(); int repeatCount = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (Character.isDigit(c)) { repeatCount = repeatCount * 10 + (c - '0'); } else if (Character.isLetter(c)) { curString.append(c); } else if (c == '[') { // 保存外层状态 stack.push(new State(repeatCount, curString.toString())); // 重置状态，开始处理内层 repeatCount = 0; curString.setLength(0); } else { // 取出外层状态 State state = stack.pop(); // 将内层解码结果重复指定次数，并拼接到外层字符串后面 String innerString = curString.toString(); curString.setLength(0); curString.append(state.outerString); for (int j = 0; j < state.repeatCount; j++) { curString.append(innerString); } } } return curString.toString(); } static class State { int repeatCount; String outerString; public State(int repeatCount, String outerString) { this.repeatCount = repeatCount; this.outerString = outerString; } } ``` 本题也可以使用递归实现。有兴趣的读者可以尝试从递归的角度思考，如何处理嵌套的编码结构。
米哈游内推～游戏AI算法实习｜强化学习方向
工作地点在上海、北京，校园实习岗位，具体JD可以看下文～ 岗位：游戏AI算法实习生 工作职责 研究复杂游戏场景中的强化学习Agent，探索大模型与强化学习融合，参与分布式强化学习框架、推理加速及知识蒸馏。 任职要求 1、计算机、人工智能、数学、统计学等相关专业硕士及以上学历 2、在深度学习、强化学习或LLM、VLA领域有扎实研究基础 3、熟练PyTorch/TensorFlow，精通Python/C++ 4、具备算法实现与大规模工程落地能力 5、对游戏和AI有自驱力，具备逻辑推演、协作和责任心 优先／加分项 博士优先；相关顶会论文优先。 官网说明：表现优异有转正的机会。 官方岗位及内推入口： https://jobs.mihoyo.com?isRecommendation=true&recommendationCode=606VG#/campus/position/9362 校招入口内推码：606VG 有任何问题欢迎留言咨询哈～ 
【单调栈】每日温度
## 每日温度 [739. 每日温度](https://leetcode.cn/problems/daily-temperatures/) 题目给定每日气温数组 `temperatures`，求每一天距离下一次出现更高气温需要等待的天数，记为 `answer[i]`。如果之后气温都不会升高，则对应位置填 `0`。 一个较为容易想到的直观解法是： 对于每个位置 `i`，从 `i + 1` 开始向右寻找，直到找到第一个比 `temperatures[i]` 更高的气温。 如果找到了，记录两个位置之间的距离；如果遍历到了数组末尾还没有找到，就记录 `0`。 基于这一思路可以写出代码： ```java public int[] dailyTemperatures(int[] temperatures) { int[] answer = new int[temperatures.length]; for (int i = 0; i < temperatures.length; i++) { int nextIndex; for (nextIndex = i + 1; nextIndex < temperatures.length; nextIndex++) { if (temperatures[i] < temperatures[nextIndex]) { break; } } answer[i] = nextIndex < temperatures.length ? nextIndex - i : 0; } return answer; } ``` 这种解法在最坏情况下，例如气温一直递减，**每个位置都可能需要向右遍历很长一段距离**，因此时间复杂度为 $O(n^2 )$，其中 $n$ 为数组长度。 这一暴力解法的思路很直观，但是对于每个位置，我们都需要独立地向右查找，可能存在重复遍历。 那么，能否在遍历气温数组的过程中，利用已经遍历过的信息，减少重复计算，从而提高算法的效率呢？ 我们先来看一个简单的例子： ```java temperatures = [73, 71, 69, 72] ``` 对于气温 `73`，向右查找后发现没有更高的气温，因此答案为 `0`。 对于气温 `71`，需要经过 `69`，才能找到更高的气温 `72`，因此答案为 `2`。 对于气温 `69`，同样需要向右查找，才能找到气温 `72`，因此答案为 `1`。 我们注意到，**气温 `72` 不仅是 `69` 的答案，也是 `71` 的答案**。 那么，当我们遍历到 `72` 时，**能否利用它，同时处理前面多个位置的「下一个更大元素」问题，而不必针对每个位置独立地向右查找**？ 为此，我们可以换一种思路：不再针对每个气温向右寻找答案，而是从左向右遍历，让当前气温主动去解决前面尚未找到答案的元素。 具体来说，我们可以维护一个集合，记录那些**尚未找到更高气温的元素**。 当遍历到一个新气温时，检查集合中的元素，**如果某个元素的气温低于当前气温，那么当前气温就找到了它的答案，我们便可以将它移出集合**。 那么，应该**如何组织这些尚未找到答案的元素，才能快速判断哪些元素可以由当前气温解决呢**？ 观察前面的例子，候选气温依次为 `73、71、69`，它们是降序排列的。因此，我们可以**优先检查最后加入的元素**。 当遇到 `72` 时，它比 `69` 大，因此可以确定 `69` 的答案，并将其移出集合。接着检查 `71`，发现 `72` 同样比它大，于是也可以将其移出集合。 由此，我们可以**让候选元素始终按照气温从高到低排列**。每当遇到新的气温，就从最后一个候选元素开始，不断移除气温低于当前气温的元素。 **对于每一个被移除的元素，当前气温就是它所等待的下一次更高气温，因此可以直接确定它的答案。** 重复这一过程，直到遇到一个气温不低于当前气温的元素，或者集合为空。 最后，将当前气温加入集合，作为一个尚未找到答案的新候选元素。 观察上述操作，我们只需要**在集合的一端添加和移除元素**。因此，可以使用**栈**来存储这些尚未找到答案的候选元素。 由于栈内的元素从栈底到栈顶按照气温从高到低排列，因此这个栈具有单调性，这样的栈称为**单调栈（monotonic stack）**。 在本题中，我们维护的是一个**单调递减栈**：栈中的元素从栈底到栈顶按照气温从高到低排列，栈顶元素就是最后加入的候选元素。 基于这一思路，我们可以写出如下代码： ```java public int[] dailyTemperatures(int[] temperatures) { // 对于本题，我们在单调栈中存储的是尚未找到更高气温的元素下标 Deque<Integer> stack = new ArrayDeque<>(); int[] answer = new int[temperatures.length]; for (int i = 0; i < temperatures.length; i++) { // 当前气温更高，说明栈顶元素找到了下一个更高气温 while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int j = stack.pop(); answer[j] = i - j; } stack.push(i); } return answer; } ``` 复杂度分析： - 时间复杂度为 $O(n)$：虽然代码中有嵌套的 `while` 循环，但每个元素最多入栈、出栈一次。因此，总体时间复杂度为 $O(n)$。 - 空间复杂度为 $O(n)$：不计入答案数组所需的空间，单调栈最多存储 $n$ 个元素。 实际上，本题是一个经典问题——**下一个更大元素（Next Greater Element）问题**的变体。 原问题描述的是：对于数组中的每个元素，我们需要找到其右侧第一个比它更大的元素。而本题则是要求我们计算二者之间的距离。 类似地，如果将条件改为寻找右侧第一个更小的元素，就得到了**下一个更小元素（Next Smaller Element）问题**。如果改变查找方向，还可以研究左侧第一个更大或更小的元素。 这类问题统称为**最近更大/更小元素问题**。当题目要求寻找每个元素左侧或右侧第一个更大或更小的元素时，可以考虑使用单调栈，通过**空间换时间**，将时间复杂度优化到 $O(n)$。
ARTS 1025: 唯一字符与同构字符串、省词可能增加阅读负担与重新估算软件的实现成本
每周完成一个 ARTS： 至少做一个 leetcode 的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的技术文章。（也就是 Algorithm、Review、Tips、Share 简称 ARTS） ## Algorithm 这周因为都是简单难度的，所以来写两道算法题目： 1）第一道：LeetCode [387. 字符串中的第一个唯一字符](https://leetcode.cn/problems/first-unique-character-in-a-string/)  这道题目住要的办法就是，先用 Map 拿到每一个 Charecter 出现的次数，然后根据 map 记录的内容进行返回 index。这有一点需要注意：HashMap 不保证元素的遍历顺序与插入顺序一致。如果需要按照插入顺序遍历元素，可以使用 LinkedHashMap ```java class Solution { public int firstUniqChar(String s) { Map<Character, Integer> map = new HashMap<>(); char[] chars = s.toCharArray(); for (char c : chars) { map.merge(c, 1, Integer::sum); } for (int i = 0; i < chars.length; i++) { if (map.getOrDefault(chars[i], null) == null || map.get(chars[i]) > 1) { continue; } return i; } return -1; } } ``` 2）第二道：LeetCode [205. 同构字符串](https://leetcode.cn/problems/isomorphic-strings/)  有几点需要注意： + 错误把“出现次数相同”当成了“同构”。不能只是单纯的判断，字母出现的数量进行对比。 + 只检查了映射的一致性，漏掉了映射的唯一性。如果一个 a -> b a -> a 这样也不是同构的，所以这里我们使用 Set 进行判断。 ```java class Solution { public boolean isIsomorphic(String s, String t) { if (s.length() != t.length()) { return false; } Map<Character, Character> charMap = new HashMap<>(); Set<Character> usedTargets = new HashSet<>(); for (int i = 0; i < s.length(); i++) { char sC = s.charAt(i); char tC = t.charAt(i); Character mapped = charMap.get(sC); if (mapped == null) { // tC 已经被其他字符使用，不能重复映射 if (!usedTargets.add(tC)) { return false; } charMap.put(sC, tC); } else if (mapped != tC) { return false; } } return true; } } ``` ## Review 论文：[Why is AI-generated language so hard to understand?](https://arxiv.org/html/2610.29162v1) 作者提出一个假说：训练中压缩信息的压力，可能让模型更偏爱紧凑、省词的表达。这些表达在语法上说得通，却可能让读者花更多精力判断词义、记住前文、补出句子里的关系。 1、阅读时，读者需要不断预测后文、记住前文。 看到一个词时，读者已经在结合上下文判断它的意思。论文引用的心理语言学研究发现，越难预测的词，通常需要越长的阅读时间。词语搭配不常见，读者就更难顺着前文理解下去。 记忆也会影响阅读。如果主语和对应的动词隔得很远，读到动词时，就得找回前面的主语，再把两者联系起来。相互关联的词之间隔了多远，称为「依存距离」。一句话里需要暂时记住的信息越多，理解起来就越费力。所以，判断句子是否好读，不能只看字数，还要看读到哪里才能确定它在说什么。 2、论文检查了六类可能增加阅读负担的表达。 下面结合例子说明，其中的中文例子是为帮助理解补充的。 罕见的词语搭配，可能让人每个词都认识，连起来却不熟悉。例如，论文开头的 `reader-patience budget`，字面上是「读者耐心预算」。读者需要先理解这里把耐心比作一种会被消耗的预算，才能明白整个词组。写成「读者愿意花多少耐心读下去」，含义就直接一些。 长距离依存，会让读者更久地记住还没读完整的内容。例如，「负责处理缓存失效后大量请求同时访问数据库问题的服务需要重启」，读到「服务」时，才知道前面一大段都在修饰它，接着还得把它和「需要重启」联系起来。可以拆成：「这个服务负责处理缓存失效后大量请求同时访问数据库的问题。现在需要重启它。」先交代服务的用途，再说要做什么，读者就不用把整串修饰语一直记到句尾。 宾语关系从句中的省略，可能让句子少一些结构提示。例如，`The patch the engineer reviewed failed.` 的意思是「工程师审查过的补丁失败了」。句子的主干是 `The patch failed.`，中间的从句说明补丁被谁审查过，`the patch` 是 `reviewed` 的宾语。写成 `The patch that the engineer reviewed failed.`，多出的 `that` 标出了从句的开始。省去它也符合语法，但读者需要更依赖后文来判断结构。相关研究发现，人类会根据后续内容是否容易预测，决定要不要省略这类词。 名词堆叠，会省去概念之间的关系。例如，「缓存失效回源并发保护策略」把几个概念连在一起，读者需要自己判断哪些是条件、动作和目的。可以展开成：「缓存失效后，请求会访问数据库。为避免大量请求同时回源，可以限制同时回源的请求数。」多出来的文字，把原来需要读者推断的关系写了出来。 名词转动词，也能把原本需要几个词说明的动作缩短。例如，把表示日历的 `calendar` 当作动词，就可以表达「把某件事记入日历」。这类用法依赖说话者和读者对情境的共同理解。如果上下文不够充分，读者就得先猜这个词在当前句子里指什么动作。 还有一类是让没有生命的事物去做通常由人或动物完成的动作。例如，论文中的 `this asymmetry bites`，需要把「咬」理解成「造成问题」。在技术说明中，仅写「这个不对称性会反咬一口」，读者还得继续追问它具体影响什么。直接说明它会导致什么错误，更方便判断影响范围。名词转动词和拟人表达都可以正常使用，是否难读，还取决于读者对这种用法的熟悉程度，以及上下文是否充分。 3、训练目标可能强化了这些表达偏好。 作者推测，数学、代码等后训练任务可以奖励答案正确，却未必奖励读者是否容易理解。再加上上下文长度和 token 成本的限制，模型可能逐渐偏向用更少的词表达更多信息。 放到文档里看，省掉连接词、把动作写成名词、把背景放进一长串修饰语，确实可能缩短输出。但条件和因果关系不会因此消失，它们只是需要读者自己还原。对模型来说省下了词，对读者来说却可能多了一步推断。 人类的表达会随语境调整：容易预测的内容可以省略，新信息多的地方则需要更多提示。前面是否保留 `that` 的例子，就说明了这种取舍。**省略是否合适，要看读者能不能顺着上下文理解下去。** 对我们的启发就是，在写技术笔记时，可以留意那些需要读者自己补全的地方：主语是否明确，修饰语能否拆开，几个名词之间是什么关系，隐喻具体指什么行为和结果。让 AI 润色时，也可以要求保留条件和因果关系，再根据读者已有的知识，决定哪些内容可以省略。 ## Tips 1、macOS 使用 FineTune 可以管理不同软件得声音，非常实用。开源地址： https://github.com/ronitsingh10/FineTune 2、epub 阅读器，可以使用这个开源项目：https://github.com/readest/readest 3、继续学习 Rust 相关的内容，学到 [ Lifetimes](https://doc.rust-lang.org/book/ch10-03-lifetime-syntax.html#validating-references-with-lifetimes) 了，继续冲 ## Share 文章：[We should be more ambitious with the software we build](https://danluu.com/ambitious/) Dan Luu 提出了一个值得重新考虑的问题：有了 AI 编程工具之后，哪些过去因为成本太高而放弃的事情，现在已经值得做了？他更倾向于说「可以更有野心」，因为工具能力的变化，让开发者有机会尝试以前做不起的软件。 1、判断一个项目值不值得做，需要重新估算实现成本。 过去，嫌编译慢就自己改编译器，嫌搜索慢就自己写正则引擎，通常意味着投入大量时间，还可能耽误原本要完成的工作。因此，优先使用现成工具、避免重复造轮子，是很合理的选择。 但 Dan Luu 发现，有些判断已经需要更新。他针对自己的使用场景，尝试了正则引擎、ripgrep 分支和 Rust 编译加速等项目，投入的个人时间比过去少了很多。开发者可能还沿用着没有编程 Agent 时的成本估计，连试一下都觉得不划算。 这里也要保留作者给出的范围：这些工具主要达到了「自己能用」的程度，做成可靠的公共项目仍然需要更多工作，文中也没有提供完整、严谨的性能评测。这些经历更适合用来说明尝试的成本发生了变化，具体收益还要在实际场景中测量。 2、值得尝试的软件，也可以只解决一个很小的需求。 文章中有个例子很有意思：Dan Luu 一直想玩一款还原小说中太空战斗方式的游戏，但这种玩法很小众。过去，花十几个小时开发，再玩一两个小时，并不划算；当他只需要花几分钟安排 Agent 实现时，这件事就值得做了。 这种变化也适用于日常工具。比如，一个脚本只能省下每次几分钟的手动操作，过去因为开发和维护太麻烦，一直没有人写。现在可以先做一个范围很小的版本，用几次看看是否方便，再决定要不要继续完善。软件只供几个人使用，也可能有足够的价值。 3、项目能做得更大，验证也得跟得上。 Dan Luu 用 pgrust 数据库项目说明，有质量问题的 AI 项目很多，但认真测试的项目仍然能产生价值。按他的介绍，pgrust 的测试过程甚至找出了 PostgreSQL 本身的 Bug，即使这个项目最终没有成功，这些发现也能帮助已有软件改进。 不过，作者并没有得出「软件开发已经解决了」的结论。他发现，模型能实现的东西越来越多，但在缺少人工指导时，能够有效验证的范围没有同步跟上。尝试更复杂的项目之后，人仍然需要判断实现是否符合预期。
【单调队列】滑动窗口最大值
[239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/) 题目要求我们求出固定长度为 `k` 的滑动窗口从左向右滑动过程中，每个位置对应的窗口最大值。例如： ``` 滑动窗口的位置 | 最大值 ------------------------------------- [1 3 -1] -3 5 3 6 7 | 3 1 [3 -1 -3] 5 3 6 7 | 3 1 3 [-1 -3 5] 3 6 7 | 5 1 3 -1 [-3 5 3] 6 7 | 5 1 3 -1 -3 [5 3 6] 7 | 6 1 3 -1 -3 5 [3 6 7] | 7 ``` 接下来，**如何求出窗口内的最大值呢**？一个直观的想法是：每次都遍历窗口内的所有元素，找出最大值。 然而，这种做法效率较低。因为窗口每次向右移动一格时，只会有一个元素移出窗口、一个新元素进入窗口，有不少旧元素是重叠的。每次重新遍历整个窗口，都会**重复计算这些重叠元素**。 因此，这种做法的时间复杂度为 $O(nk)$，其中，$n$ 是数组 `nums` 的长度，$k$ 是滑动窗口的长度。 那么，我们能否在窗口滑动的过程中，维护一些有用的信息，使得我们不必每次都重新遍历整个窗口？ 一个自然的想法是，我们可以尝试记录上一个窗口的最大值。然而，当上一个窗口的最大值离开窗口时，我们仍然需要重新遍历窗口内的剩余元素，才能找到新的最大值。因此，仅仅记录最大值是不够的。 那么，能否**在记录最大值的同时，也记录其他可能成为最大值的元素**？这样，当最大值离开窗口时，我们就有机会直接从这些元素中找到新的最大值，而不必重新遍历整个窗口。 不过，**窗口内的所有元素都有必要记录下来吗**？ 我们可以先考虑这样一种情况：如果一个新进入窗口的元素，它比窗口中某个先进入的元素更大，那么后者还有可能成为窗口的最大值吗？ 举个例子，假设窗口中有一个元素 `3`，现在又有一个更大的元素 `5` 进入窗口。由于窗口始终向右滑动，后进入的 `5` 一定比先进入的 `3` 更晚离开窗口。既然 `5` 更大，那么 `3` 就不可能再成为窗口的最大值，可以将其排除。 更进一步，如果新进入窗口的元素比前面多个元素都大，那么这些元素也都可以排除。因为它们比新元素小，并且会比新元素更早离开窗口，因此不可能再成为窗口的最大值。 这样，我们就**不必记录窗口内的所有元素，只需要保留那些仍有可能成为最大值的元素**。 既然只需要保留候选元素，我们应该按照什么顺序组织它们，才能快速找到最大值？ 我们可以让候选元素按照从大到小的顺序排列。这样，每次只需要查看第一个元素，就能得到当前窗口的最大值。 那么，当一个新元素进入窗口时，应该如何维护候选元素的排列顺序呢？ 我们可以从候选元素的末尾开始，将新元素与末尾元素进行比较。如果新元素更大，就移除末尾元素，并继续比较；直到末尾元素不再比新元素小，或者候选元素为空，再将新元素加入末尾。 例如，已有候选元素 `6、4、3、2`，现在新进入一个元素 `5`。由于 `5` 比 `4、3、2` 都大，因此这三个元素都可以排除。将 `5` 加入后，候选元素变为 `6、5`，仍然保持从大到小的顺序。 接下来，还需要考虑窗口向右移动时，如何处理离开窗口的元素。 我们前面已经规定，候选元素从大到小排列。因此，当窗口最左边的元素离开时，我们只需要判断它是不是候选集合中的最大值。如果是，就移除候选集合中的第一个元素；否则，不需要处理。 观察上述操作，我们需要从末尾移除元素、从末尾添加元素、从开头移除元素，同时还需要快速访问第一个元素。因此，可以使用**双端队列（deque）**来存储候选元素。 由于我们始终维护候选元素从大到小的排列顺序，因此这个队列具有单调性。这样的队列称为**单调队列（monotonic queue）**。 在本题中，我们维护的是一个单调递减队列：队列中的元素从队首到队尾单调递减，队头元素就是当前候选元素中的最大值。 基于这一思路，我们可以写出如下代码： ```java public int[] maxSlidingWindow(int[] nums, int k) { List<Integer> res = new ArrayList<>(); // 窗口表示为左闭右开区间 [l, r) int l = 0, r = 0; Deque<Integer> q = new ArrayDeque<>(); while (r < nums.length) { int cur = nums[r++]; // 新元素进入时，从队尾移除比它小的候选元素，再将新元素加入队尾。 while (!q.isEmpty() && cur > q.peekLast()) { q.removeLast(); } q.addLast(cur); if (r - l == k) { // 窗口形成后，记录队头元素作为当前窗口的最大值。 res.add(q.peekFirst()); // 移除窗口最左侧的元素；如果它等于队头元素，则同时移除队头。 int removed = nums[l++]; if (removed == q.peekFirst()) { q.removeFirst(); } } } return res.stream() .mapToInt(Integer::intValue) .toArray(); } ``` 复杂度分析： - 时间复杂度为 $O(n)$：虽然代码中有嵌套的 `while` 循环，但**每个元素最多入队一次，也最多从队尾或队头移除一次**。因此，所有元素在队列上的操作总次数为 \(O(n)\)，整体时间复杂度为 \(O(n)\)。 - 空间复杂度为 $O(k)$：不计存储结果数组 `res` 所需的空间，额外空间主要由双端队列 `q` 占用。队列中最多保存当前窗口内的候选元素，因此最多存储 \(k\) 个元素，空间复杂度为 \(O(k)\)。
【模拟】相交链表
[160. 相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/) 对于如图所示的两个链表 `A`、`B`，标红节点就是我们要找的交点：  如果暂时不考虑题目的约束——函数返回后，链表必须保持原始结构。 我们可以尝试将本题与「环形链表 II」联系起来。 假设两个链表存在公共部分，我们将公共部分的尾节点指向链表 A 的头节点，就可以构造出一个环。  此时，从链表 B 的头节点出发，沿着 B 的独有部分进入环，环的入口恰好就是两个链表的第一个公共节点。因此，我们可以借助「环形链表 II」的思路寻找交点。 不过，这种方法需要修改链表结构，而且还需要额外处理两个链表原本就不相交的情况，因此不适合作为本题的直接解法。 那么，有没有不修改链表结构，也能找到交点的方法呢？ 一个可行的方案是**交叉遍历**。 我们使用两个指针 `pA`、`pB`，分别从链表 A、B 的头节点出发，每次各向后移动一个节点。 当某个指针到达 `null` 时，就让它从另一条链表的头节点重新出发。另一个指针同理。 当 `pA == pB` 时，遍历结束： - 如果两个链表相交，两个指针最终会在第一个公共节点处相遇。 - 如果两个链表不相交，两个指针最终都会到达 `null`。 为什么交叉遍历是正确的？我们来推导一下这一思路背后的数学原理。 设 A 独有部分长度为 $a$，B 独有部分长度为 $b$，公共部分长度为 $c$（不相交时 $c = 0$）。 那么： - 链表 A 的长度为 $a+c$。 - 链表 B 的长度为 $b+c$。 如果两个链表相交，`pA` 从 A 的头节点出发，遍历完 A 后切换到 B，最终到达交点，走过的路程为： $$ (a+c)+b=a+b+c $$ 同理，`pB` 从 B 的头节点出发，遍历完 B 后切换到 A，最终到达交点，走过的路程为： $$ (b+c)+a = a + b + c $$ 我们发现，二者到达交点前的路程是一样的： $$ (a+c)+b = (b+c)+a=a+b+c $$ 这说明，**两个指针到达第一个公共节点前，走过的路程相同**。由于二者每次都移动一个节点，因此最终会在该节点相遇。 如果两个链表不相交，那么 \(c=0\)。此时，两个指针分别遍历完 A、B 两条链表，再遍历另一条链表，最终都会到达 `null`。 由此可见，无论两个链表是否相交，交叉遍历都能保证两个指针最终相遇。 基于这一思路，我们不难写出如下代码： ```java public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p = headA, q = headB; while (p != q) { p = p == null ? headB : p.next; q = q == null ? headA : q.next; } return p; } ```
【哈希】字母异位词
## 有效的字母异位词 [242. 有效的字母异位词](https://leetcode.cn/problems/valid-anagram/) 给了两个单词 `s` 和 `t`，要判断它们是不是字母异位词。 所谓字母异位词是指由**相同种类和数目**的字母组合而成的单词，例如这一对组合：`"anagram" ` 与 `"nagaram"`。 一个直观的思路是对字符串内部字符按照字典序排序。若两字符串排序结果相同，则说明它们是异位词。 然而，对字符串内部的字符进行排序，通常需要 $O(n\log n)$ 的时间复杂度。其实还有更好的 $O(n)$ 解法——统计单词的字符频率。 我们使用计数器 `counter` 来统计 `s` 的字符频率。 遍历 `t` 时，我们对 `counter` 进行相反的操作，即将对应字符的计数减一。 最终，若计数器中的所有计数都归零，则 `s` 和 `t` 就是一组字母异位词。 基于这一思路，不难写出代码： ```java public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } // 由于题目保证单词仅由小写字母构成，因此用数组来模拟 Map<Character, Integer>。 int[] counter = new int[26]; for (int i = 0; i < s.length(); i++) { counter[s.charAt(i) - 'a']++; } for (int i = 0; i < t.length(); i++) { counter[t.charAt(i) - 'a']--; } for (int count : counter) { if (count != 0) { return false; } } return true; } ``` ## 字母异位词分组 [49. 字母异位词分组](https://leetcode.cn/problems/group-anagrams/) 题目给我们一个仅有小写字母构成的单词数组 `strs`，并要求我们将字母异位词组合在一起。 显然，我们要将这些单词按照**是否为同一类字母异位词**这一标准进行分组。那么这个标准要如何表示呢？ 一个较为直接的想法是对每个单词内部的字符按照字典序排序。若两个单词属于同一类字母异位词，则它们排序后的结果一定相同。因此，我们可以将排序后的字符串作为 key，将对应的单词列表作为 value。 除此之外，还有时间复杂度更优的方案，即继续利用字符频率。 这里有一个难点，我们怎么用字符频率构建标准呢？ 我的想法是利用 `counter` 构造一个压缩后的字符串表示：按照字典序依次记录每个出现过的字符及其频率。例如，`"nagaram"` 可以被压缩表示为 `"a3g1n1r1"`。 属于同一类字母异位词的单词，其字符频率完全相同，因此一定可以得到相同的字符串表示。这样，我们就可以将这个字符串作为 key。 基于这一思路，不难写出如下代码： ```java public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> group = new HashMap<>(); for (String str : strs) { String key = buildFrequencyKey(str); group.computeIfAbsent(key, s -> new ArrayList<>()) .add(str); } return new ArrayList<>(group.values()); } private String buildFrequencyKey(String str) { if (str.isEmpty()) { return str; } StringBuilder res = new StringBuilder(); int[] counter = new int[26]; for (int i = 0; i < str.length(); i++) { counter[str.charAt(i) - 'a']++; } for (int i = 0; i < counter.length; i++) { if (counter[i] > 0) { res.append((char)(i + 'a')); res.append(counter[i]); } } return res.toString(); } ```
【二分】搜索二维矩阵 Ⅱ
[240. 搜索二维矩阵 II](https://leetcode.cn/problems/search-a-2d-matrix-ii/) 矩阵中的元素具有以下特性： - 每行元素从左到右按升序排列； - 每列元素从上到下按升序排列。 那我们如何利用这样的有序性高效查找 `target` 呢？ 为了利用矩阵的有序性缩小搜索范围，我们希望每次比较当前元素与 `target` 后，都能**排除一部分不可能包含目标值的区域**。 观察矩阵的四个角，可以发现，左上角的元素是整个矩阵的最小值，右下角的元素是整个矩阵的最大值。 结合矩阵的行、列有序性，我们可以进一步观察**右上角和左下角**这两个位置。以右上角为例，可以发现，该位置的元素是**所在行的最大值，同时也是所在列的最小值**。 我们记右上角元素为 `cur`： - 当 `cur < target` 时，由于 `cur` 是所在行的最大值，该行所有元素都小于 `target`，因此可以排除当前行。 - 当 `cur > target` 时，由于 `cur` 是所在列的最小值，该列所有元素都大于 `target`，因此可以排除当前列。 - 当 `cur == target` 时，说明找到了目标值，直接返回 `true`。 因此，从右上角开始搜索，就可以根据每次比较的结果，不断缩小搜索范围。排除一行或一列后，剩余区域仍然保持每行、每列有序的性质，因此可以继续按照上述方法搜索。 同理，左下角也具有类似的性质，因此也可以作为搜索起点。这里选择右上角进行说明。 我们从右上角出发，并使用变量 `top` 和 `right` 分别维护当前搜索区域的上边界和右边界。 每次比较后，根据上述规则移动对应边界，逐步缩小搜索范围。当搜索区域为空时，说明 `target` 不在矩阵中，返回 `false`。 基于这一思路，可写出如下代码： ```java public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int top = 0, right = n - 1; while (top < m && right >= 0) { int cur = matrix[top][right]; if (cur == target) { return true; } else if (cur > target) { right--; } else { top++; } } return false; } ``` 复杂度分析: - 时间复杂度：$O(m+n)$。每次循环都会排除一整行或一整列，`top` 最多增加 $m$ 次，`right` 最多减小 $n$ 次。 - 空间复杂度：$O(1)$。只使用了常数个额外变量。
【模拟】LRU 缓存
[146. LRU 缓存](https://leetcode.cn/problems/lru-cache/) > 本题也是面试时的高频考点，需要重点掌握。 什么是 LRU 缓存淘汰算法？ **LRU（Least Recently Used，最近最少使用）** 是一种缓存淘汰算法。当缓存空间已满，需要存入新数据时，就淘汰最近最少使用的数据，也就是最久没有被访问过的数据。 举个生活中的例子：假如你的书桌只能放 5 本书，每次阅读一本书后，就把它放到最顺手的位置。当书桌放满，需要放入一本新书时，就把最久没有翻阅过的那本书收进书架。这就是 LRU 算法的核心思想。 本题要求 `get`、`put` 操作必须以 $O(1)$ 的平均时间复杂度运行，所以很容易想到应该使用哈希表来存储数据。 然而，哈希表本身无法维护数据的访问顺序，因此还需要借助另外一个辅助数据结构——双向链表。 > 之所以选择双向链表而非单链表，是因为本题需要频繁移动已有节点。移动节点时，需要先将其从当前位置删除，再插入链表头部。双向链表的节点同时保存了前驱和后继指针，因此可以在$O(1)$的时间复杂度内找到节点的前驱节点，从而完成删除操作；而单链表无法直接找到前驱节点，通常需要从链表头部遍历查找。因此，双向链表更适合本题的需求。 我们规定：最近使用的数据排在链表最前面，最久未使用的数据排在链表最后面。 为了简化链表操作，我们设置虚拟头节点 `head` 和虚拟尾节点 `tail`，所有真实节点都位于两者之间。插入新节点或访问已有节点时，将其放到 `head` 之后；缓存已满时，删除 `tail` 之前的真实节点。 接下来，实现 `get` 和 `put` 两个操作。 对于 `get` 操作，先通过哈希表查找对应的节点。如果节点不存在，返回 `-1`；如果节点存在，将其移动到链表头部，再返回节点中保存的值。 对于 `put` 操作，先判断 `key` 是否存在。如果存在，更新节点的值，并将其移动到链表头部；如果不存在，则先判断缓存是否已满。若缓存已满，删除链表尾部的真实节点，并将其对应的 `key` 从哈希表中移除。然后创建新节点，将其插入链表头部，并在哈希表中记录 `key` 与节点的对应关系。 这里有一个细节需要注意：链表节点不仅要保存 `value`，还要保存 `key`。因为淘汰节点时，需要根据节点的 `key` 删除哈希表中的对应记录，保证哈希表和链表中的数据始终一致。 最后，我们将双向链表的操作封装成三个辅助方法。`removeNode` 用于删除指定节点，`addNode` 用于将节点插入虚拟头节点之后，`moveNodeToHead` 则通过先删除、再插入的方式，将已有节点移动到链表头部。 实现时，建议先写好双向链表的插入、删除和移动操作，再实现 `get` 和 `put`。动手编码前，先理清每个操作对哈希表和链表的影响，可以有效避免逻辑混乱。 参考代码： ``` java class LRUCache { private final int capacity; private final Map<Integer, Node> map; private final Node head; private final Node tail; public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); Node head = new Node(-1, -1); Node tail = new Node(-1, -1); head.next = tail; tail.pre = head; this.head = head; this.tail = tail; } public int get(int key) { Node node = map.get(key); if (node == null) { return -1; } moveNodeToHead(node); return node.data; } public void put(int key, int value) { Node node = map.get(key); if (node == null) { // 新的键值对 if (map.size() == capacity) { Node removed = tail.pre; removeNode(removed); map.remove(removed.key); } node = new Node(key, value); addNode(node); } else { // 更新旧的键值对 node.data = value; moveNodeToHead(node); } map.put(key, node); } private void removeNode(Node node) { node.pre.next = node.next; node.next.pre = node.pre; } private void moveNodeToHead(Node node) { removeNode(node); addNode(node); } private void addNode(Node node) { node.next = head.next; head.next.pre = node; node.pre = head; head.next = node; } static class Node { int key; int data; Node pre; Node next; public Node(int key, int data) { this.key = key; this.data = data; } } } ```