Прыжки по массиву

Question

Вам дан список неотрицательных чисел arr, а также номер позиции start в этом списке, на котором вы находитесь. Когда вы находитесь на индексе i вы можете прыгнуть к индексам i + arr[i] или i - arr[i]. Проверьте, сможете ли вы достичь любого индекса со значением 0 в списке.

Заметьте, что вы не можете выпрыгнуть за пределы списка.

Sample Input 1:

[4,2,3,0,3,1,2] 5

Sample Output 1:

True

Sample Input 2:

[3,0,2,1,2] 2

Sample Output 2:

False

Answer 1

def canReach(self, arr: list, start: int) -> bool:
    indx = start
    count = 0
    result= None
    while arr[indx] != 0:
        count += 1
        nextIndx = indx + arr[indx]
        prevIndx = indx - arr[indx]

        if count<len(arr):

            if nextIndx < len(arr):
                indx = nextIndx
            elif prevIndx >= 0:
                indx = prevIndx
        else: break

    if arr[indx] == 0: result = True
    else: result = False
    return result

Answer 2

Алгоритм на примере [1,0,1,1,1,1,1] 4

Решение

class Solution:
    def canReach(self, arr: list, start: int) -> bool:
        ln = len(arr)
        stack = [start]
        visited = set()

        while stack:
            i = stack.pop(0)
            if 0 <= i < ln and i not in visited:
                if arr[i] == 0:
                    return True

                visited.add(i)
                stack.append(i + arr[i])
                stack.append(i - arr[i])

        return False

БЛОГ НА HUSL

Прыжки по массиву

Ответы (2 шт):