We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
出处:LeetCode 算法第55题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
出处:LeetCode 算法第55题
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。
采用动态规划的方式,定义一个数组dp,如果当前位置i能到达,则置dp[i]的值为数组的值,否则将dp[i]的值置为-1(表示不能到达)
/** * @param {number[]} nums * @return {boolean} */ var canJump = function (nums) { var dp = []; var length = nums.length; if (length == 0) { return false; } if (length == 1) { return true; } dp[0] = nums[0]; for (var i = 1, length = nums.length; i < length; i++) { var flag = false; for (var j = 0; j < i; j++) { if (Math.abs(i - j) <= dp[j]) { flag = true; dp[i] = nums[i]; break; } } if (!flag) { dp[i] = -1; } } return dp[length - 1] > -1 ? true : false; }; console.log(canJump([3, 2, 1, 0, 4]));
The text was updated successfully, but these errors were encountered:
No branches or pull requests
习题
思路
采用动态规划的方式,定义一个数组dp,如果当前位置i能到达,则置dp[i]的值为数组的值,否则将dp[i]的值置为-1(表示不能到达)
解答
The text was updated successfully, but these errors were encountered: