class Solution {
public:
int minJump(vector<int>& jump) {
}
};
LCP 09. 最小跳跃次数
为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。
为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。
示例 1：
输入：
jump = [2, 5, 1, 1, 1, 1]输出：
3解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。
限制：
1 <= jump.length <= 10^61 <= jump[i] <= 10000原站题解
golang 解法, 执行用时: 168 ms, 内存消耗: 49.5 MB, 提交时间: 2023-10-25 23:56:29
func minJump(jump []int) int {
n := len(jump)
res := len(jump)
var f[1000001]int
var max_dis[1000001]int
for i:=0; i<=n; i++{
f[i] = n+1;
max_dis[i] = 0;
}
f[0] = 0
curr_min_num := 0
for i:=0; i<n; i++{
if i>max_dis[curr_min_num]{
curr_min_num += 1
}
f[i] = Min(f[i], curr_min_num+1)
jump_tmp := i+jump[i]
if jump_tmp>=n {
res = Min(res,f[i]+1)
}else{
f[jump_tmp] = Min(f[jump_tmp],f[i]+1)
max_dis[f[i]+1] = Max(max_dis[f[i]+1],jump_tmp)
}
}
return res
}
func Min(x, y int) int {
if x < y {
return x
}
return y
}
func Max(x, y int) int {
if x > y {
return x
}
return y
}
cpp 解法, 执行用时: 420 ms, 内存消耗: 189.5 MB, 提交时间: 2023-10-25 23:56:12
class Solution {
private:
int f[10000000 + 7];
int maxdis[10000000 + 7];
public:
int minJump(vector<int>& jump) {
int n = jump.size();
int w = 0;
int ans = 1000000000;
for (int i=1; i<=n; ++i) {
f[i] = 1000000000;
maxdis[i] = 0;
}
f[1] = 0;
maxdis[0] = 1;
for (int i=1; i<=n; ++i) {
if (i > maxdis[w]) { // 更新单调指针
++w;
}
f[i] = min(f[i], w+1); // 用 maxdis[w] 更新 f[i]
int next = i + jump[i-1]; // 第一步跳跃更新
if (next > n) {
ans = min(ans, f[i] + 1);
} else if (f[next] > f[i] + 1) {
f[next] = f[i] + 1;
maxdis[f[next]] = max(maxdis[f[next]], next);
}
}
return ans;
}
};
python3 解法, 执行用时: 496 ms, 内存消耗: 78.5 MB, 提交时间: 2023-10-25 23:55:59
class Solution:
def minJump(self, jump: List[int]) -> int:
res = n = len(jump)
f = [n]*(n+1)
f[0] = 0
max_dis = [0]*(n+1)
curr_min_num = 0
for i in range(0,n):
if i>max_dis[curr_min_num]:
curr_min_num += 1
f[i] = min(f[i],curr_min_num+1)
jump_tmp = i+jump[i]
if jump_tmp>=n:
res = min(res,f[i]+1)
else:
f[jump_tmp] = min(f[jump_tmp],f[i]+1)
max_dis[f[i]+1] = max(max_dis[f[i]+1],jump_tmp)
return res
cpp 解法, 执行用时: 184 ms, 内存消耗: 107.8 MB, 提交时间: 2023-10-25 23:55:23
class Solution {
public:
int minJump(vector<int>& jump) {
vector<int> dp(jump.size(), 0);
for(int i = jump.size() - 1; i >= 0; --i)
{
if(i + jump[i] >= jump.size())
dp[i] = 1;
else
dp[i] = dp[i + jump[i]] + 1;
for(int j = i + 1; j < jump.size() && j < i + jump[i] && dp[j] > dp[i]; ++j)
dp[j] = dp[i] + 1;
}
return dp[0];
}
};
java 解法, 执行用时: 10 ms, 内存消耗: 119.9 MB, 提交时间: 2023-10-25 23:55:05
class Solution {
public int minJump(int[] jump) {
int[] dp = new int[jump.length];
dp[jump.length - 1] = 1;
for(int i = jump.length - 2; i > -1; --i){
dp[i] = jump[i] + i >= jump.length ? 1 : dp[jump[i] + i] + 1;
//遍历当前位置更新后影响到的后面的位置，只需要更新到dp[j] >= dp[i]+1即可
//如果遍历到某dp[j]<dp[i]+1就不需要向右遍历了,因为j到dp.length的值会被当前遍历到的dp[j]更新而不是dp[i]+1
for(int j = i + 1; j < dp.length && dp[j] >= dp[i] + 1; ++j){
dp[j] = dp[i] + 1;
}
}
return dp[0];
}
}