Re: [閒聊] 每日LeetCode已回收
55. Jump Game
跳跳遊戲，你每次可以從第i格跳nums[i]格，求出你是否可以從第0格跳到最後一格。
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
思路：
1.一樣是dp經過空間複雜度優化後變成貪婪，每次只要記錄i之前可以到達的最遠距離
當最遠距離不夠的時候返回false，而當最遠距離提前到達目的地也提前返回true。
Java Code：
-------------------
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int jump = nums[0];
for (int i = 1; i < n; i++) {
if (jump < i) {
return false;
}
if (jump >= n) {
return true;
}
jump = Math.max(jump, nums[i] + i);
}
return true;
}
}
-------------------
https://i.imgur.com/acHi4CL.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.106.12 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672019605.A.A2B.html
※ 編輯: Rushia (1.160.106.12 臺灣), 12/26/2022 09:53:58
推
12/26 10:03,
3年前
, 1F
12/26 10:03, 1F
討論串 (同標題文章)
完整討論串 (本文為第 153 之 719 篇)：