专栏首页蜉蝣禅修之道LeetCode之Jump Game II

LeetCode之Jump Game II

  • 在LeetCode上刷的第三题,尝试了几种方法,最后还是选择贪心,复杂度为O(n),个人感觉有不少的收获。
  • 该题的题目是这样的,给定一个非负整数数组,每个元素代表着在当前位置最大能跳多少步,而我们的目标是从第一个位置开始,通过最少的步数到达最后一个位置。例如,给定数组是 A = [2,3,1,1,4],则只需两步就能到达终点(第一个位置跳1步到达第二个位置,第二个位置上跳三步到达最后一个位置)。
  • 首先,我想着用动态规划做的,设f(n)为从n位置出发到达终点所需的最少步数,那么f(n)的表达式为
  • 然而,这个算法的复杂度可能是O(n2)O(n^2),因为它重复算了一些没用的元素的步数,而且使用递归不断重复压栈出栈性能也会有影响。
  • 然后,我接着想出另一种反向动态规划,首先遍历一次A,找出那些能一步到达终点的位置,在这些位置中选出最小的一个,以它作为新的终点继续上一步操作,直至最小的位置为0,算法结束。可惜,这种算法对于全是1的数组复杂度为O(n2)O(n^2),因为每次迭代我们都需要遍历一次数组。
  • 最后,还是利用贪心的思想,感觉自己一开始走了弯路,贪心照理说是第一个需要考虑的~,主要思想是,初始化scope为A[0],遍历的初始位置fromIndex为1,然后通过判断在fromIndex到scope范围内,找出新的最大的scope,如果新的scope大于终点的index,那么算法结束,否则fromIndex=原来scope+1,scope=新的scope,重新计算上一步。这样算法的复杂度就只是O(n)O(n),因为最坏的情况也是只需遍历一次数组就搞定了。
  • 因为才刚开始刷OJ,笔者目前仍然是算法的小白,不过通过这一题确实让我收获不少,知道了算法设计的考虑顺序和一些基本逻辑。希望对大家也会有所帮助。
class Solution {
public:
    int jump(vector<int>& nums) {
    if (nums.size() <= 1){
        return 0;
    }
    int firstNum = nums[0];
    if (firstNum == 0){
        return 0;
    }
    int scope = firstNum;
    int step = 0;
    int from = 1;
    while (scope < nums.size() - 1){
        int currentScope = scope;
        for (int i = from; i <= scope; i++){
            if (currentScope < i + nums[i])
                currentScope = i + nums[i];
        }
        step++;
        from = scope + 1;
        scope = currentScope;
    }
    return step + 1;
}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Next Permutation之字典序法

    forrestlin
  • Leetcode之Longest Valid Parentheses

    forrestlin
  • LeetCode之Longest Substring Without Repeating Characters

    forrestlin
  • LeetCode1 两数之和

    itlemon
  • LeetCode 215. Kth Largest Element in an Array(排序)

    题解:我们当然可以排序好了,之后,选择第K大的数字。但是这样做一点技术含量也没有。

    ShenduCC
  • Leetcode 16. 3Sum Closest

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode 75 Sort Colors

    Given an array with n objects colored red, white or blue, sort them so that obj...

    triplebee
  • 【每日一练】第001期--两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    会呼吸的Coder
  • LeetCode 217. Contains Duplicate

    ShenduCC
  • Array - 164. Maximum Gap

    Given an unsorted array, find the maximum difference between the successive elem...

    用户5705150

扫码关注云+社区

领取腾讯云代金券