Giả sử chúng ta có một danh sách các số được gọi là num trong đó mỗi số hiển thị số bước nhảy tối đa mà chúng ta có thể thực hiện; chúng tôi phải kiểm tra xem chúng tôi có thể đạt đến lần bắt đầu lập chỉ mục cuối cùng ở chỉ số 0 hay không.
Vì vậy, nếu đầu vào giống như nums =[2,5,0,2,0], thì đầu ra sẽ là True, vì chúng ta có thể nhảy từ chỉ mục 0 sang 1, sau đó nhảy từ chỉ mục 1 đến cuối.
Để 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
-
arr:=một mảng có kích thước n và điền bằng false
-
arr [n - 1]:=Đúng
-
đối với tôi trong phạm vi n - 2 đến 0, giảm 1, thực hiện
-
arr [i]:=true nếu bất kỳ một trong số arr [từ chỉ mục i + 1 đến i + nums [i]] là true
-
-
return arr [0]
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): n = len(nums) arr = [False] * n arr[n - 1] = True for i in range(n - 2, -1, -1): arr[i] = any(arr[i + 1 : i + nums[i] + 1]) return arr[0] ob = Solution() nums = [2,5,0,2,0] print(ob.solve(nums))
Đầu vào
[2,5,0,2,0]
Đầu ra
True