在Python中检查我们是否可以通过石头或无法通过河流

在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]中的每个跳跃,做以下操作
    • 如果跳跃>= 1,则
      • next_pos:=跳跃+ pos
      • 如果next_pos在A中且check(next_pos,jump)为true,则
      • 返回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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程