iT邦幫忙

1

【小馬的LeetCode練功坊】55. Jump Game

參考題目: LeetCode- 55. Jump Game

題目敘述:
給你一個陣列,全是非負整數,代表你能夠跳躍的最長距離,請判斷能否跳到最後一格

例1:
Input: [2,3,0,0,4]
Output: true
解釋: 先從index0跳到index1,再跳三格即抵達最後格

例2:
Input: [3,2,1,0,4]
Output: false
解釋: 不論如何最遠只能跳到index3,然後就動不了

想法:
貪婪選擇下一步可以去的位置中,所能抵達的最遠距離的位置,
因為下一步所能抵達的最遠距離涵蓋其它的選擇,如果所能抵達位置最遠距離的那些位置都無法解決問題,其它選擇自然也不行

<c++程式碼>:

class Solution {
public:
    bool canJump(vector<int>& nums) {     
        int pos = 0; //目前所在index
        while (pos < nums.size()-1){
            if(nums[pos]==0)
                return false;
            int far_idx = pos, far_place = 0;
            for(int i=pos+1; i< min(pos+1+nums[pos], (int)nums.size()); i++){
                if(i+nums[i]>=far_place){
                    far_idx = i;
                    far_place = i+nums[i];
                }
            }
            pos = far_idx;    
        }
        return true;
    }
};

<python程式碼>:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        pos = 0 #目前所在index
        while pos < len(nums)-1:
            if nums[pos]==0:
                return False
            far_idx, far_place = pos,0
            for i in range(pos+1, min(pos+1+nums[pos], len(nums))):
                if i+nums[i]>=far_place:
                    far_idx, far_place = i, i+nums[i]
            pos = far_idx
        return True

心得: c++的執行速度真的比python快

這邊跟大家分享寫leetcode以來有感受到的一件事,
邏輯相同的程式碼,
c++的執行速度真的比python快。
以這一題來說,python的執行時間大約為100ms,
c++的執行時間只要24ms


尚未有邦友留言

立即登入留言