iT邦幫忙

2025 iThome 鐵人賽

DAY 23
0
Software Development

leetcode程式自學系列 第 23

Day23 leetcode程式自學

  • 分享至 

  • xImage
  •  

今天解的題目是第四十五題 Jump Game II,題目給定一個整數陣列 nums,每個元素代表在該位置最多可以往前跳的步數,起始位置在索引 0,目標是找到到達最後一個索引所需的最少跳躍次數,並且題目保證一定可以到達終點。這題的核心思路是使用貪心法來追蹤當前能到達的範圍與最遠能延伸的範圍,我們定義 end 表示當前這一步能走到的最遠邊界,farthest 則用來記錄在這個範圍內能延伸到的最遠位置。遍歷陣列的過程中,每次更新 farthest = max(farthest, i + nums[i]),表示目前位置能夠跳到的最遠索引,當我們走到 end 的位置時,代表這一步的範圍已經結束,必須要再跳一次,於是將跳數加一並更新 end = farthest。如此不斷往前推進,直到最後一格,就能計算出最少的跳數。以範例 nums = [2,3,1,1,4] 為例,第一次從索引 0 跳出範圍能到達最遠索引 2,跳數加一,接著在範圍 [1,2] 中,利用 nums[1] = 3 可以延伸到索引 4,當走到索引 2 時再跳一次,更新 end = 4,剛好到達終點,因此答案是 2。


上一篇
Day22 leetcode程式自學
下一篇
Day24 leetcode程式自學
系列文
leetcode程式自學24
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言