Giả sử chúng ta có một mảng các số nguyên không âm; ban đầu chúng ta được định vị ở chỉ mục đầu tiên của mảng. Mỗi phần tử trong mảng đã cho đại diện cho độ dài bước nhảy tối đa tại vị trí đó. Chúng tôi phải xác định xem chúng tôi có khả năng đạt đến chỉ số cuối cùng hay không. Vì vậy, nếu mảng giống như [2,3,1,1,4], thì kết quả đầu ra sẽ là true. Điều này giống như nhảy một bước từ vị trí 0 đến 1, sau đó ba bước từ vị trí 1 đến cuối.
Hãy để chúng tôi xem các bước -
- n:=độ dài của mảng A - 1
- cho i:=n - 1, giảm xuống -1
- nếu A [i] + i> n, thì n:=i
- trả về true khi n =0, ngược lại là false
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution(object): def canJump(self, nums): n = len(nums)-1 for i in range(n-1,-1,-1): if nums[i] + i>=n: n = i return n ==0 ob1 = Solution() print(ob1.canJump([2,3,1,1,4]))
Đầu vào
[2,3,1,1,4]
Đầu ra
True