題目

https://leetcode.com/problems/jump-game/

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [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: [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.

解答

C#

public class Solution {
    public bool CanJump(int[] nums)
    {
        int length = nums.Length;
        if (length == 0)
            return false;
        
        int max = 0;
        for(int i = 0; i < length; i++)
        {
            if(i > max)
                return false;
            if(max > length)
                return true;
            max = Math.Max(max, nums[i] + i);
        }
        
        return true;
    }
}

結果

Runtime: 96 ms, faster than 95.36% of C# online submissions.

Memory Usage: 25.4 MB, less than 75% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(1)

為什麼我要這樣做？

這題主要是說，在 array 裡每個數字是當前可以走的最大步數，需要判斷出最終可不可以走到最後。
換句話說，你只要確定有一個 nums[i] 裡的數字可以走到最後，那就是 true；否則，就是 false。

1. 宣告 int length 為 array 的長度
2. 判斷 length 為 0 時，return false
3. 宣告 int max 用於記錄 nums[i] 可以走的 最大步數
4. 宣告 for 迴圈逐一判斷 nums[i]
   • if(i > max) return false; 表示當前的 位置 已經 超過 可以走的步數
   • if(max > length) return true; 表示 最大步數 可以走超過最後一個 位置
   • max = Math.Max(max, nums[i] + i);
     • 比較出 目前最大步數 max 與 當前可以走的步數 + 位置 index 的最大的數字，即為 最大步數
5. 若 for 迴圈結束後，沒有 return false，代表這個 array 是有辦法走到最後的，因此 return true;

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t730@yahoo.com.tw) 給我。
那我們就下回見囉