首页 > 试题广场 >

跳跃游戏-ii

[编程题]跳跃游戏-ii
  • 热度指数:12476 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一个非负整数数组,你最初在数组第一个元素的位置
数组中的元素代表你在这个位置可以跳跃的最大长度
你的目标是用最少的跳跃次数来到达数组的最后一个元素的位置
例如

给出数组 A =[2,3,1,1,4]

最少需要两次才能跳跃到数组最后一个元素的位置。(从数组下标为0的位置跳长度1到达下标1的位置,然后跳长度3到数组最后一个元素的位置)

示例1

输入

[2,3,1,1,4]

输出

2
 /*
	 * Runtime: 9 ms. Your runtime beats 93.99 % of java submissions.
	 * 参考自leetcode网友:@ChengZhang
	 * The main idea is based on greedy. Let's say the range of the current jump
	 * is [curBegin, curEnd], curFarthest is the farthest point that all points
	 * in [curBegin, curEnd] can reach. Once the current point reaches curEnd,
	 * then trigger another jump, and set the new curEnd with curFarthest, then
	 * keep the above steps, as the following
	 */
	public int jump(int[] A) {
		int jumps = 0, curEnd = 0, curFarthest = 0;
		for (int i = 0; i < A.length - 1; i++) {
			curFarthest = Math.max(curFarthest, i + A[i]);
			if (i == curEnd) {
				jumps++;
				curEnd = curFarthest;
			}
		}
		return jumps;
	}
编辑于 2017-06-25 10:48:20 回复(5)
  • 贪心解法:参考:http://blog.sina.com.cn/s/blog_6a0e04380102v5ag.html
  • 贪心大法好,但真的难想明白。。首先,要设置三个值:当前位置(是一个区域:从i~furthest_pre中,区域中的点中能到达的最大位置)所能到达的最大位置(furthest_cur),当前位置的上一个位置(也是区域)所能到达的最大位置(furthest_pre),还有就是所走的步数。
  • 有一点可能有点会懵,furthest_cur是还没有step++的时候,具体结合代码,也就是是一个预判能走到的但还没走的状态。
  • 感觉讲的还是有点乱,现在抛开代码,想象我们站在题目给的数组的开头位置:从开始位置到开始位置能走到的最大距离(furthest_pre)之间构成了一块区域,然后我们开始一格一格走,每走一下刷新一下当前这块区域能到的最大位置(furthest_cur),如果走到从开始位置走到了furthest_pre那我们也刷新出了最大的furthest_cur,如果furthest_cur比终点大,那恭喜!再跳一不就到终点了!可以开始跳一步咯!然后重复上述的动作,直到到达终点。
  • 如果能一步到最大位置furthest_pre,那肯定能到一步到它前面那块区域的某一位置,实行下一步跳,跳到furthest_cur
  • 给一个测试用例,可以在纸上画画:
4 1 6 9 7 4 5 0 6 8 1 2 3 5 8 0 2 1 2

代码

public class Solution {
    public int jump(int[] A) {
        int len=A.length;
        if(len==0||A==null){
            return 0;
        }
        int furthest_cur=0;
        int furthest_pre=0;
        int steps=0;
        for(int i=0;i<len;i++){
            if(furthest_pre>=len){
                return steps;
            }
            if(i>furthest_pre){
                furthest_pre=furthest_cur;
                steps++;
            }
            furthest_cur=Math.max(furthest_cur,A[i]+i);
        }
        return steps;
    }
}
发表于 2018-05-06 21:17:03 回复(1)
class Solution {
public:
    // 当前能够到达的最远距离还没有到n,必须再走下一步
    int jump(int A[], int n) 
    {
        int curReach=0,maxReach = 0,steps=0;
        for(int i=0;i<n && i<=maxReach;i++)
        { 
            if(i>curReach)    //steps-1步能够到达的距离,必须再走一步了
            {
                ++steps;
                curReach = maxReach;
            } 
            maxReach = max(maxReach,i+A[i]); // step步最远距离
        }
        if(maxReach<n-1)
            return -1;
        else
            return steps;
    }
};

发表于 2017-07-09 11:09:46 回复(0)
class Solution {
public:
    int jump(int A[], int n) {
        int cur=0;  // 每个台阶内最远去的地方
        int last=0;  // 每一步直接能跨越的最远距离
        int step=0;  //步数
        for(int i=0; i<n && cur>=i; ++i)
        {
            if(i>last)
            {
                last=cur;
                step++; 
            }
            cur =max(cur, A[i]+i);
        }
        
        return step;
        
    }
};

发表于 2016-04-08 21:43:27 回复(0)
/*
 贪心算法可以解决, 关键是三个变量的含义
 cur_step_max_point  使用当前的步数可以去的最远位置
 next_step_max_point 使用当前的步数,如果再走一步,可以到达的最远位置
 step 当前的步数
 -------------------
 一个具体的例子,i=1讲得比较详细,后面的基本就是代码流程。
 A[7] =  {3, 1, 2, 1, 2, 3, 2}
 初始状态:此时step=0, 所以最远能去0, 下一步能去的最远位置就是A[0]
 i = 0: 就是初试状态,step = 0, cur_step_max_point = 0, next_step_max_point = A[i] = 3;
 i = 1: 此时已经超过了当前步数step=0的的极限了,所以迈出一步,step = 1,同时当前步数可以到的最远点位置
        就要更新了,即cur_step_max_point = next_step_max_point = 3;同时next_step_max_point也
        可以更新了,即A[i] + i, 此时A[i] + i值为2,还不如i = 0时的next_step_max_point大,所以不更
        新,因为去2这个位置当前步数1就满足。
 i = 2  此时cur_step_max_point = 3,在当前步数的射程范围内,不用新增步数。但是在i = 2位置,下一步可以
        去的最远位置要更新了,因为A[i] + i = 4, 大于之前存的下一步可以到达的最远位置。next_step_max_point = 4;
 i = 3  也在cur_step_max_point = 3的射程范围内, cur_step_...不更新。此时i=3下一步能到达的最远位置A[3]+1=4,
        也不用更新
 i = 4  此时i已经超出了step = 1所能到达的最远距离cur_step... = 3。所以step++,step = 2。更新cur_step_...,令
        cur_step_max_point = next_step_max_point = 4。同时更新next_step_max_point = A[i] + i = 6;
 i = 5  此时i又超过了step = 2时的最大位置cur_step_max_point = 4。所以step++,step = 3
        cur_step_max_point = next_step_max_point = 6。next_step_max_point = A[i] + i = 8;
 
 这是突然发现cur_step_max_point = 6. 大于等于n。说明当前步数可以到达n点,于是直接return step.
 */
int jump(int A[], int n)
{
    if (n == 1 || n == 0) return 0;
    
    int next_step_max_point = A[0];  //下一步可以到达的最远距离
    int cur_step_max_point = 0;      //当前步数可以去的最远距离
    int step = 0;                    //去next_step_max_point的累计步数
    
    for(int i = 0; i < n; i++)
    {
        if (i > cur_step_max_point)
        {
            cur_step_max_point = next_step_max_point;
            step++;
        }
        if (cur_step_max_point >= n)
        {
            return step;
        }
        next_step_max_point = max(A[i] + i, next_step_max_point);
    }
    return step;
}

编辑于 2019-08-22 16:54:16 回复(0)
动态规划吧,很简单的
public class Solution {
public int jump(int[] A) {
 int len = A.length;
 int[] dp = new int[len];
 for(int i=1;i<len;i++){
 for(int j=1;j<=i;j++){
 if(i-(i-j)<=A[i-j]){
 dp[i]=dp[i-j]+1;
 }
 }
 }
 return dp[len - 1];
 }
 }

编辑于 2019-03-14 13:12:51 回复(0)
    /*
    * 目的:用最少的跳跃次数来到达数组的最后一个元素的位置
    * 方法:动态规划
    */
    int jump(int A[], int n) {
        vector<int>dp(n,INT_MAX);
        dp[0] = 0;
        for (int i = 0; i<n;i++){
            int maxp = min(i+A[i],n-1);
            for (int j = i+1;j<=maxp;++j){
                dp[j] = min(dp[j],dp[i]+1);
            }
        }
        return dp[n-1];
    }
发表于 2019-12-10 11:08:11 回复(0)
class Solution {
public:
    int jump(int A[], int n) {
        if(n==1) return 0;
        if(n==2) return 1;
        int a[n-1];
        a[0] = 1;
        int i,j;
        for(i=1;i<=n-2;i++){
            if(A[n-2-i]>=i+1)
                a[i] = 1;
            else{
                a[i] = n;
                for(j=1;j<=A[n-2-i];j++){
                    if(1+a[i-j]<a[i])
                        a[i] = 1+a[i-j];
                }
            }
        }
        return a[n-2];
    }
};


发表于 2019-03-19 21:16:22 回复(0)
先预处理一遍,把第i个为能走到的最大坐标存起来。 
我们从后往前处理,每次找到第一个能够大于等于目标值的坐标, 
把找到的坐标更新为下一个目标值,一直找到目标值为起始位置坐标,即为最小步数。
public int jump(int[] A) {
        int[] b=new int[A.length];
        for (int i = 0; i < A.length; i++) {
            b[i]=i+A[i];
        }
        int ans=0;
        int end=A.length-1;
        while (true){
            for (int j = 0; j < end; j++) {
                if(b[j]>=end){
                    end=b[j]-A[j];
                    ++ans;
                    break;
                }
            }
            if(end==0){
                break;
            }
        }
        return ans;
    }
发表于 2018-08-26 22:56:09 回复(0)
//动态规划
public class Solution {
    public int jump(int[] A) {
        int[] dp = new int[A.length + 1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < A.length; i++) {
            int index = A[i - 1] + i ;
            while ( index > i) {
                if (index < dp.length &&dp[i] + 1 < dp[index])
                    dp[index] = dp[i] + 1;
                index--;
            }
        }
        return dp[A.length];
    }
}

发表于 2017-11-21 14:23:22 回复(0)
class Solution {
public:
    int jump(int A[],int n) {
          int last=0,r=0,ans=0;
          for(int i=0;i<n&&i<=r;i++){
              if(i>last){
                 last=r;
                 ans++; 
              }
              r=max(r,i+A[i]);
          }
          return r>=n-1?ans:-1;
    }
};

发表于 2017-08-24 00:19:27 回复(0)
class Solution {
public:
    int jump(int A[], int n) {
        int *dp = new int[n]();  // dp存放都到各点的最小步数
        for(int i = 0; i < n; i++)
        {
            int maxp = min(i+A[i],n-1);  // 从i 出发能走到的最远距离
            for (int j = i + 1; j <= maxp; j ++) {
                if(dp[j] == 0 || dp[j] > dp[i]+1) 
                    dp[j] = dp[i] + 1; 
                 // 如果位置没被走过,或者可以用更少步数到达,则到达j点的步数为dp[i]+1
            }
        }
        int res = dp[n-1];
        delete [] dp; 
        dp = nullptr;
        return res;
    }
};

编辑于 2017-08-18 09:38:37 回复(0)
/*
用一个标号数组存储每个点到终点的最短距离,初始设置终点的dis为0;
从后往前更新每个点的最短距离即可
*/
class Solution {
public:
    int jump(int A[], int n) {
        if(n==0)return 0;
        int maxnum = 0xffffff;
        int dis[10000];
        for (int i = 0; i < sizeof(dis) / sizeof(dis[0]); i++)dis[i] = maxnum;
        dis[n-1]=0;
        for(int i=n-2;i>=0;i--){
            if(A[i]+i>=n-1)dis[i]=1;
            else for(int j=i;j<=A[i]+i;j++)if(dis[i]>dis[j]+1)dis[i]=dis[j]+1;
        }
        if(dis[0]==maxnum)return -1;
        return dis[0];
    }
};

发表于 2017-07-04 23:47:38 回复(0)
http://blog.sina.com.cn/s/blog_6a0e04380102v5ag.html
public class Solution {
    public int jump(int[] A) {
        if(A.length==0){
            return 0;
        }
        int furstep = 0,furpre = 0,step = 0;
        for(int i = 0;i<A.length;i++){
            if(furpre>=A.length-1){
                return step;
            }
            if(i>furpre){
                furpre = furstep;
                step++;
            }
            furstep = Math.max(furstep,A[i] + i);
        }
        return step;
    }
}

发表于 2017-06-12 15:38:02 回复(0)
public class Solution {
    public int jump(int[] A) {
        if(A == null || A.length <= 0)
        	return -1;
        // 动态规划,dp[i]放置到达i点的最少步数    
        int[] dp = new int[A.length];
        // 首先都赋值max
        for(int i = 0; i < A.length; i++)
        	dp[i] = Integer.MAX_VALUE;
        
        dp[0] = 0;
        for(int i = 0; i < A.length; i++){
              // A[i]>0,说明此点可达
        	if(A[i] > 0){
        		for(int j = 1; j <= A[i]; j++){
        			if(i + j < A.length)
        				dp[i + j] = Math.min(dp[i] + 1, dp[i + j]);
               // 第一次到达终点直接返回
                    if(i + j == A.length - 1)
        				return dp[A.length - 1];
            	}
        	}       	
        }        
        return dp[A.length - 1];
    }
}

发表于 2017-05-04 11:23:22 回复(0)
public class Solution {
    public int jump(int[] A) {
          if(A.length==1)
        return 0;
           int minstep=1,minindex=A[0],maxindex=minindex;
     for(int i=1,length=A.length;i<length;i++){
    if(i>minindex){
     minstep++;
    minindex=maxindex;
     }
    if(A[i]+i>maxindex){
maxindex=A[i]+i;
   }
   }
   return minstep;
        
    }
}
发表于 2017-04-30 17:44:32 回复(0)
[2,3,1,1,4]
1 2  3 4 5
可以看成是5个点,
1可以走1步,或2步因此可以到达2,3号位置,同理2可以选择走1,2,3步,在2可以到达
3,4,5。剩余结点同理。
因此可以转化为求最短路径问题。
编辑于 2017-01-29 19:23:18 回复(1)
public int jump(int[] A) {
		int[] dp = new int[A.length]; // dp存放都到各点的最小步数
		for (int i = 0; i < dp.length; i ++) {
			int maxPosition = Math.min(i + A[i], A.length - 1); // 从i点出发能走的最远距离
			for (int j = i + 1; j <= maxPosition; j ++) {
				if(dp[j] == 0) dp[j] = dp[i] + 1; // 如果位置没被走过,则到达j点的步数为dp[i]+1
			}
			if(dp[A.length - 1] != 0) break; // 当第一次到达终点时,肯定是到达终点最短的步数
		}
		return dp[A.length - 1];
	}
编辑于 2017-03-26 00:09:59 回复(7)
具体解析看代码注释:
public int jump (int[] A) {
        int[] resultList = new int[A.length + 1];
        // 为一维数组 resultList 填充初始值 -1, 值表示到达节点 i 所需的跳数,如果为-1 即为不可达
        Arrays.fill(resultList, -1);
        // 数组的起始位置一定是可达的, 并且所需跳数为 0
        resultList[0] = 0;
        int len = 0;
        for (int i = 0; i < A.length - 1; i++) {
            len = A[i];
            // 判断可达点 并且 len > 0
            if (len > 0 && resultList[i] > -1) {
                int endIndex = (i + len + 1 > A.length ? A.length : i + len + 1);
                for (int j = i + 1; j < endIndex; j++ ) {
                    if (resultList[j] == -1)  {
                        // 当前节点 i 跳数多1
                        resultList[j] = resultList[i] + 1;
                    }else {
                        // 当前节点 有其他的节点已经可达, 赋值为两者中的最小值
                        resultList[j] = Math.min(resultList[i] + 1, resultList[j]);
                    }
                }
            }
        }
        return resultList[A.length - 1];
    }


发表于 2020-09-20 17:29:39 回复(0)

符合动态规划的条件:

  1. 每个状态与前一个状态有关——设到i的最少步数为f(i),则f(i) = f(i的上一个点) + 1
  2. 初始状态是已知的——刚开始几个点的f与第一个点有关

然后就是实现问题了,两个循环,外循环是遍历每个点,内循环是遍历当前点的“势力范围”。

class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @return int整型
     */
    int jump(int *A, int n) {
        // write code here
        // 动态规划:设到i的最少步数为f(i),则f(i) = f(i的上一个点) + 1
        // dp数组保存到第i个点最少的步数
        if (n <= 1) return 0;
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            int maxIdx = min(A[i] + i, n - 1);  // 从i走能到的最大位置
            for (int j = i + 1; j <= maxIdx; ++j) {
                if (dp[j] == 0) dp[j] = dp[i] + 1; // 位置没有被走过,保存最小步数
            }
            if (dp[n - 1] != 0) return dp[n - 1];
        }
        return -1;
    }
};
发表于 2020-08-10 14:59:19 回复(0)