Leetcode — 55. Jump Game(中文)

問題連結: https://leetcode.com/problems/jump-game/

題目給定一個不包含負整數的陣列 nums, 陣列裡每個數字代表你在那個位子時可以跳最遠的距離
你最初的位子在index 0, 請回傳你是否可以跳到陣列最後一個位子

條件:

• 1 <= nums.length <= 3 * 104
• 0 <= nums[i] <= 105

比如給一陣列 nums = [2,3,1,1,4], 應回傳true
這例子有多種方式可以從起點跳到終點, 其中一個是從 0 跳到 1 再跳到終點 4.

⚠️ 此文章有3個不同的code, 可看我的程式碼演變, 從 252 ms 變 2 ms, 再進步到1ms.

想法:

最初看到這題, 我會想到我們可以用dynamic programming來解題
使用一個dp陣列來幫忙我們紀錄各個位子可到達的最遠地點
也就是說dp[i]就代表我們在位置i時可跳到的最遠位置

一開始會預設所有位置可跳的最遠位置是-1, 用來代表我們根本還不能跳到這邊 ⛔️
所以之後如果到了某點dp[i]=-1, 代表我們根本跳不到這麼遠, 就可以回傳false了

The code looks like below:

public boolean canJump(int[] nums) {
        int n = nums.length;
        //dp[i] stores the farest we can jump from pos i
        int[] dp = new int[n]; 
        //n-1 is our target
        Arrays.fill(dp,-1);
        dp[0] = 0; //starting point
        for(int i=0;i<n;i++)
        {
            if(dp[i]==-1) //前面的位子都沒辦法跳到位置i
                return false;
            dp[i] = i + nums[i];
            if(dp[i]>=n-1)
                return true;
            for(int j=i+1;j<=dp[i];j++) //更新所有可跳的位置, 代表我們可以到達的了
                dp[j] = 0;
        }
        return false;
    }

而上述的code只贏過 28% 的人, 是因為時間複雜度有O(n²)
因為除了保證一定要traverse整個陣列的O(n)以外, 我們在每個位子都又要多跑一個loop去update 所有 我們可以從現在的位子 跳到的位置們的dp值

那我們就可以想, 要怎麼樣來修改我們的code, 是不是有方法可以避免O(n²), 而只需要跑一次 O(n)?

從前面的code可以看到, 我們為了要紀錄現在位子可跳到的其他位子, 我們一個一個去update他們的dp value,

但換個角度想, 與其一個一個update, 我們是否可以只用一個變數reachable來表達我們最遠可以跳到的距離?
只要i 比reachable還小, 因為我們都保證一定可以跳到reachable了, 就代表我們一定也可以跳到i了!

public boolean canJump(int[] nums) {
        int n = nums.length;
        //dp[i] stores the farest we can jump from pos i
        int[] dp = new int[n]; 
        //n-1 is our target
        int reachable = 0;
        for(int i=0;i<n;i++)
        {
            if(reachable<i)
                return false;
            dp[i] = i + nums[i];
            reachable = Math.max(dp[i],reachable);
            if(reachable>=n-1)
                return true;
        }
        return false;
    }

在加了reachable變數後, 現在程式碼只需花2ms就可跑完, 贏過41%的人了
時間複雜度跟空間複雜度皆為O(n)

而我們其實又可以發現, 是不是其實dp array現在也可以省略
我們只要用reachable來一直紀錄最遠距離就好 不需知道我們是從誰可以跳到i

public boolean canJump(int[] nums) {
        int n = nums.length;
        //n-1 is our target
        int reachable = 0;
        for(int i=0;i<n;i++)
        {
            if(reachable<i)
                return false;
            reachable = Math.max(i+nums[i],reachable);
            if(reachable>=n-1)
                return true;
        }
        return false;
    }

這個code變成只需花1ms, 且贏過了 85%

而時間複雜度為 O(n), 空間複雜度: O(1)