代码随想录刷题|LeetCode 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

简介: 代码随想录刷题|LeetCode 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

122.买卖股票的最佳时机II

题目链接:

思路


  要使用贪心算法,首先要能把问题分解成局部最优,然后才能找到合适得贪心策略,按照一般贪心算法的四步分析这道题目


       首先要明确条件:

               只有一只股票

               当前只有买股票和卖股票的操作

               当天可以买,可以卖

               想要获得利润只要要以两天为单位


       1、将问题分解成若干个子问题

               假设在第1天买入股票,在第4天买出股票所获得的利润更大,那么就是 prices[3] - prices[0] ,这个式子可以分解成(prices[3] - prices[2])+(prices[2] - prices[1])+(prices[1] - prices[0]),这样就把 全局利润最大  分解成 每两天的 利润最大


       2、找到合适的贪心策略

               但是如果收集每一天的利润,那可能会包含负利润的情况,那对于这种情况只要不收集就可以,只收集获取利润的两天

042dba4bffed4956a6d840f2853f6175.png

        3、求解每个子问题的最优解

               当天减去前一天大于0 就是最优解


       4、将局部最优解堆叠成全局最优

               筛选 加入


       所以这道题目的

               局部最优:每天获得的正利润

               全局最优:整个区间获得的最大利润


买卖股票的最佳时机||

class Solution {
    public int maxProfit(int[] prices) {
        // 总利润
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i -1] , 0);
        }
        return  result;
    }
}


55. 跳跃游戏

题目链接:力扣

思路


  真的很难想到思路,如果想分析清楚各种情况的跳跃是不太可能的,最关键要想到:其实跳几步是无所谓的,关键在于可跳的覆盖范围


       在可覆盖的范围中,不论是怎么跳跃,都是可以跳跃到的,所以最终转换为跳跃范围究竟可不可以覆盖终点


       局部最优:每次取最大跳跃步数(获取当前可以覆盖的最大范围)

       全局最优:可不可以覆盖到重点


跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        // 可以覆盖到的范围
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(i + nums[i],cover);
            if (cover >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

45.跳跃游戏II

题目链接:https://leetcode.cn/problems/jump-game-ii/submissions/

思路

  本题要计算的是最小步数,关键在于在什么情况下来记录步数。如果每一个下标跳跃的步数都没有跳满,那势必不是最小的步数,所以要尽量每一步跳最大的步数


       如果跳过了下标的最大步数,还没有到达重点,那么就不要再前进一步


       思路很巧妙,代码简单也很巧妙


       遍历数组的时候,要获取当前下标数字可覆盖的最大范围

               1.如果这个范围是可以覆盖重点的,那就代表只需要跳这个下标代表的步数就可以,这代表1步

               2.如果这个范围不可以覆盖到重点,那就要看看有没有目前范围内有没有可以覆盖到的,如果遍历完还没有,那就说明继续往前扩大范围


跳跃游戏||

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        // 记录跳跃的次数
        int count = 0;
        // 当前的覆盖的最大区域
        int curDistance = 0;
        // 可获得的最大覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            // 获取可获得的最大覆盖区域
            maxDistance = Math.max(maxDistance,i + nums[i]);
            if (maxDistance >= nums.length - 1) {
                count++;
                break;
            }
            //走到当前最大区域 还没有到达终点
            if (i == curDistance) {
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}
相关文章
|
2月前
|
算法
Leetcode第45题(跳跃游戏II)
这篇博客文章讨论了如何使用贪心算法解决LeetCode第45题“跳跃游戏II”,目的是找到使用最少跳跃次数到达数组末尾的策略。
79 8
Leetcode第45题(跳跃游戏II)
|
4月前
|
算法
LeetCode第55题跳跃游戏
LeetCode第55题"跳跃游戏"的解题方法,通过记录当前最远可达到的位置并判断每个位置是否可达以及能否到达末尾,有效解决了跳跃至数组末尾的可行性问题。
LeetCode第55题跳跃游戏
|
4月前
|
算法 Python
【Leetcode刷题Python】309. 最佳买卖股票时机含冷冻期
解决LeetCode上309题“最佳买卖股票时机含冷冻期”的Python代码示例,利用动态规划方法计算在含有冷冻期约束下的最大利润。
45 1
|
2月前
Leetcode第55题(跳跃游戏)
LeetCode第55题“跳跃游戏”要求判断在一个非负整数数组中,从第一个位置出发,是否能够到达最后一个位置,其中每个位置的元素代表可跳跃的最大长度。
31 0
|
4月前
|
算法 Python
【Leetcode刷题Python】121. 买卖股票的最佳时机
解决LeetCode上121题“买卖股票的最佳时机”的Python代码示例,采用一次遍历的方式寻找最佳买卖时机以获得最大利润。
63 1
|
4月前
|
算法
leetcode188 买卖股票的最佳时机IV
leetcode188 买卖股票的最佳时机IV
65 0
|
4月前
|
算法
LeetCode第45题跳跃游戏 II
LeetCode第45题"跳跃游戏 II"的解题方法,通过一次循环和选择每个位置的最大可跳距离,有效减少了跳跃次数,简化了问题。
|
4月前
|
算法 Python
【Leetcode刷题Python】714. 买卖股票的最佳时机含手续费
提供了两种解决买卖股票最佳时机含手续费问题的Python实现方法:贪心算法和动态规划算法。
49 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2