跳跃问题、迷宫问题和设计问题
好的，今天我们来聊一聊算法题里非常经典的三大类问题：跳跃问题、迷宫问题和设计问题。这几类问题在面试里出镜率极高，而且花样繁多，但万变不离其宗。咱们就用左老师的风格，从最暴力的方法开始，一步步把思路理清，看看怎么把一个问题分析透彻，最终找到最优解。
第 23 章 跳跃问题
跳跃问题，本质上是在一个一维数组上移动，问你能否到达、最少几步到达，或者有多少种方式到达。这类问题的核心，在于定义清楚“状态”。我们通常会定义 dp[i] 表示从位置 i 出发，能得到什么样的答案。
23.2.1 跳跃游戏 II (LeetCode 45)
给你一个非负整数数组
nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总可以到达数组的最后一个位置。
我的思路：
一看到“最少次数”，第一反应就是广度优先搜索（BFS），但那是图论。在数组上，更直观的是动态规划。
解法一：暴力递归
我们想知道从位置0跳到结尾最少需要几步。这不就是一个递归过程吗？假设我站在位置 i，我能跳到 i+1, i+2, ..., i+nums[i] 这些位置。那么，从 i 出发到终点的最少步数，就是 1 + min(从i+1到终点的最少步数, 从i+2到终点的最少步数, ...)。
这就是一个标准的从右往左的动态规划模型，或者说，一个从左往右的递归。我们定义一个函数 process(i)，表示从位置 i 跳到最后一个位置 n-1，最少需要几步。
Base Case: 如果
i >= n-1，说明已经到了或者越过了，不用再跳了，返回0。递归过程: 在
i位置，我能跳nums[i]步。我可以选择跳1步、2步、...、nums[i]步。我把所有这些选择都试一遍，取一个最小值。process(i) = 1 + min(process(i+1), process(i+2), ..., process(i+nums[i]))
// LeetCode 45. 跳跃游戏 II
// 解法一：暴力递归（会超时）
public int jump_v1(int[] nums) {
return process(nums, 0);
}
private int process(int[] nums, int i) {
// 如果已经到达或越过终点，不需要再跳了
if (i >= nums.length - 1) {
return 0;
}
// 如果当前位置跳不到任何地方，这是一个无效路径（题目保证总能到达，但逻辑上要考虑）
if (nums[i] == 0) {
return Integer.MAX_VALUE; // 表示无法到达
}
int minSteps = Integer.MAX_VALUE;
// 尝试所有可能的跳跃
for (int j = 1; j <= nums[i]; j++) {
int nextSteps = process(nums, i + j);
if (nextSteps != Integer.MAX_VALUE) { // 如果后续路径有效
minSteps = Math.min(minSteps, nextSteps);
}
}
// 如果minSteps没被更新，说明从i出发无法到达终点
if (minSteps == Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
return 1 + minSteps;
}
这个递归有大量的重复计算，比如 process(5) 可能会被 process(2)、process(3)、process(4) 多次调用，时间复杂度是指数级的，铁定超时。
解法二：动态规划 (DP)
既然有重复计算，那记忆化搜索或者说DP就该上场了。我们创建一个 dp 数组，dp[i] 就存 process(i) 的结果。
dp[i] 的含义：从位置 i 跳到数组末尾所需的最少步数。
我们的目标是求 dp[0]。
dp[n-1] = 0。从
i = n-2倒着往前算。dp[i] = 1 + min(dp[i+j])，其中1 <= j <= nums[i]并且i+j < n。
// 解法二：动态规划
public int jump_v2(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
// dp[i] 表示从位置 i 到达终点所需的最少步数
// base case: dp[n-1] = 0
for (int i = n - 2; i >= 0; i--) {
if (nums[i] == 0) {
dp[i] = n; // 用一个比较大的数代表不可达
continue;
}
int minNext = n;
for (int j = 1; j <= nums[i] && i + j < n; j++) {
minNext = Math.min(minNext, dp[i + j]);
}
dp[i] = 1 + minNext;
}
return dp[0];
}
这个DP解法，每个位置 i 都需要向后遍历 nums[i] 步，所以时间复杂度是 O(N^2)，对于大数据量还是可能超时。但思路已经很清晰了。
解法三：贪心算法
这是这道题最精妙的解法。我们换个角度想：我不关心具体跳到哪一步，我只关心我跳这一步，能到达的最远范围是什么。
用几个变量来维护状态：
jumps: 当前已经跳了多少步。currentEnd: 当前这一跳能够到达的最远边界。farthest: 从当前位置i出发，通过一次跳跃，能到达的最远位置。
思路是这样的：我们遍历数组，但不急着做下一次跳跃的决定。在当前这一跳能覆盖的范围内（i <= currentEnd），我们不断更新下一步能跳到的最远距离 farthest。当遍历到 i 等于 currentEnd 时，说明当前这一跳的范围已经走完了，我们必须进行下一次跳跃了。这时，我们让 jumps++，并且把下一跳的边界 currentEnd 更新为我们之前找到的 farthest。
// 解法三：贪心算法
public int jump(int[] nums) {
int n = nums.length;
if (n <= 1) {
return 0;
}
int jumps = 0;
int currentEnd = 0; // 当前跳跃能到达的最远位置
int farthest = 0; // 从[0...i]这些位置出发，下一步能到达的最远位置
for (int i = 0; i < n - 1; i++) {
// 更新下一步能到达的最远位置
farthest = Math.max(farthest, i + nums[i]);
// 如果到达了当前跳跃的边界
if (i == currentEnd) {
jumps++; // 跳！
currentEnd = farthest; // 更新下一次跳跃的边界
// 如果新的边界已经可以覆盖终点，就可以提前结束了
if (currentEnd >= n - 1) {
break;
}
}
}
return jumps;
}
这个贪心算法只遍历了一遍数组，时间复杂度是 O(N)，空间复杂度是 O(1)。非常漂亮。它的正确性在于，每一步我们都选择了一个能让我们未来有更多选择（即跳得更远）的方案，这保证了全局最优。
23.2.2 跳跃游戏 (LeetCode 55)
给你一个非负整数数组
nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
我的思路：
这个问题比上一个简单，只问“能不能”，不问“最少几步”。
解法一：暴力递归
和上一题的思路完全一样，只是返回值变成了布尔类型。 canReach(i): 表示从位置 i 能否到达终点。
Base Case:
i == n-1，到了，返回true。递归过程: 尝试从
i跳到i+1, ..., i+nums[i]，只要其中任何一个后续调用canReach(next_i)返回true，那么canReach(i)就返回true。
// LeetCode 55. 跳跃游戏
// 解法一：暴力递归（会超时）
public boolean canJump_v1(int[] nums) {
return process(nums, 0);
}
private boolean process(int[] nums, int i) {
if (i >= nums.length - 1) {
return true;
}
if (nums[i] == 0) {
return false;
}
for (int j = 1; j <= nums[i]; j++) {
if (process(nums, i + j)) {
return true;
}
}
return false;
}
同样，指数级复杂度，会超时。
解法二：动态规划
dp[i]：布尔值，表示从位置 i 能否跳到终点。
dp[n-1] = true。从
i = n-2往前推。dp[i]为true的条件是：存在一个j（1 <= j <= nums[i]），使得i+j < n并且dp[i+j]为true。
// 解法二：动态规划
public boolean canJump_v2(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[n - 1] = true;
for (int i = n - 2; i >= 0; i--) {
for (int j = 1; j <= nums[i] && i + j < n; j++) {
if (dp[i + j]) {
dp[i] = true;
break; // 只要找到一条路就行
}
}
}
return dp[0];
}
时间复杂度 O(N^2)，空间 O(N)。比暴力好，但还能优化。
解法三：贪心算法
这题的贪心思路更直接。我们只需要维护一个变量 maxReach，表示从头开始，当前能到达的最远位置。 遍历数组，同时更新 maxReach。如果在遍历过程中，发现当前位置 i 已经超过了 maxReach，说明我们被困住了，永远到不了 i，更别说终点了。
// 解法三：贪心算法
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
// 如果当前位置已经超出了我们能到达的最远距离，那就不可能到达终点
if (i > maxReach) {
return false;
}
// 更新能到达的最远距离
maxReach = Math.max(maxReach, i + nums[i]);
// 优化：如果最远距离已经覆盖了终点，就可以提前返回了
if (maxReach >= nums.length - 1) {
return true;
}
}
// 循环能正常结束，说明能到达最后一个位置
return true;
}
这个解法只需要一次遍历，时间复杂度 O(N)，空间复杂度 O(1)。思路是，只要我能到达的位置 i，那么 i 能提供的新的最远距离 i + nums[i] 就是我潜在的下一步选择。我只需要一路维护这个“最远距离”就行了。
23.2.3 跳跃游戏 VII (LeetCode 1871)
给你一个下标从 0 开始的二进制字符串
s和两个整数minJump和maxJump。一开始，你在下标 0 处，且s[0] == '0'。当满足i + minJump <= j <= min(i + maxJump, s.length - 1)且s[j] == '0'时，你可以从下标i跳到下标j。请你返回你是否能到达s的最后一个下标。
我的思路:
这个问题加了限制，只能跳到 '0' 的位置，并且跳跃距离有上下限。还是问“能不能”，所以 DP 和 BFS 都是备选方案。
解法一：动态规划
dp[i] 表示是否能到达位置 i。
dp[0] = true对于
i > 0，dp[i]为true的条件是：s[i] == '0'并且 存在一个位置j，满足i - maxJump <= j <= i - minJump且dp[j]为true。
// LeetCode 1871. 跳跃游戏 VII
// 解法一：动态规划（会超时）
public boolean canReach_v1(String s, int minJump, int maxJump) {
int n = s.length();
if (s.charAt(n - 1) == '1') {
return false;
}
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 1; i < n; i++) {
if (s.charAt(i) == '0') {
// 检查之前的某个位置 j 是否能跳到 i
for (int j = Math.max(0, i - maxJump); j <= i - minJump; j++) {
if (dp[j]) {
dp[i] = true;
break;
}
}
}
}
return dp[n - 1];
}
这个 DP 的转移方程需要在一个窗口内查找是否有 true，这个窗口大小是 maxJump - minJump。每次计算 dp[i] 都要扫一遍窗口，总时间复杂度是 O(N * (maxJump - minJump))，会超时。
解法二：DP + 滑动窗口（前缀和思想）
上面的瓶颈在于，每次都要在 [i - maxJump, i - minJump] 这个窗口里找 dp 值。我们能不能快速知道这个窗口里有没有 true 呢？
我们可以维护一个变量 pre，表示在滑动窗口 [i - maxJump, i - minJump] 中，有多少个 dp 值为 true 的位置。 当我们计算 dp[i] 时，如果 s[i] == '0' 并且 pre > 0，那么 dp[i] 就是 true。 然后，当我们向右移动 i 时，这个窗口也向右移动。我们需要更新 pre：
窗口左边界
i - maxJump进来，如果dp[i - maxJump]是true，pre++。窗口右边界
i - minJump + 1出去，如果dp[i - minJump + 1]是true，pre--。
// 解法二：DP + 滑动窗口优化
public boolean canReach_v2(String s, int minJump, int maxJump) {
int n = s.length();
if (s.charAt(n - 1) == '1') return false;
boolean[] dp = new boolean[n];
dp[0] = true;
int preCount = 0; // 滑动窗口内可达位置的数量
for (int i = 1; i < n; i++) {
// 窗口左边界滑入
if (i >= minJump) {
if (dp[i - minJump]) {
preCount++;
}
}
// 窗口右边界滑出
if (i > maxJump) {
if (dp[i - maxJump - 1]) {
preCount--;
}
}
// 如果当前位置是'0'且窗口内有可达前驱，则当前位置也可达
if (s.charAt(i) == '0' && preCount > 0) {
dp[i] = true;
}
}
return dp[n - 1];
}
这个方法把检查窗口的操作变成了O(1)，总时间复杂度是O(N)，空间O(N)。
解法三：BFS + 剪枝
可以把每个 '0' 的位置看作图中的一个节点。从位置 i 可以跳到 j，就是一条有向边。问题变成了从 0 到 n-1 是否有路径。BFS 是最自然的选择。
队列里存放可以作为起跳点的下标。初始时，队列里只有 0。
每次从队列里取出一个
curr，然后找到它能跳到的所有next位置，即满足curr + minJump <= next <= curr + maxJump且s[next] == '0'的位置。把这些
next加入队列，并标记为已访问，避免重复。
朴素的BFS会重复扫描区间。比如从 i 能跳到 [i+min, i+max]，从 i+1 能跳到 [i+1+min, i+1+max]，这两个区间有重叠。
优化的思路是，我们只需要扫描那些尚未被访问过的 '0'。维护一个指针 farthestVisited，表示我们已经搜索过的最远 '0' 的位置。当从 curr 出发时，我们只需要从 max(curr + minJump, farthestVisited + 1) 开始扫描，找到下一个能跳到的点。
// 解法三：BFS + 剪枝
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
if (s.charAt(n - 1) == '1') return false;
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
int farthestReachable = 0; // 记录已经扫描并加入队列的最远位置
while (!queue.isEmpty()) {
int curr = queue.poll();
if (curr == n - 1) return true;
// 搜索范围：从`max(curr + minJump, farthestReachable + 1)`开始
// 这样可以跳过已经被之前节点覆盖的范围
int start = Math.max(curr + minJump, farthestReachable + 1);
int end = Math.min(curr + maxJump, n - 1);
for (int next = start; next <= end; next++) {
if (s.charAt(next) == '0') {
queue.offer(next);
}
}
// 更新已经扫描过的最远位置
farthestReachable = Math.max(farthestReachable, end);
}
return false;
}
这个BFS的思路，每个 '0' 点最多进队一次，并且 farthestReachable 指针保证了我们不重复扫描，所以总的时间复杂度也是 O(N)。
23.2.4 跳跃游戏 III (LeetCode 1306)
这里有一个非负整数数组
arr，你最开始位于start下标。当你位于下标i时，你可以跳到i + arr[i]或者i - arr[i]。请你判断自己是否能够跳到任意一个值为 0 的位置。
我的思路
这题变成了可以双向跳，而且目标是任意一个值为0的位置。这明显是一个图的遍历问题。数组的下标就是图的节点，i + arr[i] 和 i - arr[i] 就是边。
解法一：DFS (递归)
从 start 位置开始深度优先搜索。为了防止在两个位置之间来回跳导致死循环，我们需要一个 visited 数组来记录访问过的位置。
// LeetCode 1306. 跳跃游戏 III
// 解法一：DFS
public boolean canReach(int[] arr, int start) {
boolean[] visited = new boolean[arr.length];
return dfs(arr, start, visited);
}
private boolean dfs(int[] arr, int curr, boolean[] visited) {
// 越界或者已经访问过
if (curr < 0 || curr >= arr.length || visited[curr]) {
return false;
}
// 找到目标
if (arr[curr] == 0) {
return true;
}
visited[curr] = true;
// 往右跳
boolean canReachRight = dfs(arr, curr + arr[curr], visited);
// 往左跳
boolean canReachLeft = dfs(arr, curr - arr[curr], visited);
return canReachRight || canReachLeft;
}
这个思路很直观，每个节点最多访问一次，时间复杂度 O(N)，空间复杂度 O(N)（递归深度和visited数组）。
解法二：BFS
既然DFS可以，BFS当然也可以。BFS通常用在求最短路径，但这里只问可达性，所以也完全适用。
// 解法二：BFS
public boolean canReach_v2(int[] arr, int start) {
int n = arr.length;
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
if (arr[curr] == 0) {
return true;
}
// 往右跳
int nextRight = curr + arr[curr];
if (nextRight < n && !visited[nextRight]) {
queue.offer(nextRight);
visited[nextRight] = true;
}
// 往左跳
int nextLeft = curr - arr[curr];
if (nextLeft >= 0 && !visited[nextLeft]) {
queue.offer(nextLeft);
visited[nextLeft] = true;
}
}
return false;
}
BFS和DFS的思路本质相同，时间空间复杂度也一样，都是O(N)。
解法三：原地修改作为 visited
如果我们不想额外开一个 visited 数组，可以利用题目给的数组 arr 本身。因为 arr 都是非负整数，我们可以把访问过的位置 arr[i] 修改成一个负数，来表示 visited。
// 解法三：原地修改（节省空间）
public boolean canReach_v3(int[] arr, int start) {
if (start < 0 || start >= arr.length || arr[start] < 0) {
return false; // 越界或者已经访问过
}
if (arr[start] == 0) {
return true;
}
int jump = arr[start];
arr[start] = -1; // 标记为已访问
return canReach_v3(arr, start + jump) || canReach_v3(arr, start - jump);
}
这个解法修改了输入数组，空间复杂度降到了O(1)（如果不算递归栈）。需要注意面试时要和面试官确认是否可以修改输入。这本质上还是DFS，只是巧妙地利用了输入数组来记录状态。
接下来是后续问题的分析...（篇幅原因，我会继续按照这个模式，对每个问题给出三种思路和解法）
... 这种方式，我们从最简单的暴力尝试，发现问题（重复计算），然后用DP优化，再寻找问题特性（贪心、滑动窗口），一步步把解法推向最优。这套组合拳打下来，不管面试官怎么追问，都能应对自如。
（以下将继续完成剩余题目的分析）
23.2.5 跳跃游戏 IV (LeetCode 1345)
给你一个整数数组
arr，你一开始在数组的第一个元素arr[0]。每一步，你可以从下标i跳到下标：
i + 1，需要i + 1 < arr.length
i - 1，需要i - 1 >= 0
j，需要arr[i] == arr[j]且i != j请你返回到达数组最后一个元素的最少操作次数。
我的思路:
一看到“最少操作次数”，并且边的权重都是1（每一步算一次），这就是一个典型的无权图最短路径问题，BFS 是不二之选。
图的节点是数组的下标 0, 1, ..., n-1。 边有三种：
i -> i+1i -> i-1i -> j(所有arr[i] == arr[j]的j)
解法一：朴素 BFS
我们先建图，或者说在BFS的过程中动态找邻居。 为了快速找到所有 arr[i] == arr[j] 的 j，我们需要预处理一下，用一个 HashMap<Integer, List<Integer>> 来存所有值相同的位置。
// LeetCode 1345. 跳跃游戏 IV
// 解法一：朴素 BFS
public int minJumps_v1(int[] arr) {
int n = arr.length;
if (n <= 1) return 0;
// 预处理，记录相同值的所有下标
Map<Integer, List<Integer>> valToIndices = new HashMap<>();
for (int i = 0; i < n; i++) {
valToIndices.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(0);
visited[0] = true;
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int curr = queue.poll();
if (curr == n - 1) return steps;
// 1. 跳到 i+1
if (curr + 1 < n && !visited[curr + 1]) {
queue.offer(curr + 1);
visited[curr + 1] = true;
}
// 2. 跳到 i-1
if (curr - 1 >= 0 && !visited[curr - 1]) {
queue.offer(curr - 1);
visited[curr - 1] = true;
}
// 3. 跳到所有 arr[i] == arr[j] 的 j
if (valToIndices.containsKey(arr[curr])) {
for (int next : valToIndices.get(arr[curr])) {
if (!visited[next]) {
queue.offer(next);
visited[next] = true;
}
}
}
}
steps++;
}
return -1; // Not reachable
}
这个解法有个问题：当一个值出现很多次时，比如 [7,7,7,...,7,1]，我们从第一个7，会把所有其他的7都加入队列。从第二个7，又会把所有其他的7遍历一遍，造成大量重复检查。这会导致超时。
解法二：BFS + 剪枝（关键优化）
上面的瓶颈在于重复遍历相同值的下标列表。一个关键的优化是：当我们处理完一个值 v 的所有下标后，这个值的 "传送" 功能就已经用完了。之后再遇到值为 v 的点，我们不需要再把它所有相同值的邻居加一遍了，因为它们肯定已经被访问过了。所以，处理完一个值的列表后，直接从 map 中删掉它。
// 解法二：BFS + 剪枝优化
public int minJumps_v2(int[] arr) {
int n = arr.length;
if (n <= 1) return 0;
Map<Integer, List<Integer>> valToIndices = new HashMap<>();
for (int i = 0; i < n; i++) {
valToIndices.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(0);
visited[0] = true;
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int curr = queue.poll();
if (curr == n - 1) return steps;
// 1 & 2: 跳到 i+1, i-1
if (curr + 1 < n && !visited[curr + 1]) {
queue.offer(curr + 1);
visited[curr + 1] = true;
}
if (curr - 1 >= 0 && !visited[curr - 1]) {
queue.offer(curr - 1);
visited[curr - 1] = true;
}
// 3. 跳到相同值的位置，处理完后清除，避免重复
if (valToIndices.containsKey(arr[curr])) {
for (int next : valToIndices.get(arr[curr])) {
if (!visited[next]) {
queue.offer(next);
visited[next] = true;
}
}
// 【关键优化】处理完一个值的所有下标后，从 map 中移除
valToIndices.remove(arr[curr]);
}
}
steps++;
}
return -1;
}
这个小小的 remove 操作，让每个相同值的边集合只被处理一次，是AC的关键。
解法三：双向 BFS
当起点和终点都确定时，双向BFS是一个很好的优化。我们从起点和终点同时开始搜索，当两个搜索相遇时，就找到了最短路径。
维护两个队列
q_start,q_end维护两个 visited 集合
v_start,v_end每一轮，选择较小的那个队列进行扩展，这样可以更快地接近中间相遇点。
// 解法三：双向 BFS
public int minJumps(int[] arr) {
int n = arr.length;
if (n <= 1) return 0;
Map<Integer, List<Integer>> valToIndices = new HashMap<>();
for (int i = 0; i < n; i++) {
valToIndices.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
Queue<Integer> qStart = new LinkedList<>();
Queue<Integer> qEnd = new LinkedList<>();
boolean[] vStart = new boolean[n];
boolean[] vEnd = new boolean[n];
qStart.offer(0);
vStart[0] = true;
qEnd.offer(n - 1);
vEnd[n - 1] = true;
int steps = 0;
while (!qStart.isEmpty() && !qEnd.isEmpty()) {
// 优先扩展小的集合
if (qStart.size() > qEnd.size()) {
Queue<Integer> tempQ = qStart; qStart = qEnd; qEnd = tempQ;
boolean[] tempV = vStart; vStart = vEnd; vEnd = tempV;
}
int size = qStart.size();
for (int i = 0; i < size; i++) {
int curr = qStart.poll();
// 检查是否相遇
if (vEnd[curr]) return steps;
// 扩展
// 1. i+1
if (curr + 1 < n && !vStart[curr + 1]) {
qStart.offer(curr + 1);
vStart[curr + 1] = true;
}
// 2. i-1
if (curr - 1 >= 0 && !vStart[curr - 1]) {
qStart.offer(curr - 1);
vStart[curr - 1] = true;
}
// 3. same value
if (valToIndices.containsKey(arr[curr])) {
for (int next : valToIndices.get(arr[curr])) {
if (!vStart[next]) {
qStart.offer(next);
vStart[next] = true;
}
}
valToIndices.remove(arr[curr]);
}
}
steps++;
}
return -1;
}
双向BFS在图比较“宽”的情况下能显著减少搜索的节点数，是BFS的一个常用优化技巧。
23.2.6 到家的最少跳跃次数 (LeetCode 1654)
有一只跳蚤...它想从
x = 0处回到x = a + b的家。它只能向右跳a，不能跳到被禁止的点。它也可以向左跳b。并且，它不能跳到x < 0的位置。它也不能连续向左跳两次。求回到家的最少跳跃次数。
我的思路
又是一个“最少次数”，又是图的搜索问题，BFS首选。 这次的状态比较复杂，不仅仅是位置 x。因为有“不能连续向左跳两次”的限制，所以我们的状态必须包含上一步的方向。
State: (position, direction)，其中 direction 可以是 0 (from right) or 1 (from left)。
解法一：BFS
队列里存一个数组或自定义对象，
[position, direction, steps]。用一个
HashSet或二维布尔数组visited[position][direction]来记录访问过的状态，防止死循环。从
[0, 0, 0]开始 (位置0，上一步是向右的（初始状态），步数0)。
// LeetCode 1654. 到家的最少跳跃次数
// 解法一：BFS
public int minimumJumps(int[] forbidden, int a, int b, int home) {
Queue<int[]> queue = new LinkedList<>(); // [position, direction], 0-right, 1-left
Set<String> visited = new HashSet<>();
Set<Integer> forbiddenSet = new HashSet<>();
for (int f : forbidden) forbiddenSet.add(f);
queue.offer(new int[]{0, 0}); // pos, dir(0 for prev right, 1 for prev left)
visited.add("0,0");
int steps = 0;
// 需要确定一个搜索上界，否则向右可能无限跳。
// 一个合理的上界是 max(home, max(forbidden)) + a + b
// 因为如果跳过家太远，再往回跳可能不划算。
int limit = 2000 + a + b; // LeetCode 题目数据范围
for(int pos : forbidden) limit = Math.max(limit, pos + a + b);
limit = Math.max(limit, home + b);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int pos = curr[0];
int dir = curr[1];
if (pos == home) return steps;
// 1. 向右跳
int nextRightPos = pos + a;
if (nextRightPos < limit && !forbiddenSet.contains(nextRightPos) && !visited.contains(nextRightPos + ",0")) {
visited.add(nextRightPos + ",0");
queue.offer(new int[]{nextRightPos, 0});
}
// 2. 向左跳（前提：上一步不是向左跳）
int nextLeftPos = pos - b;
if (dir == 0 && nextLeftPos >= 0 && !forbiddenSet.contains(nextLeftPos) && !visited.contains(nextLeftPos + ",1")) {
visited.add(nextLeftPos + ",1");
queue.offer(new int[]{nextLeftPos, 1});
}
}
steps++;
}
return -1;
}
这个解法思路清晰，但搜索边界 limit 的确定比较关键，需要根据题目数据范围估算。如果 a > b，可能会在某个区间来回振荡，但如果 a < b，则会一直向左，所以必须有个下界0。
解法二：优化 visited 结构
用 String 作为 Set 的 key 会有额外的开销。可以用二维数组 boolean[][] visited，或者自己计算一个 hash 值。考虑到位置 pos 可能很大，二维数组不现实。Set<Integer>，key = pos * 2 + dir 是一个好方法。
// 解法二：优化 visited 结构
public int minimumJumps_v2(int[] forbidden, int a, int b, int home) {
// ... 和上面类似
Set<Integer> visited = new HashSet<>(); // key = pos * 2 + direction
// ...
// queue.offer(new int[]{0,0});
// visited.add(0 * 2 + 0);
// ...
// visited.contains(nextPos * 2 + dir)
}
这是一种工程上的小优化，不改变算法核心思想和复杂度。
解法三：Dijkstra 算法
虽然这个问题里每一步的"代价"都是1，BFS已经是最优的。但我们可以从更通用的角度看待它——最短路径问题。如果向左跳和向右跳的代价不同，比如跳 a 步代价是 cost_a，跳 b 步代价是 cost_b，那么问题就变成了带权图最短路径，就需要用 Dijkstra 算法。
这里强行用 Dijkstra 写一下，能加深对图算法的理解。
优先队列
PriorityQueue，存储[position, direction, cost]，按cost排序。dist[pos][dir]数组，记录到(pos, dir)状态的最小代价。
// 解法三：Dijkstra (用于理解通用性，本题中等价于BFS)
public int minimumJumps_v3(int[] forbidden, int a, int b, int home) {
// 状态: [cost, pos, dir]
PriorityQueue<int[]> pq = new PriorityQueue<>((v1, v2) -> v1[0] - v2[0]);
Map<String, Integer> dist = new HashMap<>(); // "pos,dir" -> min_cost
Set<Integer> forbiddenSet = new HashSet<>();
for (int f : forbidden) forbiddenSet.add(f);
pq.offer(new int[]{0, 0, 0}); // cost, pos, prev_dir
dist.put("0,0", 0);
int limit = 6000; // 经验上限
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int cost = curr[0];
int pos = curr[1];
int dir = curr[2];
if (cost > dist.getOrDefault(pos + "," + dir, Integer.MAX_VALUE)) {
continue;
}
if (pos == home) return cost;
// 向右
int nextRightPos = pos + a;
if (nextRightPos < limit && !forbiddenSet.contains(nextRightPos) &&
cost + 1 < dist.getOrDefault(nextRightPos + ",0", Integer.MAX_VALUE)) {
dist.put(nextRightPos + ",0", cost + 1);
pq.offer(new int[]{cost + 1, nextRightPos, 0});
}
// 向左
int nextLeftPos = pos - b;
if (dir == 0 && nextLeftPos >= 0 && !forbiddenSet.contains(nextLeftPos) &&
cost + 1 < dist.getOrDefault(nextLeftPos + ",1", Integer.MAX_VALUE)) {
dist.put(nextLeftPos + ",1", cost + 1);
pq.offer(new int[]{cost + 1, nextLeftPos, 1});
}
}
return -1;
}
对于所有边权为1的图，Dijkstra 退化成 BFS。但这个思维框架更通用，值得掌握。
第 24 章 迷宫问题
迷宫问题是图搜索的直接应用。二维数组就是图，每个格子是节点，相邻可通行的格子之间有边。
24.2.1 迷宫 (The Maze, LeetCode 490)
有一个球在迷宫中滚动，它会一直朝一个方向滚，直到撞到墙或边界才停下。给定球的起点、终点和迷宫，判断球能否停在终点。
我的思路
核心在于“一直滚直到停下”。这意味着一次移动（一次入队/一次递归）不是走一格，而是走到底。 问题是“能否”，所以 DFS 或 BFS 都可以。关键是要记录访问过的停靠点，而不是路径上的每个格子。
解法一：DFS
从起点开始，尝试四个方向。对于每个方向，模拟球滚动到底，找到停靠点。如果这个停靠点没被访问过，就从这个新的停靠点继续DFS。
// LeetCode 490. 迷宫
// 解法一：DFS
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length, n = maze[0].length;
boolean[][] visited = new boolean[m][n];
return dfs(maze, start[0], start[1], destination, visited);
}
private boolean dfs(int[][] maze, int r, int c, int[] dest, boolean[][] visited) {
if (visited[r][c]) return false;
if (r == dest[0] && c == dest[1]) return true;
visited[r][c] = true;
int[] dr = {-1, 1, 0, 0}; //上,下,左,右
int[] dc = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int nr = r, nc = c;
// 一直滚到底
while (nr + dr[i] >= 0 && nr + dr[i] < maze.length &&
nc + dc[i] >= 0 && nc + dc[i] < maze[0].length &&
maze[nr + dr[i]][nc + dc[i]] == 0) {
nr += dr[i];
nc += dc[i];
}
// 从新的停靠点继续搜索
if (dfs(maze, nr, nc, dest, visited)) {
return true;
}
}
return false;
}
解法二：BFS
思路和DFS一样，只是把递归改成队列。
// 解法二：BFS
public boolean hasPath_v2(int[][] maze, int[] start, int[] destination) {
int m = maze.length, n = maze[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(start);
visited[start[0]][start[1]] = true;
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
if (curr[0] == destination[0] && curr[1] == destination[1]) {
return true;
}
for (int i = 0; i < 4; i++) {
int nr = curr[0], nc = curr[1];
while (nr + dr[i] >= 0 && nr + dr[i] < m &&
nc + dc[i] >= 0 && nc + dc[i] < n &&
maze[nr + dr[i]][nc + dc[i]] == 0) {
nr += dr[i];
nc += dc[i];
}
if (!visited[nr][nc]) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
return false;
}
DFS和BFS在本题中复杂度类似，时间都是 O(MN)，因为每个停靠点最多访问一次，确定停靠点的过程最多遍历M或N。空间也是 O(MN)。
解法三：并查集 (Union-Find)
这是一个比较偏的思路，但能解。 我们可以把所有在同一条水平或垂直通路上，且中间没有障碍的格子，看作是互相连通的。 遍历迷宫的每个格子 (r, c)：
如果
maze[r][c] == 0，让它和它左边的格子(r, c-1)unite (如果左边也是0)。如果
maze[r][c] == 0，让它和它上边的格子(r-1, c)unite (如果上边也是0)。 这样，所有能通过“滚动”互相到达的点，最终会在一个连通分量里。 最后只要检查start和destination是不是在同一个集合里就行了。
// 解法三：并查集
class UnionFind {
// ... 并查集标准实现
}
public boolean hasPath_v3(int[][] maze, int[] start, int[] destination) {
int m = maze.length, n = maze[0].length;
UnionFind uf = new UnionFind(m * n);
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (maze[r][c] == 0) {
// 和上面 unite
if (r > 0 && maze[r - 1][c] == 0) {
uf.union(r * n + c, (r - 1) * n + c);
}
// 和左面 unite
if (c > 0 && maze[r][c - 1] == 0) {
uf.union(r * n + c, r * n + (c - 1));
}
}
}
}
return uf.find(start[0] * n + start[1]) == uf.find(destination[0] * n + destination[1]);
}
注意： 上面的并查集思路是错误的。并查集只能处理相邻格子的连通性，而题目中的“滚动”可以跨越多格。正确的并查集用法是：对于每个点 (r,c)，找到它四个方向滚到底的点 (nr, nc)，然后 union((r,c), (nr,nc))。这个构建过程比较复杂，不如DFS/BFS直观。所以并查集在这里并不是一个好的选择，但作为思维扩展，可以想想。
正确的解法还是DFS/BFS。
24.2.2 迷宫 II (The Maze II, LeetCode 505)
...在迷宫中滚动，求从起点到终点的最短距离。距离定义为球滚动的步数之和。
我的思路
问“最短距离”，而且边的权重不再是1（一次滚动可能滚过很多格，距离就是滚过的格子数），这是典型的带权图最短路径问题。Dijkstra 算法是标准答案。
解法一：Dijkstra 算法
状态：
(row, col)，即球停靠的位置。优先队列
pq存储[distance, row, col]，按distance从小到大排序。dist[m][n]数组，记录从起点到(r, c)的最短距离，初始化为无穷大。
// LeetCode 505. 迷宫 II
// 解法一：Dijkstra 算法
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
int m = maze.length, n = maze[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
// [distance, r, c]
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
dist[start[0]][start[1]] = 0;
pq.offer(new int[]{0, start[0], start[1]});
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0];
int r = curr[1];
int c = curr[2];
// 如果找到了更短的路径，就跳过当前这个
if (d > dist[r][c]) continue;
// 剪枝：如果到达终点，因为是Dijkstra，第一次到达即为最短
if (r == destination[0] && c == destination[1]) return d;
for (int i = 0; i < 4; i++) {
int nr = r, nc = c;
int steps = 0;
while (nr + dr[i] >= 0 && nr + dr[i] < m &&
nc + dc[i] >= 0 && nc + dc[i] < n &&
maze[nr + dr[i]][nc + dc[i]] == 0) {
nr += dr[i];
nc += dc[i];
steps++;
}
if (dist[r][c] + steps < dist[nr][nc]) {
dist[nr][nc] = dist[r][c] + steps;
pq.offer(new int[]{dist[nr][nc], nr, nc});
}
}
}
return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : dist[destination[0]][destination[1]];
}
这个是教科书般的Dijkstra解法，稳健且正确。
解法二：SPFA (适用于有负权边，但这里没有)
SPFA算法（Shortest Path Faster Algorithm），是 Bellman-Ford 的队列优化版本。它在国内比较流行，但在没有负权边的情况下，通常比 Dijkstra 慢。其思想是用一个队列来维护待更新的节点，一个节点只有在它的 dist 值被成功松弛（变得更小）后，才会重新入队，去更新它的邻居。 对于这道题，因为边权都是正的，Dijkstra 毫无疑问是更好的选择。SPFA 在这里可以写，但没有优势，只是作为一种备选方案。
// 解法二: 类似SPFA的思路（用普通队列代替优先队列）
// 这实际上会退化成一种BFS的变种，但不是标准的BFS，因为它可能多次访问一个节点
public int shortestDistance_v2(int[][] maze, int[] start, int[] destination) {
int m = maze.length, n = maze[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
Queue<int[]> queue = new LinkedList<>(); // [r, c]
dist[start[0]][start[1]] = 0;
queue.offer(start);
while(!queue.isEmpty()){
int[] curr = queue.poll();
int r = curr[0], c = curr[1];
// ... 滚动逻辑同上
for (/* ... */) {
// ...
if (dist[r][c] + steps < dist[nr][nc]) {
dist[nr][nc] = dist[r][c] + steps;
queue.offer(new int[]{nr, nc}); // 只要更新了就入队
}
}
}
//...
}
这种非优先队列的写法，可能会导致一个节点被多次入队，效率不如Dijkstra。
解法三：DFS + 剪枝
我们也可以用DFS来搜索，但必须记录最短距离。dfs(r, c, current_dist)。 为了避免重复搜索和低效路径，当我们要访问一个节点 (nr, nc) 时，如果 current_dist 已经大于等于 dist[nr][nc]，那么这条路就没必要再走下去了。
// 解法三：DFS + 剪枝
int[][] dist;
int m, n;
public int shortestDistance_v3(int[][] maze, int[] start, int[] destination) {
m = maze.length;
n = maze[0].length;
dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[start[0]][start[1]] = 0;
dfs(maze, start[0], start[1]);
return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : dist[destination[0]][destination[1]];
}
private void dfs(int[][] maze, int r, int c) {
// ... 四个方向滚动 ...
for (/* ... */) {
// ... 找到停靠点(nr, nc)和步数steps
if (dist[r][c] + steps < dist[nr][nc]) {
dist[nr][nc] = dist[r][c] + steps;
dfs(maze, nr, nc); // 继续从新点搜索
}
}
}
这个DFS本质上和解法二类似，都是一种 Bellman-Ford 的思想。在没有负权环的图上，它最终能找到正确答案，但效率通常不如Dijkstra。
24.2.3 迷宫 III (The Maze III, LeetCode 499)
...不仅要求最短距离，如果有多条最短距离的路径，还需要返回字典序最小的那条路径。路径用 "u", "d", "l", "r" 表示。
我的思路
这个问题在Dijkstra的基础上增加了第二个比较维度：路径的字典序。 我们的状态不仅要包括距离，还要包括路径字符串本身。
解法一：Dijkstra 算法（修改比较器）
优先队列
pq存储一个自定义对象或数组，包含[distance, path_string, row, col]。比较器逻辑：
优先比较
distance，距离短的优先。如果
distance相同，则比较path_string的字典序，字典序小的优先。
需要一个
path[m][n]数组来记录到达每个点的最优路径字符串。
// LeetCode 499. 迷宫 III
// 解法一：Dijkstra
class State {
int r, c, dist;
String path;
State(int r, int c, int dist, String path) {
this.r = r; this.c = c; this.dist = dist; this.path = path;
}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int m = maze.length, n = maze[0].length;
State[][] states = new State[m][n];
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
states[i][j] = new State(i, j, Integer.MAX_VALUE, "");
}
}
PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> {
if (a.dist != b.dist) return a.dist - b.dist;
return a.path.compareTo(b.path);
});
states[ball[0]][ball[1]].dist = 0;
pq.offer(states[ball[0]][ball[1]]);
char[] dirsChar = {'u', 'd', 'l', 'r'};
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 对应 u, d, l, r
while (!pq.isEmpty()) {
State curr = pq.poll();
if (curr.dist > states[curr.r][curr.c].dist ||
(curr.dist == states[curr.r][curr.c].dist && curr.path.compareTo(states[curr.r][curr.c].path) > 0)) {
continue;
}
for (int i = 0; i < 4; i++) {
int nr = curr.r, nc = curr.c;
int steps = 0;
String newPath = curr.path + dirsChar[i];
// 滚动
while (nr + dirs[i][0] >= 0 && nr + dirs[i][0] < m &&
nc + dirs[i][1] >= 0 && nc + dirs[i][1] < n &&
maze[nr + dirs[i][0]][nc + dirs[i][1]] == 0) {
nr += dirs[i][0];
nc += dirs[i][1];
steps++;
// 如果滚到了终点，就停下来
if (nr == hole[0] && nc == hole[1]) break;
}
State nextState = states[nr][nc];
int newDist = curr.dist + steps;
if (newDist < nextState.dist || (newDist == nextState.dist && newPath.compareTo(nextState.path) < 0)) {
nextState.dist = newDist;
nextState.path = newPath;
pq.offer(nextState);
}
}
}
String result = states[hole[0]][hole[1]].path;
return result.isEmpty() ? "impossible" : result;
}
这个解法非常直观，就是把Dijkstra的比较标准改了。但要注意，滚动过程中如果经过了终点，要能正确处理。上面的代码在循环条件里加了判断，如果滚到洞就停。
解法二 & 三
对于这个问题，DFS/SPFA等其他思路会变得非常复杂，因为它们不是一次性找到最优解。一个节点可能会被多次更新，每次更新路径和距离，都需要重新评估其后续所有路径，非常低效。Dijkstra 算法的贪心性质（每次取出全局最优的节点）和这个问题的要求（找到全局最优的路径）是完美匹配的。因此，在这种复合优化目标的问题中，Dijkstra 几乎是唯一的、最高效的选择。强行写其他解法没有太大意义，关键是理解为什么 Dijkstra 在这里是最佳方案。
第 25 章 设计问题
设计问题考察的是对数据结构的深刻理解和组合运用能力，目标通常是实现特定时间复杂度的操作。
25.2.1 O(1) 时间插入、删除和获取随机元素 (LeetCode 380)
我的思路
insertO(1):HashMap或HashSet。removeO(1):HashMap或HashSet。getRandomO(1): 数组或ArrayList，可以通过下标随机访问。
矛盾点在于，HashMap 无法 O(1) 随机访问，而数组的 remove 不是 O(1)（需要移动元素）。 要把两者结合起来。
解法一：HashMap + ArrayList
用一个
ArrayList存储元素，实现 O(1) 的getRandom。用一个
HashMap<Integer, Integer>存储值 -> 它在ArrayList中的下标。
核心技巧： 如何实现 O(1) 删除？ 当要删除 val 时：
通过
map找到val的下标index。获取
ArrayList的最后一个元素lastVal。将
lastVal放到index的位置上，覆盖掉要删除的val。更新
map中lastVal的下标为index。从
ArrayList中删除最后一个元素（这是O(1)的操作）。从
map中删除val。
// LeetCode 380. O(1) 时间插入、删除和获取随机元素
class RandomizedSet {
private List<Integer> list;
private Map<Integer, Integer> map;
private Random rand;
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
list.add(val);
map.put(val, list.size() - 1);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int index = map.get(val);
int lastVal = list.get(list.size() - 1);
// 核心：用最后一个元素覆盖要删除的元素
list.set(index, lastVal);
map.put(lastVal, index);
list.remove(list.size() - 1);
map.remove(val);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
这个“交换并删除末尾元素”的技巧是本题的精髓。
（对于这类设计题，通常只有一种主流的最优解法，很难像算法题一样提供多种不同思想的解法。我会尝试从不同数据结构组合的角度提供一些思路，但最终都会导向这个最优解。）
解法二 (思想实验)：双向链表 + HashMap
HashMap<Integer, Node>: 值 -> 链表节点。双向链表
DLinkedList存所有节点。insertO(1): 哈希表插入，链表尾部插入。removeO(1): 哈希表找到节点，链表O(1)删除节点。getRandomO(1)?: 做不到。链表无法随机访问。
所以这个思路走不通。
解法三 (思想实验)：尝试只用一个结构
只用
HashMap:getRandom无法 O(1)。需要转成数组再随机，那就是O(N)。只用
ArrayList:remove(非末尾) 是 O(N)。
结论：HashMap + ArrayList 的组合是解决这个问题的必要且经典的方式。
25.2.2 O(1) 时间插入、删除和获取随机元素（可重复）(LeetCode 381)
我的思路
上一题的加强版，允许元素重复。 问题来了：map 的 key 是唯一的，val -> index 的映射关系失效了。 怎么办？一个 val 可能对应多个 index。
解法一：HashMap<Integer, Set> + ArrayList
ArrayList<Integer>: 同样存储元素。HashMap<Integer, Set<Integer>>:值 -> 一组它在ArrayList中的下标。用Set或LinkedHashSet可以O(1)地添加/删除/获取一个下标。
删除操作 remove(val) 调整：
检查
map中是否存在val，以及它的下标Set是否为空。从
Set中随便取一个下标indexToRemove。和上一题一样，拿最后一个元素
lastVal来填补indexToRemove的位置。关键更新：
更新
lastVal在map中的下标信息：从
lastVal对应的Set中，删除它旧的下标（list.size() - 1）。向
lastVal对应的Set中，添加它的新下标indexToRemove。
从
map的val对应的Set中，删除indexToRemove。如果
val的Set变空了，可以从map中移除val。
从
list中移除最后一个元素。
// LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
class RandomizedCollection {
private List<Integer> list;
private Map<Integer, Set<Integer>> map; // val -> set of indices
private Random rand;
public RandomizedCollection() {
list = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
public boolean insert(int val) {
list.add(val);
Set<Integer> indices = map.computeIfAbsent(val, k -> new LinkedHashSet<>()); // LinkedHashSet O(1) get an element
indices.add(list.size() - 1);
return indices.size() == 1; // if it was newly created
}
public boolean remove(int val) {
if (!map.containsKey(val) || map.get(val).isEmpty()) {
return false;
}
// 1. Get an index of the val to remove
Set<Integer> valIndices = map.get(val);
int indexToRemove = valIndices.iterator().next(); // get an arbitrary index
// 2. Get the last element
int lastVal = list.get(list.size() - 1);
// 3. Move last element to the position of the element to remove
list.set(indexToRemove, lastVal);
// 4. Update map for both val and lastVal
valIndices.remove(indexToRemove);
Set<Integer> lastValIndices = map.get(lastVal);
lastValIndices.remove(list.size() - 1);
// Important: check if we are removing the last element which is also the 'val'
if (indexToRemove != list.size() - 1) {
lastValIndices.add(indexToRemove);
}
// 5. Remove from list
list.remove(list.size() - 1);
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}
这个实现细节更多，特别是当要删除的元素正好是最后一个元素时，map 的更新要小心。但核心思想不变。
25.2.3 全 O(1) 的数据结构 (LeetCode 432)
实现一个数据结构，支持
inc(key),dec(key),getMaxKey(),getMinKey()，所有操作都是 O(1)。
我的思路
inc/dec 想到 HashMap，getMax/getMin 想到有序结构（堆、平衡树），但它们的操作是 O(logN)。全 O(1) 是个非常强的约束。
这暗示着我们需要一种能 O(1) 访问头部和尾部的有序结构。双向链表 是一个好选择。
我们设计的双向链表的节点，存的不是 key，而是频率 (count)。
结构1:
HashMap<String, Node> keyToNode: 存储key对应的它所在的频率节点。结构2: 双向链表
DLinkedList: 链表的每个节点Node代表一个频率。Node内部包含:int count: 这个节点的频率值。Set<String> keys: 频率为count的所有key。
链表本身按
count有序。
操作流程 inc(key):
通过
keyToNode找到key当前所在的节点currNode(频率为c)。我们需要把
key移动到频率为c+1的节点。从
currNode.keys中移除key。查找
currNode的下一个节点nextNode。如果
nextNode不存在，或者nextNode.count != c+1，说明频率为c+1的节点不存在。我们在currNode和nextNode之间插入一个新节点newNode，其count为c+1。如果
nextNode.count == c+1，我们就用这个nextNode。
将
key加入到目标节点（newNode或nextNode）的keys集合中。更新
keyToNode中key的映射到这个新节点。如果
currNode.keys空了，说明频率为c的key已经没有了，可以从链表中删除currNode。
dec(key) 类似，是反向操作。 getMaxKey(): 返回链表尾部节点 tail.prev 的 keys 集合里的任意一个 key。 getMinKey(): 返回链表头部节点 head.next 的 keys 集合里的任意一个 key。
所有操作都是哈希表查找和链表节点增删，都是 O(1)。
// LeetCode 432. 全 O(1) 的数据结构
class AllOne {
class Node {
int count;
Set<String> keys = new LinkedHashSet<>();
Node prev, next;
Node(int count) { this.count = count; }
}
private Node head, tail; // dummy nodes
private Map<String, Node> keyToNode;
public AllOne() {
head = new Node(0);
tail = new Node(0);
head.next = tail;
tail.prev = head;
keyToNode = new HashMap<>();
}
private void insertAfter(Node prev, Node newNode) {
newNode.next = prev.next;
prev.next.prev = newNode;
prev.next = newNode;
newNode.prev = prev;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
public void inc(String key) {
Node currNode = keyToNode.getOrDefault(key, head);
currNode.keys.remove(key);
int newCount = currNode.count + 1;
Node nextNode = currNode.next;
if (nextNode.count != newCount) {
nextNode = new Node(newCount);
insertAfter(currNode, nextNode);
}
nextNode.keys.add(key);
keyToNode.put(key, nextNode);
if (currNode != head && currNode.keys.isEmpty()) {
removeNode(currNode);
}
}
public void dec(String key) {
Node currNode = keyToNode.get(key);
if (currNode == null) return;
currNode.keys.remove(key);
int newCount = currNode.count - 1;
if (newCount > 0) {
Node prevNode = currNode.prev;
if (prevNode.count != newCount) {
prevNode = new Node(newCount);
insertAfter(currNode.prev, prevNode);
}
prevNode.keys.add(key);
keyToNode.put(key, prevNode);
} else {
keyToNode.remove(key);
}
if (currNode.keys.isEmpty()) {
removeNode(currNode);
}
}
public String getMaxKey() {
if (tail.prev == head) return "";
return tail.prev.keys.iterator().next();
}
public String getMinKey() {
if (head.next == tail) return "";
return head.next.keys.iterator().next();
}
}
这个双向链表+哈希表的组合拳，是解决这类频率统计问题的“银弹”。
25.2.4 数据流的中位数 (LeetCode 295)
设计一个支持
addNum和findMedian的数据结构。
我的思路
中位数 需要一个能随时提供中间值的数据结构。
排序数组/列表：
addNum是 O(N)，findMedian是 O(1)。平衡二叉搜索树 (BST):
addNum是 O(logN)，findMedian也是 O(logN) (通过维护子树大小来快速定位)。
有没有 addNum 是 O(logN) 而 findMedian 是 O(1) 的方法？
解法一：对顶堆 (双堆)
维护两个堆：
大顶堆
maxHeap: 存储数据流中较小的一半数字。小顶堆
minHeap: 存储数据流中较大的一半数字。
保持平衡：
maxHeap的大小 等于 或 比minHeap大1。maxHeap的堆顶元素 <=minHeap的堆顶元素。
addNum(num) 流程:
如果
maxHeap为空或num <= maxHeap.peek()，则将num加入maxHeap。否则，将
num加入minHeap。调整：
如果
maxHeap.size() > minHeap.size() + 1，将maxHeap堆顶弹出，放入minHeap。如果
minHeap.size() > maxHeap.size()，将minHeap堆顶弹出，放入maxHeap。
findMedian() 流程:
如果元素总数是奇数，中位数就是
maxHeap的堆顶。如果元素总数是偶数，中位数是
(maxHeap.peek() + minHeap.peek()) / 2.0。
// LeetCode 295. 数据流的中位数
class MedianFinder {
// 大顶堆，存小数部分
private PriorityQueue<Integer> maxHeap;
// 小顶堆，存大数部分
private PriorityQueue<Integer> minHeap;
public MedianFinder() {
maxHeap = new PriorityQueue<>((a, b) -> b - a);
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
maxHeap.offer(num); // 先加入大顶堆
minHeap.offer(maxHeap.poll()); // 再把大顶堆的最大值给小顶堆
// 保证大顶堆数量 >= 小顶堆
if (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
}
}
这个 addNum 的实现更简洁：先把新数给 maxHeap，maxHeap 再把自己的最大值（不一定是新数）给 minHeap，最后检查一下平衡。这个过程巧妙地维护了两个堆的性质。 addNum 是 O(logN)，findMedian 是 O(1)。