讨论/《中级算法》 - 跳跃游戏/
《中级算法》 - 跳跃游戏
共 5 个回复

动态规划思路:

dp[i]为在下标i 处,可以最多往后跳几步。动态规划解空间(即dp 数组)中,当前项一定可以由之前某一(几)项推导出,所以人脑尝试了对前几项子问题的求解之后发现,求当前项时需要做出选择:

  1. 不在当前位置停留,从上一位置继续往后跳,最大跳跃步数更新为dp[i-1] - 1;
  2. 在当前位置停留,最大跳跃步数更新为nums[i];

[2,3,1,1,4] 输入为例,枚举子问题的解大致过程如下:

dp[0] = nums[0] = 2;
dp[1] = Math.max(dp[0] - 1, nums[1]) = Math.max(2 - 1, 3) = 3;
dp[2] = Math.max(dp[1] - 1, nums[2]) = Math.max(3 - 1, 1) = 2;
dp[3] = Math.max(dp[2] - 1, nums[3]) = Math.max(2 - 1, 1) = 1;
dp[4] = Math.max(dp[3] - 1, nums[4]) = Math.max(1 - 1, 4) = 4;

Bingo,递推公式(状态转移方程)出现了:dp[i] = Math.max(dp[i-1] - 1, nums[i]),然后考虑各种边界条件,问题解决了。

TS 实现

function canJump(nums: number[]): boolean {
    if (nums.length === 1) {
        return true;
    }
    if (nums[0] === 0) {
        return false;
    }
    const dp = [nums[0]];
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] - 1, nums[i]);
        if (dp[i] + i + 1 >= nums.length) {
            return true;
        } else if (dp[i] === 0) {
            return false;
        }
    }
    return false;
};

贪心思路:

不太熟悉贪心套路,看官方题解才理解,TS 实现如下:

function canJump(nums: number[]): boolean {
    let mostFar = nums[0];
    for (let i = 1; i < nums.length - 1; i++) {
        // 如果i < mostFar 则意味着位置i 可以到达,必须要先到达i 才去根据nums[i] 更新mostFar,
        // 否则遇到[1,0,1,0] 这种case 会导致求解出错
        if (i <= mostFar) {
            mostFar = Math.max(mostFar, i + nums[i]);
        }
    }
    return mostFar >= nums.length - 1;
};
3

深度优先dfs (时间效率低,但是可以通过)

class Solution {
    boolean flag = false;
    public boolean canJump(int[] nums) {
		int len = nums.length;
		if (len <= 1)
			return true;
		boolean[] visited = new boolean[len];
		dfs(nums, 0, len, visited);
		return flag;
	}

	public void dfs(int[] nums, int k, int len, boolean[] visited) {
		if (k >= len - 1) {
			flag = true;
			return;
		}
		if(visited[k] || nums[k] == 0) return;
		visited[k] = true;
		for (int i = 1; i <= nums[k]; i++) {
			dfs(nums, i + k, len, visited);
		}
	}
}

dp:理解的是题解中某位大佬的解答(时间也不是特别快)

class Solution {

    public boolean canJump(int[] nums) {
        int len = nums.length;
        if (len <= 1) return true;

        boolean[] dp = new boolean[len];  // 用来保存能否每个位置能否到达

        dp[0] = true; // 默认从0的位置开始,所以0的位置可以到达,则true

        for (int i = 1; i < len; i++) {  // 依次判断能否到到达1~~len-1的位置--i
			// 每一个要到达的位置,只可能是从它前面的位置跳过来,所以从0开始遍历--j
            for (int j = 0; j < i; j++) {  
				// 只有j的位置能够到达才能到达i && 当j的位置加上最大跳跃距离 大于等于 i,也是可以保证能够到达i的位置。
                if (dp[j] && j + nums[j] >= i) {  
                    dp[i] = true;  // 能够到达i位置,所以变为true
                    break;
                }
            }
        }
        return dp[len - 1]; // 直接判断最后一个位置的boolean即可
    }
}

1

简单的逻辑

public boolean canJump(int[] nums) {
        boolean[] isTrue = new boolean[nums.length];
        isTrue[nums.length - 1] = true;
        int nearestTrue = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] >= nearestTrue - i) {
                isTrue[i] = true;
                nearestTrue = i;
            }
        }
        return isTrue[0];
    }

执行用时:1 ms, 在所有 Java 提交中击败了99.98%的用户
内存消耗:40.3 MB, 在所有 Java 提交中击败了66.78%的用户

为啥通过75、75然后还是超时了

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();   
        int rightmost = 0;
        for (int i = 0; i < n; ++i)
         {
            if (i <= rightmost) {                        //既然能到达最远那肯定前面的都能到
                rightmost = max(rightmost, i + nums[i]);//不断更新能到达的最远距离
                if (rightmost >= n - 1)     
                {
                    return true;
                }
            }
        }
        return false;
    }
};

跳跃游戏

  1. 首先想到的是在下一次可以跳跃的长度内,选择最大的值得位置作为下一个跳跃点,但是很快又发现,不应以最大值作为选取条件,而是看哪个跳跃点可以跳的最远,例如[6, 7, 4, 2, 4, 3, 5,········], 最初位于数组的第一个下标位置,若选取最大值作为跳跃点,则选择7,但是这样原本能够跳跃的长度6,只跳跃了1个位置,应该选取可以跳的最远的位置作为下一次的跳跃点,此例是5
  2. 外层循环判断条件为跳跃点下标在数组长度范围内 并且还有能跳的余地,即跳跃点位置元素不为0
  3. 内层循环判断可以跳跃的长度内,最长的跳跃

QQ图片20210506095308.jpg

class Solution {
public:
    bool canJump(vector<int> &nums) {
        int numsSize = nums.size();
        int currentIndex = 0;
        // 判断首次能否到达最终终点
        if (currentIndex + nums[currentIndex] >= numsSize - 1) {
            return true;
        }
        // 在数组长度范围内,且跳跃点不为0
        while (currentIndex < numsSize && nums[currentIndex] != 0) {
            if (currentIndex + nums[currentIndex] >= numsSize - 1) {
                return true;
            }
            int limit = nums[currentIndex];
            int maxStep = -1;
            int jumpIndex = 0;
            // 选取可以跳跃的最远长度,并非可以跳跃的长度内的最大值
            for (int i = 1; i <= limit; i++) {
                if (maxStep < nums[currentIndex + i] + i) {
                    maxStep = nums[currentIndex + i] + i;
                    jumpIndex = i;
                }
            }
            // 更新跳跃点位置
            currentIndex += jumpIndex;
        }
        return false;
    }
};

1620264630249.png