【贪心算法】No.1---贪心算法(1)

文章目录

  • 前言
  • 一、贪心算法:
  • 二、贪心算法示例:
    • 1.1 柠檬⽔找零
    • 1.2 将数组和减半的最少操作次数
    • 1.3 最⼤数
    • 1.4 摆动序列
    • 1.5 最⻓递增⼦序列
    • 1.6 递增的三元⼦序列


前言

在这里插入图片描述

👧个人主页:@小沈YO.
😚小编介绍:欢迎来到我的乱七八糟小星球🌝
📋专栏:贪心算法
🔑本章内容:贪心算法
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~


一、贪心算法:

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。贪心算法解决问题的过程中,每一步都做出一个看似最优的决策,这个决策依赖于当前问题状态,不依赖于解决问题的前面的步骤和将来的步骤。这种方法在很多情况下并不会得到最优解,但是在某些问题上贪心算法的解就是最优解。

二、贪心算法示例:

1.1 柠檬⽔找零

  1. 题⽬链接:860. 柠檬⽔找零
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    分情况讨论:
    a. 遇到 5 元钱,直接收下;
    b. 遇到 10 元钱,找零 5 元钱之后,收下;
    c. 遇到 20 元钱:
    i. 先尝试凑 10 + 5 的组合;
    ii. 如果凑不出来,拼凑 5 + 5 + 5 的组合;
  4. C++代码
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five=0,ten=0;for(int i=0;i<bills.size();i++){if(bills[i]==5)five++;else if(bills[i]==10){ten++;if(five>0)five--;else return false;}else{if(ten>0&&five>0)//贪心{ten--;five--;}else if(five>=3)five-=3;else return false;}}return true;}
};

1.2 将数组和减半的最少操作次数

  1. 题⽬链接:2208. 将数组和减半的最少操作次数
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    a. 每次挑选出「当前」数组中「最⼤」的数,然后「减半」
    b. 直到数组和减少到⾄少⼀半为⽌。
    为了「快速」挑选出数组中最⼤的数,我们可以利⽤「堆」这个数据结构
  4. C++代码
class Solution {double sum=0,cnt=0;priority_queue<double,vector<double>,less<double>> pq;
public:int halveArray(vector<int>& nums) {for(auto&e:nums){  sum+=e;pq.push(e);}sum/=2.0;while(sum>0){cnt++;double tmp=pq.top()/2;pq.pop();sum-=tmp;pq.push(tmp);}return cnt;}
};

1.3 最⼤数

  1. 题⽬链接:179. 最⼤数
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    可以先优化:将所有的数字当成字符串处理,那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。
    贪⼼策略:按照题⽬的要求,重新定义⼀个新的排序规则,然后排序即可。
    排序规则:
    a. 「A 拼接 B」 ⼤于 「B 拼接 A」,那么 A 在前,B 在后;
    b. 「A 拼接 B」 等于 「B 拼接 A」,那么 A B 的顺序⽆所谓;
    c. 「A 拼接 B」 ⼩于 「B 拼接 A」,那么 B 在前,A 在后;
  4. C++代码
class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> v;for(auto&e:nums)v.push_back(to_string(e));string ret;sort(v.begin(),v.end(),[](string& s1,string& s2){return s1+s2>s2+s1;});for(int i=0;i<v.size();i++){if(i==0&&v[i]=="0")return "0";ret+=v[i];}return ret;}
};

1.4 摆动序列

  1. 题⽬链接:376. 摆动序列
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    对于某⼀个位置来说:
    ◦ 如果接下来呈现上升趋势的话,我们让其上升到波峰的位置;
    ◦ 如果接下来呈现下降趋势的话,我们让其下降到波⾕的位置。
    因此,如果把整个数组放在「折线图」中,我们统计出所有的波峰以及波⾕的个数即可。
  4. C++代码
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int left=0,ret=0;for(int i=0;i<nums.size()-1;i++){int right=nums[i+1]-nums[i];if(right==0)continue;if(right*left<=0)ret++;left=right;}return ret+1;//加上最后一个}
};

1.5 最⻓递增⼦序列

  1. 题⽬链接:300. 最⻓递增⼦序列
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    我们在考虑最⻓递增⼦序列的⻓度的时候,其实并不关⼼这个序列⻓什么样⼦,我们只是关⼼最后⼀个元素是谁这样新来⼀个元素之后,我们就可以判断是否可以拼接到它的后⾯
    因此,我们可以创建⼀个数组,统计⻓度为 x 的递增⼦序列中,最后⼀个元素是谁。为了尽可能的让这个序列更⻓,我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
    统计的过程中发现,数组中的数呈现「递增」趋势,因此可以使⽤「⼆分」来查找插⼊位置
  4. C++代码
class Solution {int cnt=0;
public:int lengthOfLIS(vector<int>& nums) {int n=nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i=1;i<nums.size();i++){if(nums[i]>ret.back())ret.push_back(nums[i]);//可以拼接到后面//如果不可以拼接到末尾则需要找到ret中出现第一次>=nums[i]的值进行替换,也就是把这个第一次大的值换成小的nums[i]else{int left=0,right=ret.size()-1;while(left<right){int mid=left+(right-left)/2;if(ret[mid]>=nums[i])right=mid;else left=mid+1;}ret[left]=nums[i];}}return ret.size();}
};

1.6 递增的三元⼦序列

  1. 题⽬链接:334. 递增的三元⼦序列
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    最⻓递增⼦序列的简化版。
    不⽤⼀个数组存数据,仅需两个变量即可。也不⽤⼆分插⼊位置,仅需两次⽐较就可以找到插⼊位置
  4. C++代码
class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n=nums.size();vector<int> ret;ret.push_back(nums[0]);for(int i=1;i<n;i++){if(nums[i]>ret.back())ret.push_back(nums[i]);else{int left=0,right=ret.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[i]>ret[mid])left=mid+1;else right=mid;}ret[left]=nums[i];}}return ret.size()>=3?true:false;}
};
----------------------------------------------------------------------------------------------
class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n=nums.size();int a=nums[0],b=INT_MAX;for(int i=1;i<n;i++){if(nums[i]>b)return true;else{if(nums[i]<=a)a=nums[i];else b=nums[i];}}return false;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/470067.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

无人机动力测试台如何快速外接第三方传感器

前言 动力测试台对于测试动力系统的拉力、扭矩、RPM 和效率至关重要。将传感器集成到您的测试中增加了另一层优化&#xff0c;可以将您的性能提升到一个新的水平。 在无人驾驶行业中&#xff0c;有充分的证据表明&#xff0c;从外部传感器收集数据可能具有挑战性。为了解决这…

【项目开发 | 跨域认证】JSON Web Token(JWT)

未经许可,不得转载。 文章目录 JWT设计背景:跨域认证JWT 原理JWT 结构JWT 使用方式注意JSON Web Token(缩写 JWT)是目前最流行的跨域认证解决方案,本文介绍它的原理、结构及用法。 JWT设计背景:跨域认证 互联网服务的用户认证流程是现代应用中的核心组成部分,通常的流程…

985研一学习日记 - 2024.11.12

一个人内耗&#xff0c;说明他活在过去&#xff1b;一个人焦虑&#xff0c;说明他活在未来。只有当一个人平静时&#xff0c;他才活在现在。 日常 1、起床6:00√ 2、健身2h 3、LeetCode刷了4题 无重叠区间 对于贪心算法&#xff0c;可以先对数组进行排序&#xff0c;然后再…

数学建模模型算法-Python实现

一、评价决策类 1、层次分析法&#xff08;AHP&#xff09; 层次分析法用来评价或选择一个更好更优的决策或方案 通过找到可以衡量其好坏的指标&#xff0c;进而衡量指标&#xff0c;再形成评价体系 归一化处理 让指标在同一数量级&#xff0c;且保证在同一指标下其差距保持…

洞察鸿蒙生态,把握开发新机遇

随着科技的不断进步&#xff0c;鸿蒙系统以其独特的分布式架构和跨设备协同能力&#xff0c;逐渐在智能手机、智能穿戴、车载、家居等多个领域崭露头角&#xff0c;与安卓、iOS形成三足鼎立之势。作为一名开发者&#xff0c;我对鸿蒙生态的认知和了解如下&#xff1a; 一、鸿蒙…

uniapp打包华为,提示请提供64位版本软件包后再提交审核

HBuilder项目打包需要配置勾选arm64-v8a,默认只会集成armeabi-v7a

信捷 PLC C语言 POU 指示灯交替灭0.5秒亮0.5秒(保持型定时器)

1.在全局变量表中定义2个定时器变量timer_1,timer_2 名称 类型 timer_1 TMR_A_FB False -- False False timer_2 TMR_A_FB False -- False False ot2 BOOL False -- False False ot2表示指示灯 …

Apache ECharts

目录 1. 基本概念 1.1 ECharts的主要特点有&#xff1a; 1.2 ECharts的图形绘制方式&#xff1a; 2. 基本使用 3. 图表容器的大小 4. Option常用配置项 1. 基础配置项 title 标题组件 tooltip提示框组件 legend 图例组件 2.坐标配置项 grid网格组件 xAxis 直角坐标…

NVIDIA NIM 简介

NVIDIA NIM 简介 NVIDIA NIM 是一组易于使用的微服务&#xff0c;旨在加速在云、数据中心和工作站中部署生成式 AI 模型。NIM 按模型系列和每个模型分类。例如&#xff0c;用于大型语言模型 (LLM) 的 NVIDIA NIM 将最先进的 LLM 的强大功能带入企业应用程序&#xff0c;提供无…

常用中间件介绍

1. RabbitMQ RabbitMQ是一个基于AMQP&#xff08;Advanced Message Queuing Protocol&#xff0c;高级消息队列协议&#xff09;的开源消息代理软件&#xff0c;实现了面向消息的中间件。它支持消息持久化、队列、交换机&#xff08;Exchange&#xff09;和绑定&#xff08;Bin…

AI写作(四)预训练语言模型:开启 AI 写作新时代(4/10)

一、预训练语言模型概述 ​ 预训练语言模型在自然语言处理领域占据着至关重要的地位。它以其卓越的语言理解和生成能力&#xff0c;成为众多自然语言处理任务的关键工具。 预训练语言模型的发展历程丰富而曲折。从早期的神经网络语言模型开始&#xff0c;逐渐发展到如今的大规…

《云原生安全攻防》-- K8s安全防护思路

从本节课程开始&#xff0c;我们将正式进入防护篇。通过深入理解K8s提供的多种安全机制&#xff0c;从防守者的角度&#xff0c;运用K8s的安全最佳实践来保障K8s集群的安全。 在这个课程中&#xff0c;我们将学习以下内容&#xff1a; K8s安全防护思路&#xff1a;掌握K8s自身提…

LLM之模型评估:情感评估/EQ评估/幻觉评估等

如果您想知道如何确保 LLM 在您的特定任务上表现出色&#xff0c;本指南适合您&#xff01;它涵盖了评估模型的不同方法、设计您自己的评估的指南以及来自实践经验的技巧和窍门。 Human-like Affective Cognition in Foundation Models&#xff1a;情感认知评估 研究者们提出了…

【JavaEE进阶】导读

本节⽬标 了解什么是JavaEE 在JavaEE中, 我们学习什么, 如何学, 难点是什么 一、Java EE 发展历程 Java EE(Java Platform Enterprise Edition), Java 平台企业版. 是JavaSE的扩展, ⽤于解决企业级的开发需求, 所以也可以称之为是⼀组⽤于企业开发的Java技术标准. 所以, 学习…

【韩老师零基础30天学会Java 】07章 面向对象编程(基础)

第七章 面向对象编程&#xff08;基础&#xff09; 1. 类与成员方法 类与对象关系示意图 示例&#xff1a;代码 import java.util.Scanner;public class IntDetail{public static void main(String[] args){Cat cat1new Cat();cat1.name"小花";cat1.age12;cat1.co…

超子物联网HAL库笔记:定时器[外部模式]篇

超子物联网 HAL库学习 汇总入口&#xff1a; 超子物联网HAL库笔记&#xff1a;[汇总] 写作不易&#xff0c;如果您觉得写的不错&#xff0c;欢迎给博主来一波点赞、收藏~让博主更有动力吧&#xff01; 一、资源介绍&#xff1a;STM32F103C8T6定时器资源介绍 高级定时器&#x…

谷歌浏览器的自动翻译功能如何开启

在当今全球化的网络环境中&#xff0c;能够流畅地浏览不同语言的网页是至关重要的。谷歌浏览器&#xff08;Google Chrome&#xff09;提供了一项强大的自动翻译功能&#xff0c;可以帮助用户轻松跨越语言障碍。本文将详细介绍如何开启和使用谷歌浏览器的自动翻译功能&#xff…

【大数据技术基础 | 实验十】Hive实验:部署Hive

文章目录 一、实验目的二、实验要求三、实验原理四、实验环境五、实验内容和步骤&#xff08;一&#xff09;安装部署&#xff08;二&#xff09;配置HDFS&#xff08;三&#xff09;启动Hive 六、实验结果&#xff08;一&#xff09;启动结果&#xff08;二&#xff09;Hive基…

使用 Vue 配合豆包MarsCode 实现“小恐龙酷跑“小游戏

作者&#xff1a;BLACK595 “小恐龙酷跑”&#xff0c;它是一款有趣的离线游戏&#xff0c;是Google给Chrome浏览器加的一个有趣的彩蛋。当我们浏览器断网时一只像素小恐龙便会出来提示断网。许多人认为这只是一个可爱的小图标&#xff0c; 但当我们按下空格后&#xff0c;小恐…

案例精选 | 河北省某检察院安全运营中异构日志数据融合的实践探索

河北省某检察院是当地重要的法律监督机构&#xff0c;肩负着维护法律尊严和社会公平正义的重要职责。该机构依法独立行使检察权&#xff0c;负责对犯罪行为提起公诉&#xff0c;并监督整个诉讼过程&#xff0c;同时积极参与社会治理&#xff0c;保护公民权益&#xff0c;推动法…