檢查Python中是否可以透過指定長度的跳躍到達一個數字

假設我們處於起始位置 p，我們可以向任何方向（左或右）跳躍 d1 和 d2 個單位。我們必須找到透過從 p 跳躍到達位置 q 所需的最少步數。

因此，如果輸入類似於 p = 5，q = 10，d1 = 4，d2 = 3，則輸出將為 3，因為我們可以使用距離 4 向右跳躍兩次，然後我們可以到達位置 13，然後向左跳躍 3 個單位到達 10。

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

  • gcd_res := d1 和 d2 的最大公約數
  • 如果 (p - q) 不能被 gcd_res 整除，則
    • 返回 -1
  • que := 定義一個雙端佇列
  • visited := 一個新的集合
  • 將 (p, 0) 對插入佇列
  • 標記 p 為已訪問
  • 當 que 的大小 > 0 時，執行以下操作：
    • (point, step) := 佇列的第一個元素，並將其從 que 中刪除
    • 如果 point 與 q 相同，則
      • 返回 step
    • 如果 point + d1 未被訪問，則
      • 將 (point + d1, step + 1) 對插入 que
      • 標記 (point + d1) 為已訪問
    • 如果 point + d2 不在 visited 中，則
      • 將 (point + d2, step + 1) 對插入 que
      • 標記 (point + d2) 為已訪問
    • 如果 point - d1 不在 visited 中，則
      • 將 (point - d1, step + 1) 對插入 que
      • 標記 (point - d1) 為已訪問
    • 如果 point - d2 不在 visited 中，則
      • 將 (point - d2, step + 1) 對插入 que
      • 標記 (point - d2) 為已訪問

示例

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

from math import gcd
from collections import deque
def solve(p, d1, d2, q):
   gcd_res = gcd(d1, d2)
   if (p - q) % gcd_res != 0:
      return -1
   que = deque()
   visited = set()
   que.appendleft([p, 0])
   visited.add(p)
   while len(que) > 0:
      pair = que.pop()
      point, step = pair[0], pair[1]
      if point == q:
         return step
      if point + d1 not in visited:
         que.appendleft([(point + d1), step + 1])
         visited.add(point + d1)
      if point + d2 not in visited:
         que.appendleft([(point + d2), step + 1])
         visited.add(point + d2)
      if point - d1 not in visited:
         que.appendleft([(point - d1), step + 1])
         visited.add(point - d1)
      if point - d2 not in visited:
         que.appendleft([(point - d2), step + 1])
         visited.add(point - d2)
p = 5
q = 10
d1 = 4
d2 = 3
print(solve(p, d1, d2, q))

輸入

5, 4, 3, 10

輸出

True

更新於：2021年1月18日

65 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始
廣告