Chương trình kiểm tra có thể đến cuối danh sách bắt đầu từ k trong Python

Cho một danh sách số nums và một số k. Nếu bắt đầu tại chỉ số k và tại bất kỳ chỉ số i nào, ta có thể đi sang trái hoặc sang phải đúng nums[i] bước. Kiểm tra xem có thể đến cuối danh sách hay không.

Ví dụ, nếu đầu vào là nums = [0, 0, 2, 1, 3, 3, 1, 1], k = 2, thì đầu ra là True, vì bắt đầu tại chỉ số 2, nhảy đến chỉ số 4 rồi nhảy đến chỉ số cuối 7.

Các bước giải quyết:

• n := kích thước của nums.
• visited := danh sách kích thước n khởi tạo 0.
• tovisit := danh sách chứa k.
• Trong khi độ dài tovisit > 0:
  • Lấy phần tử cuối của tovisit gán cho i và xóa nó.
  • Nếu i == n-1, trả về True.
  • Nếu visited[i] != 1:
    • visited[i] = 1.
    • up = i + nums[i], down = i - nums[i].
    • Nếu up < n, thêm up vào tovisit.
    • Nếu down >= 0, thêm down vào tovisit.
• Trả về False.

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        visited = [0] * n
        tovisit = [k]
        while len(tovisit) > 0:
            i = tovisit.pop()
            if i == n - 1:
                return True
            if visited[i] != 1:
                visited[i] = 1
                up = i + nums[i]
                dn = i - nums[i]
                if up < n:
                    tovisit.append(up)
                if dn >= 0:
                    tovisit.append(dn)
        return False

ob = Solution()
nums = [0, 0, 2, 1, 3, 3, 1, 1]
k = 2
print(ob.solve(nums, k))

Đầu vào

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

Đầu ra

True