1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
// 45. Jump Game II
#include <stdio.h>
/*
* you are given 0-indexed array of integers 'nums' of length
* 'n'. you are initially positioned at 'nums[0]' each element
* 'nums[i]' represents the maximum length of forward jump from
* from index 'i'. in other words, you can jump to any
* 'nums[i + j]' where 0 <= j <= nums[i] and i + j < n
* return the minimum number of jumps to reach 'nums[n - 1]'.
*/
int jump(int *nums, int numsSize) {
if (numsSize < 2)
return 0;
if (nums[0] >= numsSize - 1)
return 1;
int cnt = 0, max = 0, min = 0;
for (int i = 0; i < numsSize - 1; i++) {
max = nums[i] + i > max ? nums[i] + i : max;
if (i == min) {
min = max;
cnt++;
}
}
return cnt;
}
int main() {
int nums1[] = {2, 3, 1, 1, 14}, ns1 = 5;
int nums2[] = {2, 3, 0, 1, 4}, ns2 = 5;
printf("%d\n", jump(nums1, ns1)); // expect: 2
printf("%d\n", jump(nums2, ns2)); // expect: 2
}
|