leetcode_jump_game_ii

发表于

难度：Hard

解题思路：用一个数组，保存当前index的最小步数。则下一个index的最小步数为前面所有元素的最小步数＋1的最小值，前提是可以一步跨过来。题目有几个case不好过，需要优化。

[1,1,1,1......1,1]很多1的情况，需要查找最大步数。
[25550,24449,....2,1,1,0]这个情况，需要明确1是最小步数，无需过多检查。

代码如下

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
35
36
class Solution {
public:
    int jump(vector<int>& nums) {
        int max_jump = INT_MIN;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > max_jump)
                max_jump  = nums[i];
        }
        vector<int> least_steps(nums.size());
        for(int i = 0; i < nums.size();i++)
        {
            least_steps[i] = 0;
            int least_step = INT_MAX;
            int j_start = (i - max_jump) < 0 ? 0 : (i-max_jump);
            // cout<<j_start<<" ";
            for(int j = j_start; j < i; j++)
            {
                // cout<<j<<" ";
                int standard_jump_step =  i- j;
                if(nums[j] >= standard_jump_step)
                {
                    // cout<<j<<" "<<least_steps[j]<<endl;
                    least_step = min(least_steps[j]+1,least_step);
                }
                if(least_step == 1)
                    break;
                // if(standard_jump_step > max_jump)
                //     break;
            }
            if(least_step != INT_MAX)
                least_steps[i] = least_step;
        }
        return least_steps[nums.size()-1];
    }
};

运行结果：16ms，超过25.66%