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

news/2024/11/14 9:13:04/

文章目录

  • 前言
  • 一、算法>贪心算法
  • 二、算法>贪心算法示例:
    • 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.ppmy.cn/news/1545981.html

相关文章

NeurIPS24 | 多无人机协作精确预测车辆等目标移动轨迹, Drones Help Drones

Drones Help Drones: A Collaborative Framework for Multi-Drone Object Trajectory Prediction and Beyon 摘要前言related work整体结构4.1问题组织4.2 2D Feature Extraction of Observations4.3 深度估计与BEV生成4.4 通过滑动窗口模块的稀疏交互 5.实验5.1 数据集5.2 指标…

Python学习------第四天

Python的判断语句 一、布尔类型和比较运算符 二、 if语句的基本格式 if语句注意空格缩进&#xff01;&#xff01;&#xff01; if else python判断语句的嵌套用法&#xff1a;

跟李沐学AI:BERT

什么是NLP中的迁移学习 使用预训练好的模型来抽取词、句子的特征&#xff1a;Word2Vec或者预训练好的语言模型。 使用预训练好的语言模型&#xff0c;一般不会再对语言模型进行微调&#xff0c;即不进行更新。 Word2Vec一般用于替代embedding层 但是Word2Vec往往忽略了时序…

50个广泛使用的SQL关键字

1.SELECT:用于从一个或多个数据表中检索数据。 2.FROM:指定SELECT查询中数据来源的表。 3.WHERE:用于过滤查询结果&#xff0c;指定选择条件。 4.INSERT INTO:用于向表中插入新行。 5.UPDATE:用于修改表中的数据。 6.DELETE:用于从表中删除数据。 7.CREATE TABLE:用于创建…

弹性裸金属服务器和传统裸金属服务器有什么区别?

弹性裸金属服务器是一种结合了传统裸金属服务器和云计算资源两种特点的服务器&#xff0c;是一种云计算服务&#xff0c;下面我们就来了解一下弹性裸金属服务器和传统裸金属服务器之间有什么区别吧&#xff01; 弹性裸金属服务器能够支持企业快速部署新的硬件和软件系统&#x…

论文阅读-Event-based Visible and Infrared Fusion via Multi-task Collaboration

一、前言 可见光图像与红外图像融合&#xff08;VIF&#xff09;通过结合热红外图像与可见光图像的丰富纹理&#xff0c;提供了一个全面可靠的场景描述。然而&#xff0c;传统的VIF系统可能在极端光照和高动态运动场景中捕获过曝或欠曝的图像&#xff0c;进而导致融合结果下降…

【06】A-Maven项目SVN设置忽略文件

做Web项目开发时&#xff0c;运用的是Maven管理工具对项目进行管理&#xff0c;在项目构建的过程中自动生成了很多不需要SVN进行管理的文件&#xff0c;SVN在对源码进行版本管理时&#xff0c;需要将其忽略&#xff0c;本文给出了具体解决方案。 SVN设置忽略Maven项目中自动生成…

在Linux环境下使用Docker打包和发布.NET程序并配合MySQL部署

在Linux环境下使用Docker打包和发布.NET程序并配合MySQL部署 1. 引言 在当今快节奏的软件开发世界里&#xff0c;Docker化.NET程序并配合MySQL使用&#xff0c;已经成为了一种流行的组合方式。这种方式不仅能够提高开发效率&#xff0c;还能保证环境的一致性&#xff0c;简化部…