当前位置: 首页 > news >正文

LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II)

文章目录

  • 前置知识
  • 122.买卖股票的最佳时机II
    • 题目描述
    • 贪心-直观写法
    • 贪心-优化代码更简洁
  • 55. 跳跃游戏
    • 题目描述
    • 贪心-借助ability数组
    • 贪心-只用`int far`记录最远距离
  • 45.跳跃游戏II
    • 题目描述
    • 回溯算法
    • 贪心算法
  • 总结

前置知识

参考前文

参考文章:
LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)

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

题目描述

截图

LeetCode链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

贪心-直观写法

思路: 贪心算法
假设这个股票交易员有预知明天股票价格的能力;
当明天的价格大于今天的时候, 就买入/持有;
当明天价格下跌时, 就在今天抛售/不购买;
最后一天的时候如果手里还有, 就售出;

class Solution {
public:int maxProfit(vector<int>& prices) {int ans=0;if(prices.size()<=1)return ans;bool holding=false;for(int i=0; i<prices.size(); ++i){if(i==prices.size()-1){//最后一天, 手里还有股票if(holding)ans += prices.back();//卖出break;//不管咋样都要break了}if(prices[i+1] > prices[i] && !holding){//明天升值, 并且手里没有股票ans -= prices[i];//买入holding = true;}else if(prices[i+1] <= prices[i] && holding){//明天贬值, 并且手里有股票ans += prices[i];//卖出holding = false;}}return ans;}
};

贪心-优化代码更简洁

以上过程可以抽象为以下操作:
遍历整个prices序列, 只记录其中升序的部分的差值

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

55. 跳跃游戏

题目描述

在这里插入图片描述

LeetCode链接:https://leetcode.cn/problems/jump-game/description/

贪心-借助ability数组

创建并维护一个vector<bool> ability数组
从头开始遍历nums, 最开始ability[0]=true
然后如果ability[i]==true, 那么将ability[i]~ability[i+nums[i]]都为true
过程中发现某个ability[i]==false, 那么就为false

class Solution {
public:bool canJump(vector<int>& nums) {vector<bool> ability(nums.size(), false);ability[0] = true;for(int i=0; i<nums.size(); ++i){if(ability[i]){for(int j=i+1; j<=i+nums[i]; ++j){if(j>=nums.size())return true;;ability[j] = true;}}else{return false;}}return true;}
};

贪心-只用int far记录最远距离

用不到一个数组, 用一个far表示最远能到达的点就可以了

class Solution {
public:bool canJump(vector<int>& nums) {int far=0;for(int i=0; i<nums.size(); ++i){if(far >= nums.size()-1)return true;if(far>=i){far = max(far, i+nums[i]);}else{return false;}}return true;}
};

核心思想是: 不要纠结这次跳几步, 而是关注最远能跳到哪里

45.跳跃游戏II

题目描述

在这里插入图片描述

LeetCode链接:https://leetcode.cn/problems/jump-game-ii/description/

回溯算法

思路: 回溯算法
每一层的回溯过程就是在遍历自己从这一步跳出去, 可以跳的距离的所有可能性
终止条件是index>nums.size()-1, 或者nums[index]==0

class Solution {
private:int ans = INT_MAX;int cur = 0;void backtrack(vector<int>& nums, int index){if(index>=nums.size()-1){ans = min(ans, cur);return;}if(nums[index]==0)return;for(int i=nums[index]; i>0; --i){cur++;backtrack(nums, index+i);cur--;}return;}
public:int jump(vector<int>& nums) {backtrack(nums, 0);return ans;}
};

贪心算法

回溯法肯定是可以解决问题的, 但是奈何回溯的本质是遍历, 时间复杂度过高, 超出时间限制
所以老老实实用贪心吧:
和<55. 跳跃游戏>的核心思路是一样的, 都是尽量往远了跳, 但是这个又不能乱跳, 因为涉及到要不要ans++的问题

所以贪心的思路是: 先看一下这一步能跳多远, 如果可以满足要求, 就结束, 如果不能, 那么就再跳一步
具体的实现是: 用nextDistence记录在当前范围内, 再跳一步可以达到的最远结果;
当遍历达到了curDistence处时, 如果还没有到最后一位, 那么就转nextDistence

class Solution {
public:int jump(vector<int>& nums) {int ans = 0;if(nums.size()<=1)return ans;int nextDistence=0, curDistence=0;for(int i=0; i<nums.size(); ++i){nextDistence = max(nextDistence, i+nums[i]);if(i==curDistence){ans++;curDistence = nextDistence;if(nextDistence>=nums.size()-1)break;}}return ans;}
};

总结

贪心算法大概率就是没法把握, 甚至看起来是"千题千解", 尽量熟悉吧只能说, 如果之后遇到类似的题目了, 可以想起来最好.
实在不行的话或许只能用回溯和动态规划尝试了.

刚才的第二题, 说到不要纠结这次跳几步, 而是关注最远能跳到哪里, 或许也是某种人生哲学呢哈哈哈.
本质上我们或多或少的都在用贪心算法规划自己的人生.
(用贪心还算好了, 至少是当下和未来一部分时间内的最优, 还有不知道多少人是在后视镜开车呢)

本文参考:
买卖股票的最佳时机II
跳跃游戏
跳跃游戏II

相关文章:

LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II)

文章目录 前置知识122.买卖股票的最佳时机II题目描述贪心-直观写法贪心-优化代码更简洁 55. 跳跃游戏题目描述贪心-借助ability数组贪心-只用int far记录最远距离 45.跳跃游戏II题目描述回溯算法贪心算法 总结 前置知识 参考前文 参考文章&#xff1a; LeetCode刷题笔记【23】…...

游戏出现卡顿有哪些因素

一、服务器CPU内存占用过大会导致卡顿&#xff0c;升级CPU内存或者优化自身程序占用都可以解决。 二、带宽跑满导致卡&#xff0c;可以升级带宽解决。 二、平常不卡&#xff0c;有大型的活动的时候会卡&#xff0c;这方面主要是服务器性能方面不够导致的&#xff0c;性能常说…...

学习Bootstrap 5的第八天

目录 加载器 彩色加载器 实例 闪烁加载器 实例 加载器大小 实例 加载器按钮 实例 分页 分页的基本结构 实例 活动状态 实例 禁用状态 实例 分页大小 实例 分页对齐 实例 面包屑&#xff08;Breadcrumbs&#xff09; 实例 加载器 彩色加载器 在 Bootstr…...

vue中自定义指令

什么是指令 在Vue.js中&#xff0c;指令是一种特殊的 token&#xff0c;用于在模板中以声明式方式将响应式数据绑定到 DOM 元素上&#xff0c;从而实现与 DOM 元素的交互和操作。指令以 “v-” 前缀开始&#xff0c;后跟指令的名称&#xff0c;例如 v-model、v-bind 和 v-on。…...

Python:安装Flask web框架hello world

安装easy_install pip install distribute 安装pip easy_install pip 安装 virtualenv pip install virtualenv 激活Flask pip install Flask 创建web页面demo.py from flask import Flask app Flask(__name__)app.route(/) def hello_world():return Hello World! 2023if _…...

小程序点击复制功能制作

在wxml文件中添加一个按钮或需要点击的元素&#xff0c;并绑定点击事件监听器2 <button bindtap"copyText">点击复制</button> 2 在对应的js文件中定义点击事件处理函数&#xff0c;并在函数中调用小程序的API进行复制操作&#xff0c; copyText(e){co…...

20230909java面经整理

1.java常用集合 ArrayList动态数组&#xff0c;动态调整大小&#xff0c;实现List接口 LinkedList双向链表&#xff0c;实现list和queue接口&#xff0c;适用于频繁插入和删除操作 HashSet无序&#xff0c;使用哈希表实现 TreeSet有序&#xff0c;使用红黑树实现 HashMap无序&…...

常用的css命名规则

一、命名规则说明&#xff1a; 1&#xff09;、所有的命名最好都小写 2&#xff09;、属性的值一定要用双引号(“”)括起来 3&#xff09;、给图片加上alt标签 4&#xff09;、尽量使用英文命名原则 5&#xff09;、尽量不缩写&#xff0c;除非一看就明白的单词 二、相对网页外…...

【Linux编程Shell自动化脚本】03 shell四剑客(find、sed、grep、awk)

文章目录 一、find1. 常用expression2. 时间参数3. 其他选项参数3.1 查找深度3.2 执行命令 二、sed1. 常用命令选项2. 常用动作脚本命令2.1 s 替换2.2 已匹配字符串标记&2.3 在当前行前后插入文本 a\ 和 i\2.4 p 打印指定行2.5 匹配行的方式2.5.1 以数字形式指定行区间2.5.…...

java的springboot框架中使用logback日志框架使用RabbitHandler注解为什么获取不到消费的traceId信息?

当使用 Logback 日志框架和 RabbitMQ 的 RabbitHandler 注解时&#xff0c;如果无法获取消费的 traceId 信息&#xff0c;可能是因为在处理 RabbitMQ 消息时&#xff0c;没有正确地将 traceId 传递到日志中。 为了将 traceId 传递到日志中&#xff0c;你可以利用 MDC&#xff…...

初探Vue.js及Vue-Cli

一、使用vue框架的简单示例 我们本次的vue系列就使用webstorm来演示&#xff1a; 对于vue.js的安装我们直接使用script的cdn链接来实现 具体可以参考如下网址&#xff1a; https://www.bootcdn.cn/ 进入vue部分&#xff0c;可以筛选版本,我这里使用的是2.7.10版本的&#xff…...

大数据课程K21——Spark的SparkSQL基础语法

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Spark的SparkSQL通过方法来使用; ⚪ 掌握Spark的SparkSQL通过sql语句来调用; 一、SparkSQL基础语法——通过方法来使用 1. 查询 df.select("id","name").show()…...

【实践篇】Redis最强Java客户端(三)之Redisson 7种分布式锁使用指南

文章目录 0. 前言1. Redisson 7种分布式锁使用指南1.1 简单锁&#xff1a;1.2 公平锁&#xff1a;1.3 可重入锁&#xff1a;1.4 红锁&#xff1a;1.5 读写锁&#xff1a;1.6 信号量&#xff1a;1.7 闭锁&#xff1a; 2. Spring boot 集成Redisson 验证分布式锁3. 参考资料4. 源…...

卫星通话过后,卫星导航产业被彻底激活

华为新手机发布后&#xff0c;其主打的卫星通话功能备受热议。在卫星产业链发展的背后&#xff0c;下一个大产业在哪里让人颇为好奇。 目前&#xff0c;卫星导航颇被看好&#xff0c;或将引领下一个技术狂潮。它的特点是产业大、发展快、参与者多。继电动汽车、新能源和芯片产…...

【算法训练-链表 七】【排序】:链表排序、链表的奇偶重排、重排链表

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【链表的排序】&#xff0c;使用【链表】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&am…...

LGB的两种写法

方法一 import lightgbm as lgb import pandas as pd from sklearn.model_selection import train_test_split, KFold from sklearn.metrics import accuracy_score# 读取训练集和测试集数据 train_data pd.read_csv(train.csv) test_data pd.read_csv(test.csv)# 分割特征和…...

【Unity的HDRP下ShaderGraph实现权重缩放全息投影_(内附源码)】

实现权重缩放全息投影 效果如下 效果如下 顶点位置偏移 链接&#xff1a; 提取码&#xff1a;1234...

透视俄乌网络战之二:Conti勒索软件集团(上)

透视俄乌网络战之一&#xff1a;数据擦除软件 Conti勒索软件集团&#xff08;上&#xff09; 1. Conti简介2. 组织架构3. 核心成员4. 招募途径5. 工作薪酬6. 未来计划参考 1. Conti简介 Conti于2019年首次被发现&#xff0c;现已成为网络世界中最危险的勒索软件之一&#xff0…...

【华为OD机试python】拔河比赛【2023 B卷|100分】

【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 公司最近准备进行拔河比赛,需要在全部员工中进行挑选。 选拔的规则如下: 按照身高优先、体重次优先的方式准备比赛阵容; 规定参赛的队伍派出10名选手。 请实现一个选拔队员的小程序。 输…...

05 CNN 猴子类别检测

一、数据集下载 kaggle数据集[10 monkey] 二、数据集准备 2.1 指定路径 from tensorflow import keras import tensorflow as tf import numpy as np import pandas as pd import matplotlib.pyplot as plttrain_dir /newdisk/darren_pty/CNN/ten_monkey/training/ valid_d…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...