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 }