Open youngyangyang04 opened 3 months ago
这题值得推敲!深刻诠释了贪心算法
if (nums.length == 1) return 0;
int temp = 0, cover = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
temp = Math.max(i + nums[i], temp);
if (i == cover) {
count++;
cover = temp;
if (cover >= nums.length - 1) break;
}
}
return count;
// 例: nums = [2,3,1,1,4], temp = 0, cover = 0, count = 0
i = 0: temp = 2, 满足 0 == 0, count = 1, cover = 2。没到终点, 继续遍历。
i = 1: temp = 4, 不满足 1 == 2, 继续遍历。
i = 2: temp = 4, 满足 2 == 2, count = 2, cover = 4。到终点了, 停止遍历。
这道题用动规做感觉好理解一点,但是时间复杂度就为n^2了
struct Solution;
impl Solution {
pub fn jump(nums: Vec<i32>) -> i32 {
let mut dp = vec![i32::MAX;nums.len()];
dp[0] = 0;
for i in 0..nums.len() {
for j in 0..i {
if nums[j] >= i as i32-j as i32{
dp[i] = dp[i].min(dp[j]+1);
}
}
}
*dp.last().unwrap()
}
}
https://www.programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html