跳跃游戏-ii

import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int jump (int[] nums) {
        int length = nums.length;
		// 当前这一步所能跳到的最远距离
		int end = 0;
		// 下一步能跳到的最远距离
		int maxLen = 0;
		// 步数
		int step = 0;
		for (int i = 0; i < length - 1; i++) {
			maxLen = Math.max(maxLen, i + nums[i]);
            // 如果到达了当前这一步所能到的最大距离，则跳下一步。
            // 注意 i < length - 1这个条件，这是因为，如果end刚好等于length-1,则会进行一步无用的跳跃（因为此时已经到达了最后一个元素了）
			if (i == end) {
				step++;
				end = maxLen;
			}
			if (end >= length - 1) {
				break;
			}
		}
		return step;
    }
}

//思路：
a   b 2 3 1 1 4
-2 -1 0 1 2
其中3+1最大，所以跳到3的位置


    public int jump (int[] A) {
        // write code here
        int size = A.length;
        int count=0;
        int i=0;
        
        while(i<size-1)
        {
            int len = A[i];
            if(i+len>=size-1)
            {
                count++;
                break;
            }
            int max = A[i];
            int index=0;
            for(int k=-len;k<=len;k++)
            {
                if(i+k>=0&&i+k<=size)
                {
                    if(A[i+k]+k>max)
                    {
                        max=A[i+k]+k;
                        index=i+k;
                    }
                }
            }
            i=index;
            count++;
        }
        return count;
    }

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];
 }
 }

public static int jump(int[] nums) {
        int[] dp =new int[nums.length];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0]=0;
        for (int i = 0; i < dp.length; i++) {
            for (int j = i+1; j <=i+nums[i]&&j<nums.length; j++) {
                dp[j]=Math.min(dp[i]+1, dp[j]);
            }
        }
        return dp[nums.length-1];
    }

牛客上能过，leetcode上显示超时

• 贪心解法：参考：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;
    }
}

//思路： 递归 + 缓存中间结果
public int jump(int[] A) {
        if(A.length == 0) return -1;
        if(A.length == 1) return 0;
        int[] *** = new int[A.length];
        // 缓存：从索引i到最后一个索引的最小步数
        for(int i = 0; i < ***.length; i++) {
            ***[i] = -1;
        }
        int min = jumpCore(A, 0, A.length - 1, ***);
        return min;
    }

    private int jumpCore(int[] A, int start, int end, int[] ***) {
        if(start >= end) {
            return 0;
        }
        // 如果以前计算过，直接返回
        if(***[start] != -1) return ***[start];
        // 为0，则不能到达最后一个索引
        if(A[start] == 0) {
            ***[start] = Integer.MAX_VALUE;
            return ***[start];
        }
        int min = Integer.MAX_VALUE;
        for(int i = 1; i <= A[start]; i++) {
            int step = jumpCore(A, start + i, end, ***);
            if(step != Integer.MAX_VALUE) min = Math.min(min, step + 1);
        }
        // 缓存结果
        ***[start] = min;
        return min;
    }

// dpi  表示当前位置到最后走的最少步数。从后往前遍历
public class Solution {
    public int jump(int[] A) {
        int n = A.length;
        int[] dp = new int[n];
        for(int i=n-2; i>=0; i--) {
            int min = n - i - 1;
            for(int j=i+1; j<n && j<=A[i]+i; j++)
                min = Math.min(dp[j] + 1, min);
            dp[i] = min;
        }
        return dp[0];
    }
}

//回复里原来还有On的算法,不知道为啥没置顶
 public int jump(int[] A) { // On
        int step = 0, maxdis_p = 0, maxdis = 0;// maxdis再多走一步最远能到哪， maxdis_p 当前步数最远能到哪， step当前步数
         for(int i=0; i<A.length; i++) {
             if(maxdis_p >= A.length)
                 return step;
             if(i > maxdis_p) {
                 step++;
                 maxdis_p = maxdis;
             }
             maxdis = Math.max(maxdis, A[i] + i);
         }
         return step;
    }

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];
	}

I try to change this problem to a BFS problem, where nodes in level i are all the nodes that can be reached in i-1th jump. for example. 2 3 1 1 4 , is
2||
3 1||
1 4 ||

clearly, the minimum jump of 4 is 2 since 4 is in level 3. my ac code.

int jump(int A[], int n) { if(n<2)return 0; int level=0,currentMax=0,i=0,nextMax=0;

	while(currentMax-i+1>0){
	

		//nodes count of current level>0
	


level++;

	for(;i<=currentMax;i++){
	

		//traverse current level , and update the max reach of next level
	


nextMax=max(nextMax,A[i]+i);

	if(nextMax>=n-1)return level;
	

		// if last element is in level+1,  then the min jump=level 
	


}
		 currentMax=nextMax;
	 } return 0;
 }