→ Wardyal: 你怎麼早上都有時間再寫leetcodeㄚ 02/08 09:37
→ Rushia: 我提早到公司很簡單的上班前寫一寫很快 02/08 09:41
推 pandix: 大師 02/08 11:31
推 SecondRun: 大師 02/08 13:25
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