122.买卖股票的最佳时机II ,55. 跳跃游戏 ,45.跳跃游戏II

简介: **简介:**本文介绍了三道经典算法题的解法,涵盖贪心算法的核心思想与应用。 1. **买卖股票的最佳时机 II**:通过收集每天的正利润实现最大收益,局部最优推导全局最优。 2. **跳跃游戏**:利用贪心算法扩展覆盖范围,判断是否能到达终点。 3. **跳跃游戏 II**:基于最大覆盖范围计算最小跳跃次数,平衡当前步与下一步的覆盖距离。 三道题目均采用贪心策略,通过优化局部选择实现整体最优解,代码简洁高效,时间复杂度低,适合解决类似问题。

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

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1:

输入:prices = [7,1,5,3,6,4]

输出:7

解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。

    随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。

    总利润为 4 + 3 = 7 。

示例 2:

输入:prices = [1,2,3,4,5]

输出:4

解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。

    总利润为 4 。

示例 3:

输入:prices = [7,6,4,3,1]

输出:0

解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。

提示:

1 <= prices.length <= 3 * 104

0 <= prices[i] <= 104

思考历程与知识点:  

我们需要收集每天的正利润就可以,收集正利润的区间,就是股票买卖的区间,而我们只需要关注最终利润,不需要记录区间。

那么只收集正利润就是贪心所贪的地方!

局部最优:收集每天的正利润,全局最优:求得最大利润。

局部最优可以推出全局最优,找不出反例,试一试贪心

题解:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
};

 题目:55. 跳跃游戏

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1:

输入:nums = [2,3,1,1,4]

输出:true

解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]

输出:false

解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

提示:

1 <= nums.length <= 3 * 104

0 <= nums[i] <= 105

思考历程与知识点:  

贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。

题解:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true; // 只有一个元素,就是能达到
        for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};

 题目:45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]  

i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是  

2

。

    从下标为 0 跳到下标为 1 的位置,跳  

1

步,然后跳  

3

步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]

输出: 2

提示:

1 <= nums.length <= 104

0 <= nums[i] <= 1000

题目保证可以到达 nums[n-1]

思考历程与知识点:  

本题相对于55.跳跃游戏 (opens new window)还是难了不少。

但思路是相似的,还是要看最大覆盖范围。

本题要计算最小步数,那么就要想清楚什么时候步数才一定要加一呢?

贪心的思路,局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一。整体最优:一步尽可能多走,从而达到最小步数。

思路虽然是这样,但在写代码的时候还不能真的能跳多远就跳多远,那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候,要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最小步数!

这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点。

题解:

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标(相当于加油了)
                if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点,不用做ans++操作了,直接结束
            }
        }
        return ans;
    }
};


相关文章
|
存储 编解码 数据可视化
【Matplotlib】figure方法之图形的保存
【Matplotlib】figure方法之图形的保存
1637 1
|
5月前
|
人工智能 前端开发 Java
AGENTS.md完整落地实践:一份文件翻倍AI编码效率实操指南
在AI编程工具广泛普及的当下,Cursor、Claude Code、Copilot、各类智能体工具各自使用独立规则文件,团队需要维护多套配置,切换工具时重复同步编码规范,AI对项目架构、私有组件、构建流程一无所知,产出代码大量不符合团队标准,反复人工修改大幅拉低开发效率。AGENTS.md作为统一行业标准,完美解决配置碎片化、AI缺少项目上下文的痛点,仅在仓库根目录放置一份Markdown文件,即可让全部AI编码工具统一读取项目规则、架构、构建命令,搭配配套工程脚本,实现「AI读懂项目、写完自动自检、自主验证功能」完整闭环,显著提升AI编码产出质量与整体研发效率。本文结合Spring Boot
1060 0
|
运维 监控 数据可视化
故障发现提速 80%,运维成本降 40%:魔方文娱的可观测升级之路
魔方文娱携手阿里云构建全栈可观测体系,实现故障发现效率提升 80%、运维成本下降 40%,并融合 AI 驱动异常检测,迈向智能运维新阶段。
852 89
|
10月前
|
人工智能 Rust 自然语言处理
Qoder NEXT 测评:不止是代码补全,而是“会思考的编程搭档”
本次测评聚焦三大核心问题: 能否超越传统 FIM,支持真实开发中的结构化编辑? 编辑建议是否精准、符合开发者意图? 是否具备持续进化能力,越用越好?
|
存储 人工智能 边缘计算
Gartner 魔力象限:数据中心网络交换机 2025
Gartner 魔力象限:数据中心网络交换机 2025
1219 0
Gartner 魔力象限:数据中心网络交换机 2025
|
10月前
|
人工智能 UED
Qoder NEXT有妙用:当"反向思维"遇上AI编程助手
博士生实测Qoder NEXT新功能NES,意外发现“反向思维”妙用:通过AI高亮提示反推配置逻辑,轻松实现导航栏排序。无需代码基础,几分钟完成优化,AI不仅提供建议,更生成完整方案。技术门槛降低,效率翻倍,探索充满乐趣。#AI编程 #低代码
353 5
|
安全 API 网络安全
API安全危机四伏!开发者掌握这“十八般武艺”才能破局?
在数字化时代,API作为连接应用的核心枢纽,其安全性至关重要。本文深入解析API安全攻防实战技巧,涵盖数据传输加密、身份认证、输入验证、速率限制、日志监控、API网关应用及持续安全实践等七大防御策略,帮助开发者全面掌握保护数据接口的关键技能,构筑坚实的安全防线。
849 100
|
10月前
|
NoSQL 关系型数据库 分布式数据库
2026年阿里云数据库产品活动解析:云数据库 RDS、云原生数据库 PolarDB等数据库特惠
阿里云数据库活动为新用户提供全方位优惠,覆盖关系型、NoSQL及数据仓库产品。RDS新用户享指定规格3折/年或全系6折/年,如MySQL基础版100GB存储首年2232元起;PolarDB新用户全系规格6折/年,分布式版低至2.8折;Redis开源版2GB倚天版399元/年起,MongoDB指定规格1999元/年起;AnalyticDB MySQL版首月6折。活动涵盖从基础到企业级需求,助力企业以高性价比构建数据平台,降低上云门槛。
|
12月前
|
人工智能 程序员 开发者
用Qoder自动生成开源项目的说明书(wiki),新人爱看,老人爱用
程序员晚枫分享AI编程新利器Qoder:一键自动生成中文项目Wiki,解决文档维护难题。支持代码同步更新,降低学习成本,助力开源项目发展。12月第二周将在重庆阿里中心分享实战经验,欢迎交流!
2913 1
用Qoder自动生成开源项目的说明书(wiki),新人爱看,老人爱用
|
Linux
Linux下使用ls查看文件颜色全部为白色的解决方法,以及Linux中文件颜色介绍
Linux下使用ls查看文件颜色全部为白色的解决方法,以及Linux中文件颜色介绍
1875 3