iT邦幫忙

2024 iThome 鐵人賽

DAY 11
0

原文題目

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

題目摘要

  1. 問題描述:給定一個整數陣列 nums,其中每個元素代表你從該位置最多可以跳的步數。起始位置是陣列的第一個位置,目標是判斷能否跳到陣列的最後一個位置。
  2. 輸入:一個整數陣列 nums,每個元素代表在該位置能跳的最大距離。
  3. 輸出:回傳 truefalsetrue 表示可以跳到最後一個位置,false 表示無法到達。

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.

Example 2:

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. 觀察跳躍範圍:每個位置的數值代表你能從該位置跳多遠,理論上你可以選擇在這個範圍內任意跳。重點在於你是否能持續向前移動到達終點。
  2. 追蹤最遠距離:可以設定一個變數 maxReach,表示你目前能跳到的最遠位置。如果 maxReach 超過或等於終點位置,那麼你就可以到達終點。
  3. 遍歷陣列:從頭開始依序遍歷每個位置,對於每個位置:
    • 如果當前的位置超過了 maxReach,那表示你無法繼續跳躍,直接回傳 false
    • 否則,更新 maxReach 為當前位置加上當前數值的最大值。
  4. 成功與否的判斷:如果你在遍歷過程中能更新 maxReach 到達或超過終點,則回傳 true

程式碼

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0; //定義maxReach為0,表示當前能跳到的最遠位置
        for (int i = 0; i < nums.length; i++) {
            //如果索引i超過了最遠可達範圍maxReach,表示無法繼續前進,直接回傳false
            if (i > maxReach) {
                return false;
            }else{
                //更新maxReach,使用 Math.max保證最遠的跳躍範圍
                maxReach = Math.max(maxReach, i + nums[i]);
            }
            //如果最遠可達範圍已經超過或等於最後一個位置,回傳true
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return true; //如果遍歷完所有位置都沒有被卡住,則返回 true
    }
}

結論: 這題「跳躍遊戲」就像在生活中達成目標時,你需要一步步地前進,有時候可能一步跳得很遠,有時候只能走小步。關鍵在於,你總要記得每一步的選擇都會影響你能走多遠,不能因為一兩次小的選擇就停下來。解題時,我們追蹤每一步能到達的最遠範圍,就像規劃下一步的最大潛力。如果途中某個時刻沒法再往前走,代表你被卡住,目標達不成了。不過,只要你能保持前進並不斷推進範圍,最終還是能成功達到終點。


上一篇
Day10 Greedy Algorithm題目1:121. Best Time to Buy and Sell Stock
下一篇
Day12 Greedy Algorithm題目3:45. Jump Game II
系列文
Java刷題B:Leetcode Top 100 Liked30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言