跳跃游戏II的贪心策略设计(LC45)
哪些公司问过
答案要点
- 维护当前跳跃边界end、下一跳最远位置farthest和步数
- 遍历中用i+nums[i]更新farthest
- i到达end时步数加一,end更新为farthest
- 选择依据:在当前可达范围内选下一步能跳最远的位置
- 只遍历到n-2,时间O(n)、空间O(1)
易错点
- 遍历到n-1导致多算一步
- 每一步都跳到当前能到的最远位置,而不是选下一步最远的起跳点
- 忽略数组长度为1时答案为0
面试官常见追问
- 为什么说这是BFS?
- 和跳跃游戏I(LC55)有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。