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

开启你的职业生涯

完成课程获得认证

开始学习
广告