Re: [閒聊] 每日LeetCode
45. Jump Game II
給你一個陣列nums，nums[i]表示從這個點可以往後移動幾格，求出從第0格開始，最少
跳幾格可以跳到陣列尾端(題目保證一定可以到陣列尾端)。
Example:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1
step from index 0 to 1, then 3 steps to the last index.
Input: nums = [2,3,0,1,4]
Output: 2
思路：
1.如果當前走最遠的地方(curr)到不了i，讓curr等於下一次的最遠距離(next)且次數+1。
2.否則不斷更新下次可以走的最遠距離。
3.最後返回次數即可。
JavaCode：
------------------------------------
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int count = 0;
int curr = 0;
int next = 0;
for (int i = 0; i < n; i++) {
if (curr < i) {
count++;
curr = next;
}
next = Math.max(next, nums[i] + i);
}
return count;
}
}
------------------------------------
看起來是dp寫出來是貪婪 .0.
--
https://i.imgur.com/fHpKflu.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.64.249 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675819928.A.AE5.html
→
02/08 09:37,
2年前
, 1F
02/08 09:37, 1F
→
02/08 09:41,
2年前
, 2F
02/08 09:41, 2F
推
02/08 11:31,
2年前
, 3F
02/08 11:31, 3F
推
02/08 13:25,
2年前
, 4F
02/08 13:25, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 223 之 719 篇)：