1 #include "000库函数.h"
2
3
4 //考虑当前最远能到什么地方，例如2, 3, 1, 1, 4，
5 //首先只考虑a[0] = 2，即最远可以到a[2]，然后从1到2中找下一个可到的最远点，
6 //即a[1]可以到达a[4]，此时找到结果，步数记录为2。若接着考虑，
7 //下一次应该从3 - 4里面找一个最远即a[4]可达a[8]（4 + 4）,
8 //再下一次从5 - 8中找最远
9 //20ms
10 class Solution {
11 public:
12 int jump(vector<int>& nums) {
13 if (nums.size() < 2)return 0;
14 int min = 0;
15 int a = 0, b = 0 + nums[0];//第一步和下一步的坐标
16 while (a < nums.size() - 1) {
17 min++;
18 int s = MAX(nums, a + 1, b); //在a,b中找到最远距离
19 a = b;
20 b = s;
21 }
22 return min;
23 }
24 int MAX(vector<int>& nums, int s, int t) {
25 int max = s + nums[s];
26 for (; s < nums.size() && s <= t; ++s) {
27 if (max < s + nums[s])
28 max = s + nums[s];
29 }
30 return max;
31 }
32 };
33
34 //博客解法 20ms
35 //解法的思想一样，找到跳的最远的那个
36 class Solution {
37 public:
38 int jump(vector<int>& nums) {
39 int res = 0, n = nums.size(), i = 0, cur = 0;
40 while (cur < n - 1) {
41 ++res;
42 int pre = cur;
43 for (; i <= pre; ++i) {
44 cur = max(cur, i + nums[i]);
45 }
46 if (pre == cur) return -1; // May not need this
47 }
48 return res;
49 }
50 };
51
52
53 class Solution {
54 public:
55 int jump(vector<int>& nums) {
56 int res = 0, n = nums.size(), last = 0, cur = 0;
57 for (int i = 0; i < n - 1; ++i) {
58 cur = max(cur, i + nums[i]);
59 if (i == last) {
60 last = cur;
61 ++res;
62 if (cur >= n - 1) break;
63 }
64 }
65 return res;
66 }
67 };
68 void T045() {
69 Solution s;
70 vector<int>v;
71 v = { 5,5,3,2,1,0,2,3,3,10,0,0 };
72 cout << s.jump(v) << endl << "**************" << endl;
73 v = { 2,0,2,4,6,0,0,3};
74 cout << s.jump(v) << endl << "**************" << endl;
75 v = { 2,3,0,1,4 };
76 cout << s.jump(v) << endl << "**************" << endl;
77 v = { 2,3,1,1,4 };
78 cout << s.jump(v) << endl << "**************" << endl;
79 }
