minJumping
Cho một mảng arr có độ dài n, chỉ chứa các số 1 và 0. Số 0 thể hiện một ô có thể đứng trên đó. Số 1 thể hiện một chướng ngại không thể đứng trên đó.
Một bước nhảy của bạn được tối đa 2 ô.
Ban đầu bạn ở ô số 0, đích ở ô (n-1). Đầu vào luôn đảm bảo có thể tới được đích. Hãy tìm số lượt di chuyển nhỏ nhất để tới được đích.
Ví dụ:
- Với
arr = [0,0,1,0,0,1,0]. Bạn có cách đi0->1->3->4->6. Do đómin_jumping(arr) = 4.
Đầu vào/Đầu ra:
-
[Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
-
[Đầu vào] vector<int> arr
2 <= n <= 10^6arr[0] = arr[n-1] = 0arr[i] = 0 | arr[i] = 1 -
[Đầu ra] Integer
Số bước nhảy nhỏ nhất để tới được đích.
Post Comment