iT邦幫忙

5

[演算法][Python]演算法挑戰系列(8)-Jump Game

欸嘿嘿!哈囉!大家好!沒錯就是Python,不要懷疑自己的眼睛XD,因為小弟我最近在練習用Python玩爬蟲,所以可以看到發問了一些很菜的問題,也因為才剛學不久,所以想說來跳個tone,用新學的語言來嘗試這個演算法系列!這樣也像是呼應我前幾篇說的,其實所有的語言都可以試著用自己的想法來解題!不過相信各位大大們已經在先前此系列的留言區看過各種語言解題了,我算是第一次做突破,那就開始正文!

題目名稱:Jump Game
難易度:中
題目內容:輸入一個陣列,起點為第一個位置,終點是陣列的最後一個位置,從起點開始,每一個位置的值代表可以前進的距離,只要判斷能夠到達終點或超過就回傳True,如果沒辦法的話就回傳False,需要注意的是如果第一個位置無法前進到終點,可以接著從下個位置的值開始,到的了終點的話一樣回傳True,但如果下一個位置是0的話也無法再前進,所以回傳False(這題搞懂規則花了我很長的時間/images/emoticon/emoticon06.gif)。
例如:
1.傳入以下陣列:
[2,6,1,1,4]
step1.起點位置0的值為2所以可以前進到位置2值為1。
step2.來到了位置2的值為1所以可以前進到位置3值為1。
step3.來到了位置3的值為1所以可以前進到終點的位置4
所以會回傳True。

2.傳入以下陣列:
[3,2,1,0,4]
step1.起點位置0的值為3,所以前進到位置3但因為該值為0,無法再前進。
step2.起點位置0的值無法到終點,所以從下一個位置1開始,但因為值為2,還是會移動到位置3,無法前進。
step3.上一位置1的值無法到終點,所以從下一個位置2開始,但因為值為1,還是會移動到位置3,無法前進。
step4.上一位置2的值無法到終點,所以從下一個位置3開始,但因為值為0,無法前進。
因為不論從哪裡開始,都無法跨過第一個0,所以會回傳False。

接著是Python的解題初體驗,說真的在解題的時候一直很有衝動換成簡單等級的XD:

class Solution:
    def canJump(self, nums):
        '建立一個變數用來當目前在的位置'
        distance = 0
        '跑迴圈'
        for index in range(len(nums)):
            """
            如果現在跑的位置比目前在的地方還大,那就失敗了,
            代表目前在的地方已經在個位置遇到0無法再往前了。
            """
            if index > distance:
                return False
            """
            index是目前跑到第幾個索引,
            nums[index]是目前這個索引的值,也就是這次可以移動的距離,
            所以如果他目前到達的這個位置加上這次可以移動的距離,
            就是下一次他會在的位置。
            """
            thisDistance = index + nums[index]
            '如果下一次會到的位置比目前在的位置還遠就更新'
            if (thisDistance > distance):
                distance = thisDistance
            """
            更新完位置後,如果剛好到該陣列的最後一個位置或超過,就算成功。
            """
            if distance >= len(nums):
                return True
        '如果再迴圈內沒有進到False就回傳True'
        return True

接著分享一下執行成績,大概48ms左右:
https://ithelp.ithome.com.tw/upload/images/20180624/20106935vJqNcXiAVq.jpg
然後我真的很想要分享其他大大的解法,但是以我目前的程度實在還無法理解我看到討論區的邏輯/images/emoticon/emoticon02.gif,所以原諒我這次沒有分享其他高手的解法,但是我真的看到很厲害的簡潔答案+.+,之後有機會我再把他補上來!還請各位大大見諒!也因為還不熟Python,不曉得以上會不會有更好的寫法!如果有任何建議,或是有什麼問題,再麻煩各位大大留言告訴我,我會盡快修正,也歡迎大家跟我一起來挑戰各種題目XD,一個人很孤單,但是大家一起做就會覺得很酷!今天文章到這邊,謝謝觀賞/images/emoticon/emoticon41.gif


2 則留言

1
fysh711426
iT邦新手 1 級 ‧ 2018-06-24 20:37:30

小弟最近也想學 Python,剛好用這題來進入 Python 的世界,不過因為是不熟的程式語言,所以解題過程中採了不少坑,也 Google 了不少資料,寫完後覺得有所進步,感謝大大又再拖慢效能的題目。

在解題過程中,小弟學到一個教訓,
就是看完題目後,要再多想個五分鐘在開始,不要馬上動手,
因為一開始看完題目,小弟直覺就是寫一個遞迴去繞所有結果,
沒有仔細去想就開始寫了,沒想到寫完程式效能奇差無比,
排在 16.24% 的地方,覺得太丟臉了一開始不敢放上來。
/images/emoticon/emoticon16.gif

效能奇差版本,時間複雜度應該是 O(2N) 吧,還不太會看,而且因為用遞迴,函數的呼叫又再拖慢效能。

class Solution:
    def canJump(self, nums):
        return self._jump(0, len(nums)-1, nums, {})

    def _jump(self, current, end, nums, map):
        # 如果走到最後位置回傳True
        if current == end:
            return True
        # 將當前位置設為已走過
        map[current] = 1
        
        # 往下走
        idx = min(current+nums[current], end)
        while idx >= 0:
            # 已走過的索引後面的也一定會走過
            if idx in map:
                break
            if self._jump(idx, end, nums, map):
                # 已走到終點回傳 True
                return True
            idx=idx-1

        # 未走到終點回傳 False
        return False

經過一陣掙扎修改後還是沒有改善,決定重新看一遍題目,
看完後發現自己把問題複雜化了,沒有抓到重點。

這題解題重點在於:

  1. 找到 0
  2. 確認該 0 無法被跳過

只要有 0 無法被跳過就無法到達終點,反之則一定可以到達終點,
改完後上傳,結果總算比較滿意了。
/images/emoticon/emoticon37.gif

新版本時間複雜度只有 O(N) 快非常多。

class Solution:
    def canJump(self, nums):
        # 紀錄目前最大可到達的索引位置
        maxIndex = 0
        flag = True

        for index in range(0, len(nums)-1, 1):
            num = nums[index]
            # 如果是 0,且無法被跳過,表示無法到達終點
            if num == 0 and index >= maxIndex:
                flag = False
                break
            # 比較當前可到達索引位置和最大可到達索引位置
            if index+num > maxIndex:
                maxIndex = index+num
        return flag

https://ithelp.ithome.com.tw/upload/images/20180624/20106865rRscYWWVZK.jpg


看完大大的解法發現,下面這段程式好像沒有作用,

'直接從下一次的位置開始跑,就不用跑多餘的流程'
index = thisDistance

如果假設上面的邏輯正確執行,下面的測試資料,是不是結果會是錯誤的。

[2,3,1,0,0]

/images/emoticon/emoticon19.gif

不過目前大大的程式執行結果是正確的,因為 index 沒有往前跳,還是跑完了整個 List。

看更多先前的回應...收起先前的回應...

!!!所以他不會改變到index的值嗎/images/emoticon/emoticon04.gif
我下班回去測試看看再回覆大大,
謝謝你!!

對耶!!
剛剛試了一下發現他會略過[2,3,1,0,0]的3,導致跳到1就失敗了!!
其實那一句是我第一次執行成功後再加上去的,
沒想到反而弄巧成拙/images/emoticon/emoticon20.gif
我以後還是再精神好的時候打文章好了XD
那天已經敲到一個神遊狀態了,哈哈哈,
多虧fysh711426大大一個神救援/images/emoticon/emoticon32.gif

剛剛看了一下大大的做法也和我有點類似,
都是去看每一個位置能到達的最多距離是多少,
然後如果在途中遇到0就False
覺得很厲害!剛進入可以做出兩種解答!
我一開始經過了無數次失敗才生出兩個版本,
結果後來自以為改良的版本還是錯的XD

話說回來,
我們之後可以一起分享學Python歷程XD

哈哈哈,我也是採了很多坑才寫出來,前前後後花了將近半天的時間。
/images/emoticon/emoticon13.gif

恩我的作法和您類似,最慢的情況下要跑 N 次,
不過如果 0 出現在很前面 break 離開的話,
後面的就可以不用跑。

Python 的話之後會分享心得,主要是想學習深度學習的東西,
不過不知道學不學得起來。
/images/emoticon/emoticon16.gif

哈哈哈,忘了問

剛剛試了一下發現他會略過[2,3,1,0,0]的3,導致跳到1就失敗了!!

這個是用程式測試嗎,還是用推想的?

我用另外一個變數來代替index下去跑的XD
之後就去print那個變數來觀察程式跑的方式,
晚上我可以在把測試的程式碼放上來!

了解 /images/emoticon/emoticon41.gif

是想說有沒有denug模式可以用嗎XD

你習慣哪個開發工具?
我是用 VSCode 可以 debug。
/images/emoticon/emoticon37.gif

哈哈哈,抱歉昨天一回家就睡死了,
今天早上還突然驚醒/images/emoticon/emoticon04.gif
我也是用VSCode!!但是我沒有用過他debug,哈哈,
通常演算法的問題,我都直接在那個頁面用print讀他的流程。

1
Neish
iT邦研究生 5 級 ‧ 2018-06-25 08:50:03

請問大大 這些題目來源在哪裡?

我也是初入Python的新手

而且還有解題後的效能判斷

感覺這還蠻有趣的

看更多先前的回應...收起先前的回應...

個人在學階段是透過這線上平台來玩的
https://zerojudge.tw/
可以參考看看,裡面題目都挺不錯的

Neish iT邦研究生 5 級‧ 2018-06-25 09:30:49 檢舉

/images/emoticon/emoticon12.gif

我是從這裡找的題目哦!
https://leetcode.com/problemset/algorithms/

Neish iT邦研究生 5 級‧ 2018-06-25 13:34:39 檢舉

謝謝分享!
/images/emoticon/emoticon41.gif

不會啦!
有功大家練XD

我要留言

立即登入留言