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题目描述回溯算法贪心算法 总结 前置知识 参考前文 参考文章: LeetCode刷题笔记【23】…...
游戏出现卡顿有哪些因素
一、服务器CPU内存占用过大会导致卡顿,升级CPU内存或者优化自身程序占用都可以解决。 二、带宽跑满导致卡,可以升级带宽解决。 二、平常不卡,有大型的活动的时候会卡,这方面主要是服务器性能方面不够导致的,性能常说…...

学习Bootstrap 5的第八天
目录 加载器 彩色加载器 实例 闪烁加载器 实例 加载器大小 实例 加载器按钮 实例 分页 分页的基本结构 实例 活动状态 实例 禁用状态 实例 分页大小 实例 分页对齐 实例 面包屑(Breadcrumbs) 实例 加载器 彩色加载器 在 Bootstr…...
vue中自定义指令
什么是指令 在Vue.js中,指令是一种特殊的 token,用于在模板中以声明式方式将响应式数据绑定到 DOM 元素上,从而实现与 DOM 元素的交互和操作。指令以 “v-” 前缀开始,后跟指令的名称,例如 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文件中添加一个按钮或需要点击的元素,并绑定点击事件监听器2 <button bindtap"copyText">点击复制</button> 2 在对应的js文件中定义点击事件处理函数,并在函数中调用小程序的API进行复制操作, copyText(e){co…...

20230909java面经整理
1.java常用集合 ArrayList动态数组,动态调整大小,实现List接口 LinkedList双向链表,实现list和queue接口,适用于频繁插入和删除操作 HashSet无序,使用哈希表实现 TreeSet有序,使用红黑树实现 HashMap无序&…...
常用的css命名规则
一、命名规则说明: 1)、所有的命名最好都小写 2)、属性的值一定要用双引号(“”)括起来 3)、给图片加上alt标签 4)、尽量使用英文命名原则 5)、尽量不缩写,除非一看就明白的单词 二、相对网页外…...
【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 注解时,如果无法获取消费的 traceId 信息,可能是因为在处理 RabbitMQ 消息时,没有正确地将 traceId 传递到日志中。 为了将 traceId 传递到日志中,你可以利用 MDCÿ…...

初探Vue.js及Vue-Cli
一、使用vue框架的简单示例 我们本次的vue系列就使用webstorm来演示: 对于vue.js的安装我们直接使用script的cdn链接来实现 具体可以参考如下网址: https://www.bootcdn.cn/ 进入vue部分,可以筛选版本,我这里使用的是2.7.10版本的ÿ…...
大数据课程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 简单锁:1.2 公平锁:1.3 可重入锁:1.4 红锁:1.5 读写锁:1.6 信号量:1.7 闭锁: 2. Spring boot 集成Redisson 验证分布式锁3. 参考资料4. 源…...
卫星通话过后,卫星导航产业被彻底激活
华为新手机发布后,其主打的卫星通话功能备受热议。在卫星产业链发展的背后,下一个大产业在哪里让人颇为好奇。 目前,卫星导航颇被看好,或将引领下一个技术狂潮。它的特点是产业大、发展快、参与者多。继电动汽车、新能源和芯片产…...

【算法训练-链表 七】【排序】:链表排序、链表的奇偶重排、重排链表
废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【链表的排序】,使用【链表】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为&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实现权重缩放全息投影_(内附源码)】
实现权重缩放全息投影 效果如下 效果如下 顶点位置偏移 链接: 提取码:1234...

透视俄乌网络战之二:Conti勒索软件集团(上)
透视俄乌网络战之一:数据擦除软件 Conti勒索软件集团(上) 1. Conti简介2. 组织架构3. 核心成员4. 招募途径5. 工作薪酬6. 未来计划参考 1. Conti简介 Conti于2019年首次被发现,现已成为网络世界中最危险的勒索软件之一࿰…...
【华为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…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!
今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等,设置经线、纬线都以10间隔显示。 2、需要插入背会归线…...
SpringCloud优势
目录 完善的微服务支持 高可用性和容错性 灵活的配置管理 强大的服务网关 分布式追踪能力 丰富的社区生态 易于与其他技术栈集成 完善的微服务支持 Spring Cloud 提供了一整套工具和组件来支持微服务架构的开发,包括服务注册与发现、负载均衡、断路器、配置管理等功能…...