检查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 次浏览

开启你的职业生涯

完成课程获得认证

开始
广告