【贪心算法】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;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

阿里云-防火墙设置不当导致ssh无法连接

今天学网络编程的时候&#xff0c;看见有陌生ip连接&#xff0c;所以打开了防火墙禁止除本机之外的其他ip连接&#xff1a; 但是当我再次用ssh的时候&#xff0c;连不上了才发现大事不妙。 折腾了半天&#xff0c;发现阿里云上可以在线向服务器发送命令&#xff0c;所以赶紧把2…

基于物联网设计的地下煤矿安全监测与预警

文章目录 一、前言1.1 项目介绍【1】项目开发背景【2】设计实现的功能【3】项目硬件模块组成 1.2 设计思路1.3 系统功能总结1.4 开发工具的选择【1】设备端开发【2】上位机开发 1.5 模块的技术详情介绍【1】NBIOT-BC26模块【2】MQ5传感器【4】DHT11传感器【5】红外热释电人体检…

揭秘全向轮运动学:机动艺术与上下位机通信的智慧桥梁

✨✨ Rqtz 个人主页 : 点击✨✨ &#x1f308;Qt系列专栏:点击 &#x1f388;Qt智能车上位机专栏: 点击&#x1f388; 本篇文章介绍的是有关于全向轮运动学分析&#xff0c;单片机与上位机通信C代码以及ROS里程计解算的内容。 目录 大纲 ROS&#xff08;机器人操作系统&…

《AI在企业战略中的关键地位:以微软和阿里为例》

内容概要 在当今商业环境中&#xff0c;人工智能&#xff08;AI&#xff09;的影响力如滔滔洪水&#xff0c;愈演愈烈。文章将揭示AI在企业战略中的崛起&#xff0c;尤其以微软和阿里巴巴为代表的企业&#xff0c;这两家科技巨头通过不同方式&#xff0c;将智能技术融入其核心…

Pandas | 理性判断数据是否存在缺失值的一种方法

理性判断 一般思路进一步思考df[B].explode() 一般思路 tcc.info()上述信息info显示没有缺失值 但是真实的情况还是要根据业务实际分析tcc.isnull().sum() # 和tcc.info()作用和tcc.info() 其实是一样的 进一步思考 在此过程中&#xff0c;我们需要检验是否存在采用别的值来表…

大数据新视界 -- 大数据大厂之经典案例解析:广告公司 Impala 优化的成功之道(下)(10/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

基于vue框架的的冷链食品物流信息管理系统v81wb(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;用户,司机,冷链食品,冷链食品订单,冷链车辆,配送信息,订单费用,站点信息,食品种类,省,市,食品质量,县 开题报告内容 基于Vue框架的冷链食品物流信息管理系统开题报告 一、研究背景与意义 随着全球食品贸易的快速发展和消费者对食品品质…

职场逆袭!学会管理上司,你也能成为职场赢家

书友们&#xff0c;不要错过了&#xff01;我挖到了一本真正让我彻夜难眠的小说&#xff0c;情节跌宕起伏&#xff0c;角色鲜活得就像从书里跳出来陪你聊天。每一页都是新的惊喜&#xff0c;绝对让你欲罢不能。要是你也在寻找那种让人上瘾的阅读体验&#xff0c;这本书就是你的…

byte加byte居然是int了?

问题现象 最近在看 Java 的基础知识时看到一个有意思的现象&#xff0c;在 Java 中两个 byte 相加之后的结果的类型变成 int 类型了&#xff1a; byte a 1; byte b 2; b a b;从Idea给的提示可以看到&#xff0c;两个 byte 类型相加的结果变成了 int 类型&#xff0c;不能…

vue3中使用mqtt数据传输(封装)

使用版本 "mqtt": "^5.8.0",安装指令 npm install mqtt --save ------ yarn add mqtt介绍mqtt 参考使用文档 配置 connection: {protocol: "ws",host: "broker.emqx.io",port: 8083,endpoint: "/mqtt",clean: true,con…

全面解析谷歌浏览器的功能与使用技巧

谷歌浏览器&#xff08;Google Chrome&#xff09;作为全球最受欢迎的网页浏览器之一&#xff0c;以其简洁的界面、快速的加载速度和强大的功能赢得了广大用户的青睐。本文将全面解析谷歌浏览器的功能和使用技巧&#xff0c;帮助您更好地利用这一工具提升上网体验。&#xff08…

《探索Zynq MPSoC》学习笔记(二)

引言&#xff1a;本文开始学习第二章内容&#xff0c;本文重点介绍FPGA、Zynq和Zynq MPSoC器件技术演进以及Zynq和Zynq MPSoC器件的基本结构和特点。 第二章 FPGA、Zynq和Zynq MPSoC &#xff08;1&#xff09; Zynq MPSoC是Xilinx发布的第一款SoC Zynq-7000片上系统&#xf…

mac 本地docker-mysql主从复制部署

mac 本地docker-mysql主从复制部署,服务器同理 1.本地docker启动两个mysql服务.端口号不一样 没有选择挂载到宿主机.只做测试用. 只是端口号不一样容器删掉.就没有数据了. 生产测试,需要挂在 master docker run -d --name mysql-slave -p 3308:3306 \ -e MYSQL_ROOT_PASSWORD…

七.numpy模块

NumPy(Numerical Python) 是 Python 语言的一个扩展程序库&#xff0c;支持大量的维度数组与矩阵运算&#xff0c;此外也针对数组运算提供大量的数学函数库。 NumPy 的前身 Numeric 最早是由 Jim Hugunin 与其它协作者共同开发&#xff0c;2005 年&#xff0c;Travis Oliphant…

测试用例小锦囊——基于思维导图的测试用例生成和维护

敲黑板&#xff0c;测试用例真的很重要&#xff01; 测试用例是测试工作的基础&#xff0c;通过提供结构化和系统化的方法&#xff0c;来帮助验证软件产品的功能是否按预期正确实现&#xff0c;从而确保软件质量&#xff0c;提升用户满意度。 测试用例的关键要素包括用例编号、…

Linux网络命令:用于查看和修改路由表的重要工具ip route 详解

目录 一、概述 二、用法 1、基本语法 2、参数说明 3、常用选项 4、获取帮助 三、基本用法示例 1、 查看路由表 2、 添加路由 3、 删除路由 4、 修改路由 5、 添加默认路由 6、 删除默认路由 四、路由表管理 1、查看所有路由表 2、指定路由表 五、其他选项 1、…

银行信贷风控专题:Python、R 语言机器学习数据挖掘应用实例合集:xgboost、决策树、随机森林、贝叶斯等

银行信贷风控专题&#xff1a;Python、R 语言机器学习数据挖掘应用实例合集&#xff1a;xgboost、决策树、随机森林、贝叶斯等 原创 拓端研究室 全文链接&#xff1a;https://tecdat.cn/?p38026 在当今金融领域&#xff0c;风险管控至关重要。无论是汽车贷款违约预测、银行挖掘…

容器内pip安装Apache Airflow的经历:如何重置初始密码

背景 Apache Airflow™https://github.com/apache/airflow 是一个开源平台&#xff0c;用于开发、调度和监控面向批处理的工作流程。Airflow 可扩展的 Python 框架使您能够构建几乎可以连接任何技术的工作流程。Web 界面有助于管理工作流程的状态。Airflow 可以通过多种方式部…

RHCE作业四

一要求&#xff1a; 1.搭建dns服务器能够对自定义的正向或者反向域完成数据解析查询。 2.配置从DNS服务器&#xff0c;对主dns服务器进行数据备份。 二操作&#xff1a; 主服务器 1.安装 2主配置真反向 3正反设置 区域 1安装 2添加allow-transfer 3增量 4重启 Systemctl …

算法练习:1658. 将 x 减到 0 的最小操作数

题目链接&#xff1a;1658. 将 x 减到 0 的最小操作数 这道题目的意思就是&#xff0c;给定一个整数数组&#xff0c;和一个x&#xff0c;只能从数组最左边或者最右边进行删除&#xff0c;使得x恰好等于0&#xff0c;并且要操作次数最少的情况&#xff0c;否则返回-1. 这道题直…