Jump Game I & II
in LeetCode with 0 comment

Jump Game I & II

in LeetCode with 0 comment
虽然是 hard 类的题目,但其实也很简单。不过代码如果想要既美观又高效,可能就要费点功夫了。题目链接: Jump Game, Jump Game II

原始代码

这个是我写的Jump 2的代码,Jump 1 和 2的代码基本就是一回事。

思路也比较直接,用max_pos记录从当前节点开始,可以到达的最远位置(end 或者max_pos)

若最远位置已经超出长度,那么直接返回就行了。

对于Jump 1,略微修改下代码,检测step的长度,如果step的数量超过数组长度,那么肯定是走重复了。

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums[0] == 0||nums.size()==1)
            return 0;
        int step = 0, max_pos = 0, temp, i;

        while (max_pos < nums.size()) {
            temp = 0;
            int start = max_pos + 1, end = max_pos + nums[max_pos] + 1;
            if (end > nums.size() - 1) {
                step++;
                break;
            }
            for (i = start; i < end; i++) {
                if (temp < i + nums[i]) {
                    temp = i + nums[i];
                    max_pos = i;
                }
            }

            step++;
        }

        if (max_pos >= nums.size()) {
            step++;
        }

        return step;
    }
};

可以看到这个代码比较挫,看起来就不够美观,于是到dicuss 看了看别的大佬的答案,感觉打开了新世界的代码..

Jump 2 的简短代码

class Solution {
public:
    int jump(int A[], int n) {
        int ret = 0;
        int last = 0;
        int curr = 0;
        for (int i = 0; i < n; ++i) {
            if (i > last) {
                last = curr;
                ++ret;
            }
            curr = max(curr, i+A[i]);
        }

        return ret;
    }
};

比如就是我们题目中的[2,3,1,1,4]。

初始状态是这样的:cur表示最远能覆盖到的地方,用红色表示。
last表示已经覆盖的地方,用箭头表示。它们都指在第一个元素上。

40571-lq9r8e94e4.png

接下来,第一元素告诉cur,最远咱可以走2步。于是:

81857-ei0vq2byiph.png

下一循环中,i指向1(图中的元素3),发现,哦,i小于last能到的范围,于是更新last(相当于说,进入了新的势力范围),步数ret加1.同时要更新cur。因为最远距离发现了。

96095-1voet236t1i.png

接下来,i继续前进,发现i在当前的势力范围内,无需更新last和步数ret。更新cur。

35157-7wejnffz8jf.png

i继续前进,接下来发现超过当前势力范围,更新last和步数。cur已然最大了。

90959-2e921sk0235.png

最后,i到最后一个元素。依然在势力范围内,遍历完成,返回ret。

91676-owx1lrbnvxb.png

Jump 1 的简短代码

本题用一个数 reach 表示能到达的最远下标,一步步走下去,

如果发现在 reach 范围之内某处能达到的范围大于 reach,

那么我们就用更大的范围来替换掉原先的 reach,这样一个局部的最优贪心策略,在全局看来也是最优的

因为 局部能够到达的最大范围也是全局能够到达的最大范围:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int reach = nums[0];
        for (int i = 1; i < nums.size() && reach >= i; i++)
            if (i + nums[i] > reach) reach = i + nums[i];  //贪心策略
        return reach >= (nums.size() - 1) ? true : false;
    }
};

小结

Jump 2 的代码还是蛮神奇的...有点意思.

Responses

From now on, bravely dream and run toward that dream.
陕ICP备17001447号