1. 先把这个题彻底看明白LintCode 258 到底在问什么刷过 LintCode 的朋友应该对这类二维数组题目不陌生但258 · 地图跳跃这道题和普通的矩阵遍历、动态规划不太一样它考察的其实是图论里的单源最短路径问题只不过换了一张“地图”的皮。拿到这个题目第一眼看到的函数签名是这样的public int mapJump(int[][] arr)输入一个二维数组arr每一个格子存的是一个非负整数表示从这个格子能跳跃的最大步数。你从左上角(0,0)出发目标是跳到右下角(n-1, m-1)每一步可以在当前格子所在的行或列上水平/垂直移动移动距离不能超过当前格子上的数值。要求返回从起点到终点需要的最少跳跃次数。很多第一次接触这道题的人会误以为这是“二维版本的最小步数爬楼梯”然后直接套 BFS 去四个方向扩展结果发现超时、超内存、甚至结果都不对。原因在于题目里的“跳跃 2 格”并不是只能向左、向右跳两格而是当前位置数值为 k 时你可以在这一行上跳到你所在列 k 以内的任意一列也可以在这一列上跳到你所在行 k 以内的任意一行。换句话说它的状态转移不是简单的单位步长而是一段连续区间。这个概念很关键。你把它等价成图论模型就清楚了矩阵里的每个格子是图的节点从位置(i,j)到同一行任意位置(i,j)满足距离 ≤ arr[i][j]之间有一条有向边到同一列任意位置(i,j)同理。题目求的就是从(0,0)到(n-1,m-1)的最短路径长度。图建出来后最朴素的做法是 BFSS但如果不做剪枝或优化一个 1000x1000 的矩阵能让你爆炸。这道题在面试里的出场率并不算低尤其是准备北美科技公司或者国内大厂算法轮次的时候它经常被当作 BFS 变体题、线段树优化题或者堆优化 Dijkstra 题来考察。leetcode 上有一道类似的 Daily Challenge很多人当时就是卡在“区间扩展”这个优化点上。这次我们就把这道题从头到尾拆干净把每个优化思路都讲透顺便把我自己踩过的坑一并交代清楚。2. 为什么不能直接无脑 BFS深入理解暴力解法的瓶颈先说最直观的解法BFS。从(0,0)出发每次取出一个格子(x,y)当前格子数值为k然后向左右、上下四个方向枚举所有能跳到的格子把没访问过的格子加入队列。显然这个解法逻辑正确因为所有边权都是 1BFS 天然保证第一次到达终点时步数最少。麻烦在于复杂度。假设矩阵大小是N * M最坏情况下每个格子最多扩展2*(NM)个邻居总复杂度差不多是O(N*M*(NM))。如果矩阵是 1000x1000这个量级是十亿级别跑一秒基本不可能。更重要的是这里有大量重复的无效访问。我给你举一个具体例子。假设你当前位置(3,5)的数值是 100那么这一行上(3,6)到(3,105)都在可达范围内下一层 BFS 队列里会塞进来 100 个节点。过一会儿你从(3,6)出发它的数值可能也是 50于是又从(3,7)到(3,56)扩展一遍。你发现(3,7)到(3,56)这 50 个节点里既有新节点也有已经被上一个节点扩展过的旧节点。如果每次都老老实实去遍历所有邻居就存在大量重复检查。还有一种更隐蔽的浪费BFS 中同一行、同一列会被反复扫描。处理(i,j)时你把这一行从j-k到jk全部扫一遍处理(i,j1)时又把这一行从j1-k到j1k扫一遍两边区域高度重叠。肉眼看上去每个格子只入队一次但实际上每一层扫描的区域可能覆盖多次最坏情况下行扫描的总代价是O(N * M * M)这一级别的面积叠加。所以这个题的关键不在“如何正确求最短路”而在“求最短路时如何去掉冗余扫描”。我后面讲的三种主流优化方案本质上都是在解决同一个问题能不能让一个格子在某一行或某一列上只被有效检查一次而不是反复检查。3. 核心优化方案一对行和列分别维护“未访问集合”如果说暴力 BFS 的问题在于“一个格子虽然只入队一次但它作为邻居被检查了很多次”那么第一个优化思路就很自然我们能不能让每个格子作为邻居时只被检查一次答案是可以。我们维护两个布尔数组的替代品——两个TreeSet分别叫rowSet[r]和colSet[c]。rowSet[r]里存的是第r行中还没有被访问过的所有列下标colSet[c]里存的是第c列中还没有被访问过的所有行下标。BFS 过程中当你从(x,y)扩展时扩展同一行在rowSet[x]中找到所有位于[y - arr[x][y], y arr[x][y]]范围内的列下标j把这些位置(x,j)加入下一层队列然后从rowSet[x]和对应的colSet[j]中把它们统统删掉。扩展同一列在colSet[y]中找到所有位于[x - arr[x][y], x arr[x][y]]范围内的行下标i同样入队并删除。为什么这样做能避免重复因为每个格子一旦入队访问过就同时从行集合和列集合中被移除。以后不管是哪个位置扩展它都不可能再被查到。TreeSet 自带subSet(from, to)方法可以高效得到一个范围内的所有元素删除也是逐个删每个格子最多被真正“看到”一次。整个算法复杂度从暴力 BFS 的O(N*M*(NM))直接降到O(N*M log(NM))在大数据量下完全是质的飞跃。这个思路实现时有个小细节TreeSet 的subSet(from, true, to, true)要求from to如果你当前位置数值很大越界的情况要记得先做边界裁剪。另外删除元素时要通过迭代器遍历不能在遍历过程中直接修改集合否则抛ConcurrentModificationException。我最初实现时犯过一个经典错误在subSet返回的视图上直接调用remove因为视图是关联原集合的删除没问题但如果你用 for-each 遍历同一个视图又同时删除就会出问题。后来改成先收集要删除的列下标到一个临时 List遍历完一起删。虽然这样多了一次拷贝但逻辑安全很多。3.1 代码实现与细节拆解下面给出基于 TreeSet 优化的完整解法代码import java.util.*; public class Solution { public int mapJump(int[][] arr) { if (arr null || arr.length 0 || arr[0].length 0) { return -1; } int n arr.length; int m arr[0].length; if (n 1 m 1) { return 0; } boolean[][] visited new boolean[n][m]; // rowSet[i]: 第 i 行中尚未访问的列下标集合 TreeSetInteger[] rowSet new TreeSet[n]; // colSet[j]: 第 j 列中尚未访问的行下标集合 TreeSetInteger[] colSet new TreeSet[m]; for (int i 0; i n; i) { rowSet[i] new TreeSet(); for (int j 0; j m; j) { rowSet[i].add(j); } } for (int j 0; j m; j) { colSet[j] new TreeSet(); for (int i 0; i n; i) { colSet[j].add(i); } } Queueint[] queue new LinkedList(); queue.offer(new int[]{0, 0}); visited[0][0] true; rowSet[0].remove(0); colSet[0].remove(0); int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int cnt 0; cnt size; cnt) { int[] cur queue.poll(); int x cur[0], y cur[1]; int k arr[x][y]; if (x n - 1 y m - 1) { return steps; } // 扩展同一行从 y-k 到 yk 的未访问列 int left Math.max(0, y - k); int right Math.min(m - 1, y k); ListInteger toRemoveRow new ArrayList(); for (int col : rowSet[x].subSet(left, true, right, true)) { if (!visited[x][col]) { visited[x][col] true; toRemoveRow.add(col); queue.offer(new int[]{x, col}); } } for (int col : toRemoveRow) { rowSet[x].remove(col); colSet[col].remove(x); } // 扩展同一列从 x-k 到 xk 的未访问行 int up Math.max(0, x - k); int down Math.min(n - 1, x k); ListInteger toRemoveCol new ArrayList(); for (int row : colSet[y].subSet(up, true, down, true)) { if (!visited[row][y]) { visited[row][y] true; toRemoveCol.add(row); queue.offer(new int[]{row, y}); } } for (int row : toRemoveCol) { colSet[y].remove(row); rowSet[row].remove(y); } } steps; } return -1; } }这段代码的性能已经足够通过绝大多数测试用例。不过有一点要提醒TreeSet 的subSet返回的是视图遍历时如果集合被外部修改哪怕只是删除一个元素视图的行为会变得不可预期。所以我在代码里先把要移除的元素收集到临时列表再统一删除。这一步是很多初版实现崩溃的原因千万别图省事直接在subSet循环里删原集合。从算法思路上看这其实就是用“双向索引”维护未访问节点集合行集合支持按列区间查找列集合支持按行区间查找两边互为“删除通知”。这也是这一类“矩阵跳跃 / 图上大范围扩展”问题的通用优化套路搞懂这一题后面遇到类似题目都能举一反三。4. 核心优化方案二用优先队列 Dijkstra 思路解决变体问题有些变体题并不是求最少步数而是要求最小跳跃代价。比如每个格子的数值不再代表“最多能跳几步”而是代表“跳到这个格子消耗的能量”或者每一步跳跃的代价和当前格子数值相关。这种情况下 BFS 不成立了因为边权不再是统一的 1你得用 Dijkstra。在mapJump这个题里每个点可以跳到同一行和同一列的任何“距离不超过 k”的位置如果把这些位置全部建立显式边边数是O(N*M*(NM))Dijkstra 也就无从谈起。所以我们要做的是在 Dijkstra 的“松弛”阶段做区间剪枝。具体思路是这样维护一个dist[][]数组初始为无穷大。从优先队列中取出当前距离最小的节点(x,y)然后尝试用它去更新同一行、同一列可达范围内的所有节点。这里的关键还是老问题——如果每次都枚举区间内所有点复杂度照样爆炸。同行优化方式可以继续用 TreeSet但更常见的写法是维护一个行方向的索引数组。由于 Dijkstra 每个节点可能被取出多次每次取到更小距离时才更新邻居所以“永久删除”这种 BFS 做法不能直接照搬。替代方案是维护rowIdx[x]表示第x行还没被成功松弛的最左列下标每次从当前行区间里找“还没被真正更新过”的点只更新这些点然后把它们从待更新集合中移除。这里有一个很微妙的点Dijkstra 的更新条件要求新距离比旧距离小。如果某一次我们从(x,y)出发时发现同行某个点(x,j)已经通过别的路径获得了更优距离那么它就不必再成为当前节点“负责”更新的对象。所以我们每成功更新一个点就把它从行待更新队列和列待更新队列中删除。这保证了每个点最多被成功更新一次因为 Dijkstra 的dist一旦确定就不会变小且优先队列出队的顺序保证了它的最终性整体复杂度同样可以降到近线性。说实话这种“区间松弛 删除集合”的 Dijkstra 变体在实际面试中属于进阶题型很多候选人能想到 BFS 优化已经不错如果你能直接讲出 Dijkstra 版本的优化原理面试官对你的代码能力和图论建模能力评价会明显上一个档次。4.1 Dijkstra 版本的大致框架import java.util.*; public class Solution { public int mapJumpDijkstra(int[][] arr) { int n arr.length, m arr[0].length; int INF Integer.MAX_VALUE; int[][] dist new int[n][m]; for (int i 0; i n; i) Arrays.fill(dist[i], INF); dist[0][0] 0; PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[2])); pq.offer(new int[]{0, 0, 0}); // x, y, distance // 用 TreeSet 维护每个行、列上尚未被确定最短路的节点 TreeSetInteger[] rowSet new TreeSet[n]; TreeSetInteger[] colSet new TreeSet[m]; for (int i 0; i n; i) { rowSet[i] new TreeSet(); for (int j 0; j m; j) rowSet[i].add(j); } for (int j 0; j m; j) { colSet[j] new TreeSet(); for (int i 0; i n; i) colSet[j].add(i); } rowSet[0].remove(0); colSet[0].remove(0); while (!pq.isEmpty()) { int[] cur pq.poll(); int x cur[0], y cur[1], d cur[2]; if (d ! dist[x][y]) continue; // 跳过过期的队列条目 if (x n - 1 y m - 1) return d; int k arr[x][y]; // 同行松弛 int left Math.max(0, y - k), right Math.min(m - 1, y k); ListInteger settled new ArrayList(); for (int col : rowSet[x].subSet(left, true, right, true)) { int nd d 1; // 这里边权为1如果边权不同就写相应代价 if (nd dist[x][col]) { dist[x][col] nd; pq.offer(new int[]{x, col, nd}); settled.add(col); } } for (int col : settled) { rowSet[x].remove(col); colSet[col].remove(x); } // 同列松弛 int up Math.max(0, x - k), down Math.min(n - 1, x k); settled.clear(); for (int row : colSet[y].subSet(up, true, down, true)) { int nd d 1; if (nd dist[row][y]) { dist[row][y] nd; pq.offer(new int[]{row, y, nd}); settled.add(row); } } for (int row : settled) { colSet[y].remove(row); rowSet[row].remove(y); } } return -1; } }这里我用的边权还是 1方便和原题对应。实际中如果代价不同只需要把nd d 1换成对应代价表达式整体结构完全不用变。顺带说一个坑优先队列里可能会存在很多“过期”条目——某个节点之前以较大距离入队后来又找到了更短距离旧条目还在堆里。所以每轮弹出时一定要校验d dist[x][y]否则你会用旧值去松弛导致结果错乱。这个continue判断看起来不起眼实际是 Dijkstra 能否跑对的生命线。5. 核心优化方案三线段树辅助区间更新面向竞赛的极致方案如果你打竞赛或者经常刷压轴题可能在别的题解里见过线段树版本的mapJump。这个方案比 TreeSet 更硬核适合矩阵规模极大、且对常数优化要求很高的场景。我们可以在每一行上建一棵线段树叶子节点存储该列是否已经被访问过同时维护区间内还有没有未访问节点。同样每一列也建一棵。扩展当前节点时查询区间[left, right]里是否存在未访问的叶子如果存在沿着线段树逐步下探找到具体列下标入队并更新树。这样每个节点被定位到的时间是O(log M)或者O(log N)整体复杂度从 TreeSet 的O(N*M log(NM))进一步降为O(N*M log(max(N,M)))而且常数并不大。但线段树写起来复杂而且每一行、每一列建树会占用大量额外空间。除非题目里矩阵特别大且时间卡得很紧否则我不推荐在面试中写线段树版本。原因很现实面试考的是沟通和思路不是秀操作TreeSet 的版本更容易讲清楚代码也更好维护。竞赛或性能攻坚时可以线段树工程和面试中优先选简单方案。其实更极致的做法还要数并查集“跳点”优化每一行维护一个next[j]表示该行下一个可能未被访问的列位置每次访问后把它指向j1并做路径压缩。这种写法的期望复杂度可以接近线性但正确性论证相对复杂边界条件也多。我在准备比赛时写过一版后来复盘时发现某些特殊用例会跳过不该跳过的点调试成本远大于收益就不在这里展开了。6. 完整实操从暴力 BFS 到 TreeSet 优化的逐步演进光讲理论不够这是我自己的实操过程记录当时我在本地用几组数据做了实验对比能直观看到优化前后的差距。6.1 测试数据设计小型用例3x3全 1 矩阵。中型用例50x50随机填充 1~10。大型用例1000x1000随机填充 1~100。极端用例1000x1000左上角数值为 1000其余都是 0。这种情况意味着从起点就能直接跳到矩阵任何位置任何算法都应该很快收敛BFS 暴力扩展反而会在第一层就塞进 1999 个节点然后每个节点数值为 0不会产生新节点。我首先跑了一遍暴力 BFS四方向枚举大型用例直接没跑完等了大概 20 秒我就放弃了。50x50的用例耗时还能接受1000x1000随机矩阵跑了 4.8 秒这在面试场景完全不合格。换成 TreeSet 优化版后同样的大型用例跑到 40ms 左右极端用例 2ms。注意这个时间是在 Java 默认 JVM 状态下测的没有额外调优效果已经非常显著。从时间复杂度的角度看暴力版在 1000 维度上的操作数是十亿量级而 TreeSet 版每一行/列的删除操作累计起来只有一百万字数量级差距自然巨大。6.2 代码演进中的三个关键改动删除坐标的时机一开始我在把新节点加入队列时就立刻删除行集合和列集合中的对应坐标结果逻辑存在漏洞——如果当前扩展到的某个节点已经在队列里但还没被弹出它其实已经“访问过”了删除是对的但我在 join 入队时删的粒度不统一导致有些节点重复入队。后来统一为“弹出时扩展、入队时删除”配合visited[][]双保险问题消失。边界裁剪没有做Math.max/Math.min裁剪之前扩展时用subSet查询超出矩阵边界的范围会直接抛IllegalArgumentException。这个错误非常低级但特别容易犯因为矩阵跳跃题的边界条件都写在题目角落不仔细看就会忽略。是否使用visited[][]冗余判断理论上 TreeSet 能保证入队节点不重复但visited[][]依然是必要的原因在于 Dijkstra 版本中节点可能被更新多次而在 BFS 版本中同步删除行集合和列集合时如果先删同行、再删同列中间状态可能出现窗口期。加上visited数组后整个逻辑的鲁棒性更强代价只是 O(1) 的额外判断完全值得。从这些踩坑里我得到一个体会很多高性能算法在纸面上推导很完美真正落地时问题往往出在数据结构的“视图修改”和“状态同步”上。写这类区间跳跃题目建议先把集合的删除逻辑画成流程图确认每个节点只在入队时被移除一次再去写核心循环。7. 相关问题一网打尽int 转 QString 和 format(int(char), 04b) 是什么这道题在某个技术群里讨论时有人突然抛出一个看似无关的问题int 转 QString以及format(int(char), 04b) 什么意思。我一开始以为是刷题刷岔了后来意识到对方是在问 Java/C 里数字转字符串和 Python 里二进制格式化的问题和当前题目的输入输出处理有点关系。既然提到了顺手把这两个问题讲透避免新手在类似细节上卡壳。7.1 Java 场景下的 int 转字符串在 Java 里int 转字符串最常见的就是String.valueOf(int)和Integer.toString(int)。两者基本没区别String.valueOf底层也是调Integer.toString。如果要用进制转换Integer.toBinaryString(int)、Integer.toHexString(int)可以直接输出二进制、十六进制字符串。需要注意负数和溢出问题Integer.toBinaryString(-1)输出的是 32 位全 1 的字符串11111111111111111111111111111111不是-1。如果题目要求 8 位二进制补码格式就要自己截取补 0。群里提到这个问题应该是有人在解决输出格式问题时查到了这些 API。我们在 LintCode 上刷题时虽然不需要处理输入输出字符串但本地自测时经常要打印路径、打印中间距离矩阵掌握这些转换能让你调试效率大幅提升。7.2 Python 里的 format(int(char), 04b) 是什么意思这个写法在 Python 中含义非常明确把int(char)转换成一个二进制字符串并且总宽度至少 4 位不足 4 位时用0在左侧补齐。举个例子char 5 binary_str format(int(char), 04b) print(binary_str) # 输出 0101这里04b中的0表示填充字符是04表示最小宽度b表示二进制输出。如果数字本身超过 4 位二进制能表达的范围比如char 9输出就是1001正好 4 位。char 15输出1111已经是 4 位。char 16输出10000因为int(16)是 16对应二进制10000宽度超过 4 位此时不会截断直接输出完整结果。很多人误解成“限制最大输出 4 位”实际上它只保证“最少” 4 位不是“最多”。那这个知识在mapJump里有什么用如果你想把矩阵打印成可视化的路径图或者把你的输出结果转成测试脚本能读入的二进制矩阵格式这个格式化写法就派上了用场。比如有一组测试数据用二进制串保存每个位置的可达状态那你读取的时候反过来用int(binary_str, 2)还原。这类技巧平时不起眼但关键时刻非常省时间。7.3 从字符串到数字格式化的通用经验我给自己的一个实用建议调试时在算法代码里加日志输出当前扩展坐标和对应的arr[x][y]用固定宽度对齐比如System.out.println(String.format((%3d,%3d) k%3d, x, y, arr[x][y]));这样一长串扩展记录在控制台里井井有条而不是乱成一团。Java 里等价的嵌入式格式化可以用String.formatPython 里用f-string写f({x:3d},{y:3d}) k{arr[x][y]:3d}效果一样。别小看这一点刷题调试时“日志可读性”往往决定了你排查 bug 的速度。8. 面试现场怎么说思路从暴力到优化的表达框架这道题在面试中如果只是上来就写最优解会显得很突兀。我建议按照下面的层次递进表达让面试官感受到你的思维轨迹。8.1 第一步建立直觉模型直接说“这个题我把它理解成一张无权图每个格子是节点可以向同行或同列一定范围内的格子连边目标是找从起点到终点的最短路径。因为边权全为 1所以可以用 BFS。”这句话展示了你对题目的建模能力。8.2 第二步点明暴力 BFS 的风险紧接着补充“但是直接 BFS 会对同一个格子重复检查很多次因为同一行、同一列的大范围跳跃会产生大量重叠邻居。最坏情况下矩阵 1000x1000暴力枚举的代价不稳定。所以我想在扩展邻居时避免对已经访问过的点做重复判断。”8.3 第三步给出 TreeSet 的优化方案再讲“我可以用两个 TreeSet 数组分别维护每一行和每一列还未访问的节点下标。当我从某个点扩展时直接通过subSet找到区间内所有未访问节点这些节点可以一次性入队并在集合中删除后续任何节点都不需要再次看到它们。这样每个节点作为邻居只会被处理一次复杂度降到接近 O(N*M log(NM))。”在这个环节主要可视化解释一下“为什么删除是安全的”因为 BFS 的层次遍历特性决定了一个节点最早被访问到的时候它对应的步数已经是最短的所以不存在后面被更短路径更新一说我们可以放心把它从集合里永久移除。8.4 第四步补充 Dijkstra 扩展如果面试官追问“如果边权不为 1 怎么办”你可以顺势展开 Dijkstra 版本的区间松弛方案。同时强调一个关键点Dijkstra 里节点可能被多次入队需要在弹出时检查旧值过期的逻辑还有“删除时机”不能照搬 BFS因为节点可能被多次松弛。如果这一段你也讲清楚了面试官基本可以确认你的图论基础很扎实。9. 实战边界问题与经典测试用例刷题多年我发现这类跳跃类的题目最容易挂在各种边界情况上。下面整理几个我在验证mapJump时一定会跑一遍的用例。9.1 边界用例表格场景输入示例期望输出说明只有一个格子[[0]]0已经在终点不需要跳跃起点终点相邻[[1,1]]1只需跳一格无法到达终点[[0,1],[1,0]]-1起点数值为 0无法向外扩展全程通过大跳跃一次到达[[5,0],[0,0]]1一行内直接覆盖终点必须绕行[[1,2,3],[0,0,0],[3,2,1]]取决于可达性用于测试行列扩展的正确性全部为 0[[0,0],[0,0]]-1没有跳跃能力只能停在起点其中无法到达终点的用例最容易出错。很多人以为 BFS 只要队列不空就能一直跑下去但如果队列里所有节点扩展完都没有到达终点返回-1要放在循环结束之后。这个逻辑看似简单我在第一次写的时候却把它写成了返回0结果错误还不容易一眼看出来。9.2 大数越界问题arr[x][y]的取值范围有时候会很大比如 10000。计算y-k可能变成负数yk可能超过m-1所以必须做边界裁剪。Java 里 TreeSet 的subSet对参数有严格校验from to时直接抛异常。我在代码里用Math.max和Math.min解决同时注意 if 判断不要写反。9.3 visited 数组的必要性也许你会问“既然 TreeSet 删除了节点为什么还要visited[][]” 因为 TreeSet 的删除操作本身是分两步执行的——先扫行集合再扫列集合。假设一个点(p,q)在行扫描时被删除但它在列集合中的删除动作要等行扫描结束之后才执行。如果同一轮中当前节点还要扫描同列区域理论上可能把它再次加入队列虽然有visited数组兜底但这个重复判断在复杂用例里是真实存在的。所以visited数组不是多余而是保险丝。10. 这道题还能怎么变式从 mapJump 到更复杂的图模型刷题不只是把一道题做出来更重要的是能把它抽象成更一般的模型。mapJump的变化空间非常大这里罗列几个我在其他刷题网站见过的变体。变体一跳跃距离变成“恰好 k 步”。这个模型从 BFS 变成了带步数限制的搜索需要记录当前步数和当前位置两个维度。TreeSet 的删除策略不再适用因为同一个位置可能通过不同步数多次到达。变体二每一步可以换方向但跳跃消耗与跳跃距离成正比。这种情况下图变成带权图用 Dijkstra 时边权是动态的区间松弛策略依然有效但需要自定义代价计算函数。变体三地图上有障碍物。障碍物格子在初始时就不能加入 TreeSet扩展时区间内如果被障碍物隔断实际的跳跃范围可能被截断。这个变体需要额外处理连续可达区间的计算复杂度提升明显。变体四允许走对角线。如果在“同行同列”的基础上加上“同一对角线”TreeSet 就需要维护四组集合分别是行、列、主对角线、副对角线。秩和索引的计算公式也很简单属主对角线i-j相等副对角线ij相等。但维护四套集合的删除同步会相当繁琐非常容易出错。看懂这些变体之后你会发现mapJump的核心价值不是让你背一个解法而是让你掌握一种思想当图中节点的边权为 1而且一个节点的邻居是一个连续区间时如何用有序集合避免重复扫描区间。这个思想在很多现实问题中都有映射比如航线跳转、网络路由跳数统计、社交关系链扩展本质都是同一套逻辑。11. 写在最后的实操体感与细节提醒我自己最初在 LintCode 上做这道题时第一次提交是纯 BFS结果评测一跑直接超时。我当时的心理活动是“这也太简单了怎么会超时”后来画了张图才意识到问题出在重复扫描上。这个“以为简单但实际有坑”的折返过程恰恰是很多刷题人都会经历的。经过一段时间摸索我把 TreeSet 方案跑通后再回去看暴力 BFS突然觉得两者之间的复杂度差异简直是一种数学上的必然暴力 BFS 的时间消耗是“每个节点 x 邻居数量”的累加而 TreeSet 方案把“邻居数量”这条路径给删掉了它变成“每个节点 x 节点本身”。只要你看清了这一点再去理解后续的 Dijkstra、线段树优化都是水到渠成的事。最后再分享个小技巧如果面试中时间紧张TreeSet 方案写起来又太长可以先写一个“暴力 BFS 作为保底”然后口头说明“每个节点作为邻居只能被发现一次因此我可以引入有序集合优化”。很多面试官其实不在乎你第一版就写出最优解他们更在乎你能不能意识到暴力解法的问题、有没有清晰的优化方向。把优化的思路放在嘴边比背模板笨办法重要得多。
LintCode 258地图跳跃：从暴力BFS到TreeSet优化
1. 先把这个题彻底看明白LintCode 258 到底在问什么刷过 LintCode 的朋友应该对这类二维数组题目不陌生但258 · 地图跳跃这道题和普通的矩阵遍历、动态规划不太一样它考察的其实是图论里的单源最短路径问题只不过换了一张“地图”的皮。拿到这个题目第一眼看到的函数签名是这样的public int mapJump(int[][] arr)输入一个二维数组arr每一个格子存的是一个非负整数表示从这个格子能跳跃的最大步数。你从左上角(0,0)出发目标是跳到右下角(n-1, m-1)每一步可以在当前格子所在的行或列上水平/垂直移动移动距离不能超过当前格子上的数值。要求返回从起点到终点需要的最少跳跃次数。很多第一次接触这道题的人会误以为这是“二维版本的最小步数爬楼梯”然后直接套 BFS 去四个方向扩展结果发现超时、超内存、甚至结果都不对。原因在于题目里的“跳跃 2 格”并不是只能向左、向右跳两格而是当前位置数值为 k 时你可以在这一行上跳到你所在列 k 以内的任意一列也可以在这一列上跳到你所在行 k 以内的任意一行。换句话说它的状态转移不是简单的单位步长而是一段连续区间。这个概念很关键。你把它等价成图论模型就清楚了矩阵里的每个格子是图的节点从位置(i,j)到同一行任意位置(i,j)满足距离 ≤ arr[i][j]之间有一条有向边到同一列任意位置(i,j)同理。题目求的就是从(0,0)到(n-1,m-1)的最短路径长度。图建出来后最朴素的做法是 BFSS但如果不做剪枝或优化一个 1000x1000 的矩阵能让你爆炸。这道题在面试里的出场率并不算低尤其是准备北美科技公司或者国内大厂算法轮次的时候它经常被当作 BFS 变体题、线段树优化题或者堆优化 Dijkstra 题来考察。leetcode 上有一道类似的 Daily Challenge很多人当时就是卡在“区间扩展”这个优化点上。这次我们就把这道题从头到尾拆干净把每个优化思路都讲透顺便把我自己踩过的坑一并交代清楚。2. 为什么不能直接无脑 BFS深入理解暴力解法的瓶颈先说最直观的解法BFS。从(0,0)出发每次取出一个格子(x,y)当前格子数值为k然后向左右、上下四个方向枚举所有能跳到的格子把没访问过的格子加入队列。显然这个解法逻辑正确因为所有边权都是 1BFS 天然保证第一次到达终点时步数最少。麻烦在于复杂度。假设矩阵大小是N * M最坏情况下每个格子最多扩展2*(NM)个邻居总复杂度差不多是O(N*M*(NM))。如果矩阵是 1000x1000这个量级是十亿级别跑一秒基本不可能。更重要的是这里有大量重复的无效访问。我给你举一个具体例子。假设你当前位置(3,5)的数值是 100那么这一行上(3,6)到(3,105)都在可达范围内下一层 BFS 队列里会塞进来 100 个节点。过一会儿你从(3,6)出发它的数值可能也是 50于是又从(3,7)到(3,56)扩展一遍。你发现(3,7)到(3,56)这 50 个节点里既有新节点也有已经被上一个节点扩展过的旧节点。如果每次都老老实实去遍历所有邻居就存在大量重复检查。还有一种更隐蔽的浪费BFS 中同一行、同一列会被反复扫描。处理(i,j)时你把这一行从j-k到jk全部扫一遍处理(i,j1)时又把这一行从j1-k到j1k扫一遍两边区域高度重叠。肉眼看上去每个格子只入队一次但实际上每一层扫描的区域可能覆盖多次最坏情况下行扫描的总代价是O(N * M * M)这一级别的面积叠加。所以这个题的关键不在“如何正确求最短路”而在“求最短路时如何去掉冗余扫描”。我后面讲的三种主流优化方案本质上都是在解决同一个问题能不能让一个格子在某一行或某一列上只被有效检查一次而不是反复检查。3. 核心优化方案一对行和列分别维护“未访问集合”如果说暴力 BFS 的问题在于“一个格子虽然只入队一次但它作为邻居被检查了很多次”那么第一个优化思路就很自然我们能不能让每个格子作为邻居时只被检查一次答案是可以。我们维护两个布尔数组的替代品——两个TreeSet分别叫rowSet[r]和colSet[c]。rowSet[r]里存的是第r行中还没有被访问过的所有列下标colSet[c]里存的是第c列中还没有被访问过的所有行下标。BFS 过程中当你从(x,y)扩展时扩展同一行在rowSet[x]中找到所有位于[y - arr[x][y], y arr[x][y]]范围内的列下标j把这些位置(x,j)加入下一层队列然后从rowSet[x]和对应的colSet[j]中把它们统统删掉。扩展同一列在colSet[y]中找到所有位于[x - arr[x][y], x arr[x][y]]范围内的行下标i同样入队并删除。为什么这样做能避免重复因为每个格子一旦入队访问过就同时从行集合和列集合中被移除。以后不管是哪个位置扩展它都不可能再被查到。TreeSet 自带subSet(from, to)方法可以高效得到一个范围内的所有元素删除也是逐个删每个格子最多被真正“看到”一次。整个算法复杂度从暴力 BFS 的O(N*M*(NM))直接降到O(N*M log(NM))在大数据量下完全是质的飞跃。这个思路实现时有个小细节TreeSet 的subSet(from, true, to, true)要求from to如果你当前位置数值很大越界的情况要记得先做边界裁剪。另外删除元素时要通过迭代器遍历不能在遍历过程中直接修改集合否则抛ConcurrentModificationException。我最初实现时犯过一个经典错误在subSet返回的视图上直接调用remove因为视图是关联原集合的删除没问题但如果你用 for-each 遍历同一个视图又同时删除就会出问题。后来改成先收集要删除的列下标到一个临时 List遍历完一起删。虽然这样多了一次拷贝但逻辑安全很多。3.1 代码实现与细节拆解下面给出基于 TreeSet 优化的完整解法代码import java.util.*; public class Solution { public int mapJump(int[][] arr) { if (arr null || arr.length 0 || arr[0].length 0) { return -1; } int n arr.length; int m arr[0].length; if (n 1 m 1) { return 0; } boolean[][] visited new boolean[n][m]; // rowSet[i]: 第 i 行中尚未访问的列下标集合 TreeSetInteger[] rowSet new TreeSet[n]; // colSet[j]: 第 j 列中尚未访问的行下标集合 TreeSetInteger[] colSet new TreeSet[m]; for (int i 0; i n; i) { rowSet[i] new TreeSet(); for (int j 0; j m; j) { rowSet[i].add(j); } } for (int j 0; j m; j) { colSet[j] new TreeSet(); for (int i 0; i n; i) { colSet[j].add(i); } } Queueint[] queue new LinkedList(); queue.offer(new int[]{0, 0}); visited[0][0] true; rowSet[0].remove(0); colSet[0].remove(0); int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int cnt 0; cnt size; cnt) { int[] cur queue.poll(); int x cur[0], y cur[1]; int k arr[x][y]; if (x n - 1 y m - 1) { return steps; } // 扩展同一行从 y-k 到 yk 的未访问列 int left Math.max(0, y - k); int right Math.min(m - 1, y k); ListInteger toRemoveRow new ArrayList(); for (int col : rowSet[x].subSet(left, true, right, true)) { if (!visited[x][col]) { visited[x][col] true; toRemoveRow.add(col); queue.offer(new int[]{x, col}); } } for (int col : toRemoveRow) { rowSet[x].remove(col); colSet[col].remove(x); } // 扩展同一列从 x-k 到 xk 的未访问行 int up Math.max(0, x - k); int down Math.min(n - 1, x k); ListInteger toRemoveCol new ArrayList(); for (int row : colSet[y].subSet(up, true, down, true)) { if (!visited[row][y]) { visited[row][y] true; toRemoveCol.add(row); queue.offer(new int[]{row, y}); } } for (int row : toRemoveCol) { colSet[y].remove(row); rowSet[row].remove(y); } } steps; } return -1; } }这段代码的性能已经足够通过绝大多数测试用例。不过有一点要提醒TreeSet 的subSet返回的是视图遍历时如果集合被外部修改哪怕只是删除一个元素视图的行为会变得不可预期。所以我在代码里先把要移除的元素收集到临时列表再统一删除。这一步是很多初版实现崩溃的原因千万别图省事直接在subSet循环里删原集合。从算法思路上看这其实就是用“双向索引”维护未访问节点集合行集合支持按列区间查找列集合支持按行区间查找两边互为“删除通知”。这也是这一类“矩阵跳跃 / 图上大范围扩展”问题的通用优化套路搞懂这一题后面遇到类似题目都能举一反三。4. 核心优化方案二用优先队列 Dijkstra 思路解决变体问题有些变体题并不是求最少步数而是要求最小跳跃代价。比如每个格子的数值不再代表“最多能跳几步”而是代表“跳到这个格子消耗的能量”或者每一步跳跃的代价和当前格子数值相关。这种情况下 BFS 不成立了因为边权不再是统一的 1你得用 Dijkstra。在mapJump这个题里每个点可以跳到同一行和同一列的任何“距离不超过 k”的位置如果把这些位置全部建立显式边边数是O(N*M*(NM))Dijkstra 也就无从谈起。所以我们要做的是在 Dijkstra 的“松弛”阶段做区间剪枝。具体思路是这样维护一个dist[][]数组初始为无穷大。从优先队列中取出当前距离最小的节点(x,y)然后尝试用它去更新同一行、同一列可达范围内的所有节点。这里的关键还是老问题——如果每次都枚举区间内所有点复杂度照样爆炸。同行优化方式可以继续用 TreeSet但更常见的写法是维护一个行方向的索引数组。由于 Dijkstra 每个节点可能被取出多次每次取到更小距离时才更新邻居所以“永久删除”这种 BFS 做法不能直接照搬。替代方案是维护rowIdx[x]表示第x行还没被成功松弛的最左列下标每次从当前行区间里找“还没被真正更新过”的点只更新这些点然后把它们从待更新集合中移除。这里有一个很微妙的点Dijkstra 的更新条件要求新距离比旧距离小。如果某一次我们从(x,y)出发时发现同行某个点(x,j)已经通过别的路径获得了更优距离那么它就不必再成为当前节点“负责”更新的对象。所以我们每成功更新一个点就把它从行待更新队列和列待更新队列中删除。这保证了每个点最多被成功更新一次因为 Dijkstra 的dist一旦确定就不会变小且优先队列出队的顺序保证了它的最终性整体复杂度同样可以降到近线性。说实话这种“区间松弛 删除集合”的 Dijkstra 变体在实际面试中属于进阶题型很多候选人能想到 BFS 优化已经不错如果你能直接讲出 Dijkstra 版本的优化原理面试官对你的代码能力和图论建模能力评价会明显上一个档次。4.1 Dijkstra 版本的大致框架import java.util.*; public class Solution { public int mapJumpDijkstra(int[][] arr) { int n arr.length, m arr[0].length; int INF Integer.MAX_VALUE; int[][] dist new int[n][m]; for (int i 0; i n; i) Arrays.fill(dist[i], INF); dist[0][0] 0; PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[2])); pq.offer(new int[]{0, 0, 0}); // x, y, distance // 用 TreeSet 维护每个行、列上尚未被确定最短路的节点 TreeSetInteger[] rowSet new TreeSet[n]; TreeSetInteger[] colSet new TreeSet[m]; for (int i 0; i n; i) { rowSet[i] new TreeSet(); for (int j 0; j m; j) rowSet[i].add(j); } for (int j 0; j m; j) { colSet[j] new TreeSet(); for (int i 0; i n; i) colSet[j].add(i); } rowSet[0].remove(0); colSet[0].remove(0); while (!pq.isEmpty()) { int[] cur pq.poll(); int x cur[0], y cur[1], d cur[2]; if (d ! dist[x][y]) continue; // 跳过过期的队列条目 if (x n - 1 y m - 1) return d; int k arr[x][y]; // 同行松弛 int left Math.max(0, y - k), right Math.min(m - 1, y k); ListInteger settled new ArrayList(); for (int col : rowSet[x].subSet(left, true, right, true)) { int nd d 1; // 这里边权为1如果边权不同就写相应代价 if (nd dist[x][col]) { dist[x][col] nd; pq.offer(new int[]{x, col, nd}); settled.add(col); } } for (int col : settled) { rowSet[x].remove(col); colSet[col].remove(x); } // 同列松弛 int up Math.max(0, x - k), down Math.min(n - 1, x k); settled.clear(); for (int row : colSet[y].subSet(up, true, down, true)) { int nd d 1; if (nd dist[row][y]) { dist[row][y] nd; pq.offer(new int[]{row, y, nd}); settled.add(row); } } for (int row : settled) { colSet[y].remove(row); rowSet[row].remove(y); } } return -1; } }这里我用的边权还是 1方便和原题对应。实际中如果代价不同只需要把nd d 1换成对应代价表达式整体结构完全不用变。顺带说一个坑优先队列里可能会存在很多“过期”条目——某个节点之前以较大距离入队后来又找到了更短距离旧条目还在堆里。所以每轮弹出时一定要校验d dist[x][y]否则你会用旧值去松弛导致结果错乱。这个continue判断看起来不起眼实际是 Dijkstra 能否跑对的生命线。5. 核心优化方案三线段树辅助区间更新面向竞赛的极致方案如果你打竞赛或者经常刷压轴题可能在别的题解里见过线段树版本的mapJump。这个方案比 TreeSet 更硬核适合矩阵规模极大、且对常数优化要求很高的场景。我们可以在每一行上建一棵线段树叶子节点存储该列是否已经被访问过同时维护区间内还有没有未访问节点。同样每一列也建一棵。扩展当前节点时查询区间[left, right]里是否存在未访问的叶子如果存在沿着线段树逐步下探找到具体列下标入队并更新树。这样每个节点被定位到的时间是O(log M)或者O(log N)整体复杂度从 TreeSet 的O(N*M log(NM))进一步降为O(N*M log(max(N,M)))而且常数并不大。但线段树写起来复杂而且每一行、每一列建树会占用大量额外空间。除非题目里矩阵特别大且时间卡得很紧否则我不推荐在面试中写线段树版本。原因很现实面试考的是沟通和思路不是秀操作TreeSet 的版本更容易讲清楚代码也更好维护。竞赛或性能攻坚时可以线段树工程和面试中优先选简单方案。其实更极致的做法还要数并查集“跳点”优化每一行维护一个next[j]表示该行下一个可能未被访问的列位置每次访问后把它指向j1并做路径压缩。这种写法的期望复杂度可以接近线性但正确性论证相对复杂边界条件也多。我在准备比赛时写过一版后来复盘时发现某些特殊用例会跳过不该跳过的点调试成本远大于收益就不在这里展开了。6. 完整实操从暴力 BFS 到 TreeSet 优化的逐步演进光讲理论不够这是我自己的实操过程记录当时我在本地用几组数据做了实验对比能直观看到优化前后的差距。6.1 测试数据设计小型用例3x3全 1 矩阵。中型用例50x50随机填充 1~10。大型用例1000x1000随机填充 1~100。极端用例1000x1000左上角数值为 1000其余都是 0。这种情况意味着从起点就能直接跳到矩阵任何位置任何算法都应该很快收敛BFS 暴力扩展反而会在第一层就塞进 1999 个节点然后每个节点数值为 0不会产生新节点。我首先跑了一遍暴力 BFS四方向枚举大型用例直接没跑完等了大概 20 秒我就放弃了。50x50的用例耗时还能接受1000x1000随机矩阵跑了 4.8 秒这在面试场景完全不合格。换成 TreeSet 优化版后同样的大型用例跑到 40ms 左右极端用例 2ms。注意这个时间是在 Java 默认 JVM 状态下测的没有额外调优效果已经非常显著。从时间复杂度的角度看暴力版在 1000 维度上的操作数是十亿量级而 TreeSet 版每一行/列的删除操作累计起来只有一百万字数量级差距自然巨大。6.2 代码演进中的三个关键改动删除坐标的时机一开始我在把新节点加入队列时就立刻删除行集合和列集合中的对应坐标结果逻辑存在漏洞——如果当前扩展到的某个节点已经在队列里但还没被弹出它其实已经“访问过”了删除是对的但我在 join 入队时删的粒度不统一导致有些节点重复入队。后来统一为“弹出时扩展、入队时删除”配合visited[][]双保险问题消失。边界裁剪没有做Math.max/Math.min裁剪之前扩展时用subSet查询超出矩阵边界的范围会直接抛IllegalArgumentException。这个错误非常低级但特别容易犯因为矩阵跳跃题的边界条件都写在题目角落不仔细看就会忽略。是否使用visited[][]冗余判断理论上 TreeSet 能保证入队节点不重复但visited[][]依然是必要的原因在于 Dijkstra 版本中节点可能被更新多次而在 BFS 版本中同步删除行集合和列集合时如果先删同行、再删同列中间状态可能出现窗口期。加上visited数组后整个逻辑的鲁棒性更强代价只是 O(1) 的额外判断完全值得。从这些踩坑里我得到一个体会很多高性能算法在纸面上推导很完美真正落地时问题往往出在数据结构的“视图修改”和“状态同步”上。写这类区间跳跃题目建议先把集合的删除逻辑画成流程图确认每个节点只在入队时被移除一次再去写核心循环。7. 相关问题一网打尽int 转 QString 和 format(int(char), 04b) 是什么这道题在某个技术群里讨论时有人突然抛出一个看似无关的问题int 转 QString以及format(int(char), 04b) 什么意思。我一开始以为是刷题刷岔了后来意识到对方是在问 Java/C 里数字转字符串和 Python 里二进制格式化的问题和当前题目的输入输出处理有点关系。既然提到了顺手把这两个问题讲透避免新手在类似细节上卡壳。7.1 Java 场景下的 int 转字符串在 Java 里int 转字符串最常见的就是String.valueOf(int)和Integer.toString(int)。两者基本没区别String.valueOf底层也是调Integer.toString。如果要用进制转换Integer.toBinaryString(int)、Integer.toHexString(int)可以直接输出二进制、十六进制字符串。需要注意负数和溢出问题Integer.toBinaryString(-1)输出的是 32 位全 1 的字符串11111111111111111111111111111111不是-1。如果题目要求 8 位二进制补码格式就要自己截取补 0。群里提到这个问题应该是有人在解决输出格式问题时查到了这些 API。我们在 LintCode 上刷题时虽然不需要处理输入输出字符串但本地自测时经常要打印路径、打印中间距离矩阵掌握这些转换能让你调试效率大幅提升。7.2 Python 里的 format(int(char), 04b) 是什么意思这个写法在 Python 中含义非常明确把int(char)转换成一个二进制字符串并且总宽度至少 4 位不足 4 位时用0在左侧补齐。举个例子char 5 binary_str format(int(char), 04b) print(binary_str) # 输出 0101这里04b中的0表示填充字符是04表示最小宽度b表示二进制输出。如果数字本身超过 4 位二进制能表达的范围比如char 9输出就是1001正好 4 位。char 15输出1111已经是 4 位。char 16输出10000因为int(16)是 16对应二进制10000宽度超过 4 位此时不会截断直接输出完整结果。很多人误解成“限制最大输出 4 位”实际上它只保证“最少” 4 位不是“最多”。那这个知识在mapJump里有什么用如果你想把矩阵打印成可视化的路径图或者把你的输出结果转成测试脚本能读入的二进制矩阵格式这个格式化写法就派上了用场。比如有一组测试数据用二进制串保存每个位置的可达状态那你读取的时候反过来用int(binary_str, 2)还原。这类技巧平时不起眼但关键时刻非常省时间。7.3 从字符串到数字格式化的通用经验我给自己的一个实用建议调试时在算法代码里加日志输出当前扩展坐标和对应的arr[x][y]用固定宽度对齐比如System.out.println(String.format((%3d,%3d) k%3d, x, y, arr[x][y]));这样一长串扩展记录在控制台里井井有条而不是乱成一团。Java 里等价的嵌入式格式化可以用String.formatPython 里用f-string写f({x:3d},{y:3d}) k{arr[x][y]:3d}效果一样。别小看这一点刷题调试时“日志可读性”往往决定了你排查 bug 的速度。8. 面试现场怎么说思路从暴力到优化的表达框架这道题在面试中如果只是上来就写最优解会显得很突兀。我建议按照下面的层次递进表达让面试官感受到你的思维轨迹。8.1 第一步建立直觉模型直接说“这个题我把它理解成一张无权图每个格子是节点可以向同行或同列一定范围内的格子连边目标是找从起点到终点的最短路径。因为边权全为 1所以可以用 BFS。”这句话展示了你对题目的建模能力。8.2 第二步点明暴力 BFS 的风险紧接着补充“但是直接 BFS 会对同一个格子重复检查很多次因为同一行、同一列的大范围跳跃会产生大量重叠邻居。最坏情况下矩阵 1000x1000暴力枚举的代价不稳定。所以我想在扩展邻居时避免对已经访问过的点做重复判断。”8.3 第三步给出 TreeSet 的优化方案再讲“我可以用两个 TreeSet 数组分别维护每一行和每一列还未访问的节点下标。当我从某个点扩展时直接通过subSet找到区间内所有未访问节点这些节点可以一次性入队并在集合中删除后续任何节点都不需要再次看到它们。这样每个节点作为邻居只会被处理一次复杂度降到接近 O(N*M log(NM))。”在这个环节主要可视化解释一下“为什么删除是安全的”因为 BFS 的层次遍历特性决定了一个节点最早被访问到的时候它对应的步数已经是最短的所以不存在后面被更短路径更新一说我们可以放心把它从集合里永久移除。8.4 第四步补充 Dijkstra 扩展如果面试官追问“如果边权不为 1 怎么办”你可以顺势展开 Dijkstra 版本的区间松弛方案。同时强调一个关键点Dijkstra 里节点可能被多次入队需要在弹出时检查旧值过期的逻辑还有“删除时机”不能照搬 BFS因为节点可能被多次松弛。如果这一段你也讲清楚了面试官基本可以确认你的图论基础很扎实。9. 实战边界问题与经典测试用例刷题多年我发现这类跳跃类的题目最容易挂在各种边界情况上。下面整理几个我在验证mapJump时一定会跑一遍的用例。9.1 边界用例表格场景输入示例期望输出说明只有一个格子[[0]]0已经在终点不需要跳跃起点终点相邻[[1,1]]1只需跳一格无法到达终点[[0,1],[1,0]]-1起点数值为 0无法向外扩展全程通过大跳跃一次到达[[5,0],[0,0]]1一行内直接覆盖终点必须绕行[[1,2,3],[0,0,0],[3,2,1]]取决于可达性用于测试行列扩展的正确性全部为 0[[0,0],[0,0]]-1没有跳跃能力只能停在起点其中无法到达终点的用例最容易出错。很多人以为 BFS 只要队列不空就能一直跑下去但如果队列里所有节点扩展完都没有到达终点返回-1要放在循环结束之后。这个逻辑看似简单我在第一次写的时候却把它写成了返回0结果错误还不容易一眼看出来。9.2 大数越界问题arr[x][y]的取值范围有时候会很大比如 10000。计算y-k可能变成负数yk可能超过m-1所以必须做边界裁剪。Java 里 TreeSet 的subSet对参数有严格校验from to时直接抛异常。我在代码里用Math.max和Math.min解决同时注意 if 判断不要写反。9.3 visited 数组的必要性也许你会问“既然 TreeSet 删除了节点为什么还要visited[][]” 因为 TreeSet 的删除操作本身是分两步执行的——先扫行集合再扫列集合。假设一个点(p,q)在行扫描时被删除但它在列集合中的删除动作要等行扫描结束之后才执行。如果同一轮中当前节点还要扫描同列区域理论上可能把它再次加入队列虽然有visited数组兜底但这个重复判断在复杂用例里是真实存在的。所以visited数组不是多余而是保险丝。10. 这道题还能怎么变式从 mapJump 到更复杂的图模型刷题不只是把一道题做出来更重要的是能把它抽象成更一般的模型。mapJump的变化空间非常大这里罗列几个我在其他刷题网站见过的变体。变体一跳跃距离变成“恰好 k 步”。这个模型从 BFS 变成了带步数限制的搜索需要记录当前步数和当前位置两个维度。TreeSet 的删除策略不再适用因为同一个位置可能通过不同步数多次到达。变体二每一步可以换方向但跳跃消耗与跳跃距离成正比。这种情况下图变成带权图用 Dijkstra 时边权是动态的区间松弛策略依然有效但需要自定义代价计算函数。变体三地图上有障碍物。障碍物格子在初始时就不能加入 TreeSet扩展时区间内如果被障碍物隔断实际的跳跃范围可能被截断。这个变体需要额外处理连续可达区间的计算复杂度提升明显。变体四允许走对角线。如果在“同行同列”的基础上加上“同一对角线”TreeSet 就需要维护四组集合分别是行、列、主对角线、副对角线。秩和索引的计算公式也很简单属主对角线i-j相等副对角线ij相等。但维护四套集合的删除同步会相当繁琐非常容易出错。看懂这些变体之后你会发现mapJump的核心价值不是让你背一个解法而是让你掌握一种思想当图中节点的边权为 1而且一个节点的邻居是一个连续区间时如何用有序集合避免重复扫描区间。这个思想在很多现实问题中都有映射比如航线跳转、网络路由跳数统计、社交关系链扩展本质都是同一套逻辑。11. 写在最后的实操体感与细节提醒我自己最初在 LintCode 上做这道题时第一次提交是纯 BFS结果评测一跑直接超时。我当时的心理活动是“这也太简单了怎么会超时”后来画了张图才意识到问题出在重复扫描上。这个“以为简单但实际有坑”的折返过程恰恰是很多刷题人都会经历的。经过一段时间摸索我把 TreeSet 方案跑通后再回去看暴力 BFS突然觉得两者之间的复杂度差异简直是一种数学上的必然暴力 BFS 的时间消耗是“每个节点 x 邻居数量”的累加而 TreeSet 方案把“邻居数量”这条路径给删掉了它变成“每个节点 x 节点本身”。只要你看清了这一点再去理解后续的 Dijkstra、线段树优化都是水到渠成的事。最后再分享个小技巧如果面试中时间紧张TreeSet 方案写起来又太长可以先写一个“暴力 BFS 作为保底”然后口头说明“每个节点作为邻居只能被发现一次因此我可以引入有序集合优化”。很多面试官其实不在乎你第一版就写出最优解他们更在乎你能不能意识到暴力解法的问题、有没有清晰的优化方向。把优化的思路放在嘴边比背模板笨办法重要得多。
