当前位置: 首页 > 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…...

python打卡day49

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

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

云原生玩法三问:构建自定义开发环境

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

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

ArcGIS Pro+ArcGIS给你的地图加上北回归线!

今天来看ArcGIS Pro和ArcGIS中如何给制作的中国地图或者其他大范围地图加上北回归线。 我们将在ArcGIS Pro和ArcGIS中一同介绍。 1 ArcGIS Pro中设置北回归线 1、在ArcGIS Pro中初步设置好经纬格网等&#xff0c;设置经线、纬线都以10间隔显示。 2、需要插入背会归线&#xf…...

SpringCloud优势

目录 完善的微服务支持 高可用性和容错性 灵活的配置管理 强大的服务网关 分布式追踪能力 丰富的社区生态 易于与其他技术栈集成 完善的微服务支持 Spring Cloud 提供了一整套工具和组件来支持微服务架构的开发,包括服务注册与发现、负载均衡、断路器、配置管理等功能…...