class Solution { public: int jump(vectorint nums) { int step 0; // 跳跃次数 int start 0, end 0; // 当前这一跳能够覆盖的范围 // 还没有到达最后一个位置 while (end nums.size() - 1) { int far 0; // 下一跳最远能到的位置 // 在当前范围内寻找最远的位置 for (int i start; i end; i) { far max(far, i nums[i]); } // 当前这一跳结束更新下一跳的范围 start end; end far; step; // 跳了一次 } return step; } };详细总结1. 这道题到底在求什么给一个数组[2, 3, 1, 1, 4]nums[i]表示站在下标i最多可以向右跳nums[i]步。和上一道canJump不一样Jump Game I能不能到终点→true / falseJump Game II最少需要跳几次→ 返回step例如0 → 1 → 4只需要2 次所以答案是2。2.start和end是最重要的int start 0, end 0;它们表示当前这一轮我们能够考虑的范围。例如[start, end] [0, 2]就表示当前位置 0 1 2 └───────┘ 当前这一跳可以考虑的范围我们现在不需要马上决定从哪个位置跳。而是把[0,2]里面的所有位置都看一遍找出下一次跳跃最远能够到哪里。3.far是干什么的int far 0;far表示在当前范围内找到的最远位置。然后for (int i start; i end; i) { far max(far, i nums[i]); }就是不断尝试从 i 位置出发 最远 i nums[i]然后取其中最大的。例如nums [2, 3, 1, 1, 4]当前范围[0, 2]那么i 0 0 nums[0] 0 2 2 i 1 1 nums[1] 1 3 4 i 2 2 nums[2] 2 1 3所以far 4意思是在当前这一跳能够到达的范围里最好的选择可以让下一跳到达 4。4. 为什么找到far后才step这是这道题最关键的地方。我们不是走一步 step 再走一步 step而是把一整层能够到达的位置看成一次跳跃。例如nums [2,3,1,1,4]第一次[0] ↓ 最多可以到 [0,1,2]所以第一跳的范围是[0,2]然后我们在[0,2]里面寻找下一跳最远能到哪里0 → 2 1 → 4 2 → 3发现最远是4所以第二跳可以到4整个过程第1跳 0 → [0,1,2] 第2跳 [0,1,2] → 4所以step 25.start end; end far是什么意思start end; end far;可以理解成当前范围处理完了把范围推进到下一层。比如第一次start 0 end 0处理之后发现far 2更新start 0 end 2现在范围变成[0,2]下一轮就在这个范围里继续寻找。然后发现far 4再次更新start 2 end 4此时end 最后一个位置结束。6. 为什么while是这个条件while (end nums.size() - 1)意思是只要当前最远范围还没有覆盖最后一个位置就继续寻找下一跳。假设nums.size() 5最后一个下标就是4所以end 4如果end 2说明还没到终点0 1 2 3 4 ↑ end继续。如果end 4说明0 1 2 3 4 ↑ end已经覆盖终点了直接结束。最后把整个算法串起来你可以把它想成一层一层地扩展范围初始 [0] ↓ 找下一层最远位置 ↓ [0,1,2] ↓ 再找下一层最远位置 ↓ [0,1,2,3,4] ↓ 到终点对应代码就是while (end nums.size() - 1) { // ① 在当前范围找最远位置 for (int i start; i end; i) { far max(far, i nums[i]); } // ② 跳一次 step; // ③ 把范围扩展到 far start end; end far; }三个变量一定要分清变量含义start当前这一轮范围的左边界end当前这一轮范围的右边界far在当前范围内找到的下一跳最远位置step已经跳了多少次最重要的是end是“这一跳目前能覆盖到哪里”far是“在这一跳的范围里寻找后下一跳最远能覆盖到哪里”。一句话记忆当前范围[start,end]内寻找最远的far找到后跳一次并把end更新成far不断扩大覆盖范围直到覆盖终点。这其实就是一个很典型的贪心思想每次不急着决定具体从哪个位置跳而是在当前能够到达的所有位置中选择能让下一次覆盖范围最大的方案。
class Solution { public: int jump(vectorint nums) { int step 0; // 跳跃次数 int start 0, end 0; // 当前这一跳能够覆盖的范围 // 还没有到达最后一个位置 while (end nums.size() - 1) { int far 0; // 下一跳最远能到的位置 // 在当前范围内寻找最远的位置 for (int i start; i end; i) { far max(far, i nums[i]); } // 当前这一跳结束更新下一跳的范围 start end; end far; step; // 跳了一次 } return step; } };详细总结1. 这道题到底在求什么给一个数组[2, 3, 1, 1, 4]nums[i]表示站在下标i最多可以向右跳nums[i]步。和上一道canJump不一样Jump Game I能不能到终点→true / falseJump Game II最少需要跳几次→ 返回step例如0 → 1 → 4只需要2 次所以答案是2。2.start和end是最重要的int start 0, end 0;它们表示当前这一轮我们能够考虑的范围。例如[start, end] [0, 2]就表示当前位置 0 1 2 └───────┘ 当前这一跳可以考虑的范围我们现在不需要马上决定从哪个位置跳。而是把[0,2]里面的所有位置都看一遍找出下一次跳跃最远能够到哪里。3.far是干什么的int far 0;far表示在当前范围内找到的最远位置。然后for (int i start; i end; i) { far max(far, i nums[i]); }就是不断尝试从 i 位置出发 最远 i nums[i]然后取其中最大的。例如nums [2, 3, 1, 1, 4]当前范围[0, 2]那么i 0 0 nums[0] 0 2 2 i 1 1 nums[1] 1 3 4 i 2 2 nums[2] 2 1 3所以far 4意思是在当前这一跳能够到达的范围里最好的选择可以让下一跳到达 4。4. 为什么找到far后才step这是这道题最关键的地方。我们不是走一步 step 再走一步 step而是把一整层能够到达的位置看成一次跳跃。例如nums [2,3,1,1,4]第一次[0] ↓ 最多可以到 [0,1,2]所以第一跳的范围是[0,2]然后我们在[0,2]里面寻找下一跳最远能到哪里0 → 2 1 → 4 2 → 3发现最远是4所以第二跳可以到4整个过程第1跳 0 → [0,1,2] 第2跳 [0,1,2] → 4所以step 25.start end; end far是什么意思start end; end far;可以理解成当前范围处理完了把范围推进到下一层。比如第一次start 0 end 0处理之后发现far 2更新start 0 end 2现在范围变成[0,2]下一轮就在这个范围里继续寻找。然后发现far 4再次更新start 2 end 4此时end 最后一个位置结束。6. 为什么while是这个条件while (end nums.size() - 1)意思是只要当前最远范围还没有覆盖最后一个位置就继续寻找下一跳。假设nums.size() 5最后一个下标就是4所以end 4如果end 2说明还没到终点0 1 2 3 4 ↑ end继续。如果end 4说明0 1 2 3 4 ↑ end已经覆盖终点了直接结束。最后把整个算法串起来你可以把它想成一层一层地扩展范围初始 [0] ↓ 找下一层最远位置 ↓ [0,1,2] ↓ 再找下一层最远位置 ↓ [0,1,2,3,4] ↓ 到终点对应代码就是while (end nums.size() - 1) { // ① 在当前范围找最远位置 for (int i start; i end; i) { far max(far, i nums[i]); } // ② 跳一次 step; // ③ 把范围扩展到 far start end; end far; }三个变量一定要分清变量含义start当前这一轮范围的左边界end当前这一轮范围的右边界far在当前范围内找到的下一跳最远位置step已经跳了多少次最重要的是end是“这一跳目前能覆盖到哪里”far是“在这一跳的范围里寻找后下一跳最远能覆盖到哪里”。一句话记忆当前范围[start,end]内寻找最远的far找到后跳一次并把end更新成far不断扩大覆盖范围直到覆盖终点。这其实就是一个很典型的贪心思想每次不急着决定具体从哪个位置跳而是在当前能够到达的所有位置中选择能让下一次覆盖范围最大的方案。
