网站建设吉金手指专业15,wordpress支持的语言,职业生涯规划大赛规划书,洛阳霞光营销型网站面试经典150题 day9 题目来源我的题解方法一 动态规划双重循环方法二 贪心 题目来源
力扣每日一题#xff1b;题序#xff1a;55
我的题解
方法一 动态规划双重循环 使用一个dp表记录i位置是否可达#xff0c;然后在判断是否可达时需要看前面的nums[j]jidp… 面试经典150题 day9 题目来源我的题解方法一 动态规划双重循环方法二 贪心 题目来源
力扣每日一题题序55
我的题解
方法一 动态规划双重循环 使用一个dp表记录i位置是否可达然后在判断是否可达时需要看前面的nums[j]jidp[j]。 时间复杂度O( n 2 n^2 n2) 空间复杂度O(n) public boolean canJump(int[] nums) {int nnums.length;boolean[] dpnew boolean[n];dp[0]true;for(int i1;in;i){for(int j0;ji;j){if(nums[j]jidp[j])dp[i]true;}}return dp[n-1];
}方法二 贪心 记录当前能够达到的最大位置若能达到的最大位置小于当前位置则返回false若能达到的最大位置大于等于n-1则返回true,其他情况返回false。 时间复杂度O(n) 空间复杂度O(1) public boolean canJump(int[] nums) {int nnums.length;int maxIndex0;for(int i0;in;i){if(maxIndexi)return false;maxIndexMath.max(maxIndex,nums[i]i);if(maxIndexn-1)return true;}return false;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
