在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
- 如果跳跃>= 1,则
- 返回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