Giả sử chúng ta có một danh sách các số được gọi là num và một số khác k. Nếu chúng ta bắt đầu ở chỉ mục k và ở bất kỳ chỉ mục i nào, chúng ta có thể đi sang trái hoặc phải bằng số bước chính xác là nums [i]. Chúng tôi phải kiểm tra xem chúng tôi có thể đến cuối danh sách hay không.
Vì vậy, nếu đầu vào giống như nums =[0, 0, 2, 1, 3, 3, 1, 1] k =2, thì đầu ra sẽ là True, như thể chúng ta bắt đầu ở chỉ mục 2, sau đó chuyển đến chỉ mục 4 và sau đó chuyển đến chỉ mục cuối cùng 7.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−
-
n:=kích thước của nums
-
đã thăm:=một danh sách có kích thước n và điền bằng 0
-
tovisit:=danh sách kích thước 1 và chèn k vào đó
-
trong khi kích thước của tovisit <0, do
-
i:=phần tử cuối cùng từ tovisit và xóa nó khỏi tovisit
-
nếu tôi giống với n-1, thì
-
trả về True
-
-
nếu lượt truy cập [i] không giống với 1, thì
-
đã ghé thăm [i]:=1
-
lên:=i + nums [i]
-
xuống:=i - nums [i]
-
nếu lên
-
chèn lên ở cuối tovisit
-
nếu xuống> =0 thì
-
chèn xuống ở cuối tovisit
-
-
trả về Sai
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn−
Ví dụ
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=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