LeetCode 0045 - Jump Game II
# Hints
- 贪心
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
# 题意
给定一个长为 的非负整数数组 ,下标从 起,初始站在 处,从 出发可以跳到区间 内的任意一点,求最少需要跳多少次才能跳到 处。数据保证终点一定是可达的。
# 题解
容易想到动态规划求解,可以简单列出方程,用线段树维护区间最小值优化状态转移即可,时间复杂度为 。然而此题可以贪心求解,时间复杂度和代码简洁性都显著更优。
考虑从 出发,对于所有的 ,我们每次都跳到 最大的节点 处。这样一定是最优的。
因为题目保证右端点一定可达,所以前往最远可达点一定不会破坏当前的可达性。而如果没有这个保证,那么贪心显然是错误的,例如 的情形就不行了。对于这种情况,我们只需先用 LeetCode 0055 中的方法判断终点是否可达即可。
注意当 相等时要尽可能地前往编号更大的节点。
至于具体实现,我们直接模拟跳跃的过程即可,时间复杂度为 。
# AC代码
class Solution {
public:
int jump(vector<int> & nums) {
// 初始化
int n = nums.size();
int res = 0;
// 主循环
int pos = 0;
while (pos < n - 1) {
// 贪心
int nxt = pos;
for (int i = pos + 1; i <= min(pos + nums[pos], n - 1); i ++) {
if (min(nxt + nums[nxt], n - 1) <= min(i + nums[i], n - 1)) {
nxt = i;
}
}
// 更新答案
res ++;
// 递进
pos = nxt;
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01