Python程式檢查能否用石頭過河

假設我們有一個排序好的數字列表，稱為stones，它表示我們試圖穿越的河流上石頭的位置。要穿越河流，我們必須到達最後一個石頭。現在，在每一步中，我們可以跳躍 (k - 1, k, 或 k + 1) 步，其中 k 是最後一次跳躍的距離。我們必須檢查我們是否能夠穿越河流。

因此，如果輸入類似於 stones = [0, 1, 3, 4, 5, 6, 8, 9, 13]，則輸出為 True，因為我們可以從 0 開始，然後跳躍 1 個單位到達石頭 1，然後跳躍 2 個單位到達 3，然後跳躍 2 個單位到達 5，然後跳躍 3 個單位到達 8，最後跳躍 5 個單位到達 13，這是最終位置。

為了解決這個問題，我們將遵循以下步驟：

  • start := A[0]，end := A的最後一個元素
  • A := A所有唯一元素的集合
  • 定義一個函式 check()。這將採用 pos:= start，prev:= 0
  • 如果 pos 與 end 相同，則
    • 返回 True
  • 對於 [prev - 1, prev, prev + 1] 中的每個跳躍，執行以下操作：
    • 如果 jump >= 1，則
      • next_pos := jump + pos
      • 如果 next_pos 在 A 中並且 check(next_pos, jump) 為真，則
        • 返回 True
  • 返回 False
  • 從主方法呼叫 check() 並返回結果

示例 (Python)

讓我們看看下面的實現以更好地理解：

 線上演示

class Solution:
   def solve(self, A):
      start, end = A[0], A[-1]
      A = set(A)
      def check(pos=start, prev=0):
         if pos == end:
            return True
         for jump in [prev - 1, prev, prev + 1]:
            if jump >= 1:
               next_pos = jump + pos
               if next_pos in A and check(next_pos, jump):
                  return True
         return False
      return check()
ob = Solution()
stones = [0, 1, 3, 4, 5, 6, 8, 9, 13]
print(ob.solve(stones))

輸入

[0, 1, 3, 4, 5, 6, 8, 9, 13]

輸出

True

更新於：2020-12-12

294 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.