【算法】贪心算法练习一

个人主页 : zxctscl
如有转载请先通知

题目

  • 1. 贪心算法的介绍
  • 2. 860. 柠檬水找零
  • 2.1 分析
  • 2.2 代码
  • 3. 2208. 将数组和减半的最少操作次数
  • 3.1 分析
  • 3.2 代码
  • 4. 179. 最大数
  • 4.1 分析
  • 4.2 代码

1. 贪心算法的介绍

一、贪心策略:解决问题的策略,局部最优->全局最优

  1. 把解决问题的过程分为若干步;
  2. 解决每一步的时候,都选择当前看起来“最优的”解法;
  3. 希望得到全局最优。

二、贪心策略的正确性
因为有可能“贪心策略”是一个错误的方法
正确的贪心策略,是需要证明的

常见的证明方法就是在数学中见过的所有证明方法。

三、学习贪心算法的方向
遇到不会的贪心题,很正常,把心态放平。

  1. 前期学习的时候,把重点放在贪心的策略上,把这个策略当做经验吸收。
  2. 如何证明贪心策略是正确的

2. 860. 柠檬水找零

在这里插入图片描述

2.1 分析

一、题目解析
题目已经提到:一开始你手头没有任何零钱,如果第一个顾客给的钱超过了5美元,那么就没有零钱找,就返回false。
考虑当前的顾客时候,是不考虑后面的顾客。

二、算法原理
分情况讨论:第一种:当顾客给了5美元,就直接收下;
第二种,当顾客给了10美元,先判断一下有没有5美元,有就收下,没有就返回false;
第三种:20美元的找零,可以分一张10和一张5;还可以找三种5块钱,有分歧的时候就得判断一下哪一个找零更好,是10+5,还是5+5+5,所以对于5块钱的作用很大的时候,就把5块钱保留。

在这里插入图片描述

2.2 代码

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {

        int five=0,ten=0;
        for(auto x: bills)
        {
            if(x==5) five++;
            else if(x==10)
            {
                if(five==0) return false;
                five--;ten++;
            }
            else
            {
                if(ten&&five)
                {
                    ten--;five--;
                }
                else if(five>=3)
                {
                    five-=3;
                }
                else return false;
            }
        }
        return true;

    }
};

3. 2208. 将数组和减半的最少操作次数

在这里插入图片描述

3.1 分析

一、题目解析
题目要求返回将 nums 数组和至少减少一半的最少操作数,看一下例1:
在这里插入图片描述
数组和是33,一半就是16.5,先选择19减半就是9.5,此时数组和没有小于16.5;然后继续选择9.5减半为4.75,此时数组和没有小于16.5;再选择8减半为4,此时此时数组和小于16.5,总共就三次减半。

二、算法原理
每次挑选当前数组中,最大的那个数,然后减半,最大的数减半,才有可能最快减到数组和减少到至少一半。
为了选择最大的数,遍历一遍数组的时间复杂度太高了,所以就用一个大根堆,每次堆顶的元素就是最大的数。

在这里插入图片描述

3.2 代码

class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> heap;
        double sum=0;
        for(auto x:nums)
        {
            heap.push(x);
            sum+=x;
        }
        sum/=2.0;

        int count=0;
        while(sum>0)
        {
            double t=heap.top()/2;
            heap.pop();
            sum-=t;
            count++;
            heap.push(t);

        }
        return count;
    }
};

4. 179. 最大数

在这里插入图片描述

4.1 分析

一、题目解析
题目已经提到:
要得到最大的拼接数,就得先把这些数先拼接起来,然后比较找到最大的那一个就行。

二、算法原理
这里就得排序,确定元素的先后顺序:谁在前,谁在后
给这个数组排序,比如[a,b]:如果ab>ba,那么a前,b后;如果ab=ba,那么顺序无所谓;如果ab<ba,那么b前,a后。
比较数的拼接大小比较麻烦,可以把数转换为字符串,然后拼接字符串,比较字典序。
如果传[0,0],那么就会出现前导0的情况,所以在最后的结果中,就直接返回0。
在这里插入图片描述

4.2 代码

class Solution {
public:
    string largestNumber(vector<int>& nums) {
       vector<string> strs;
       for(int x:nums)strs.push_back(to_string(x));

       sort(strs.begin(),strs.end(),[](const string& s1,const string& s2)
       {
        return s1+s2>s2+s1;
       });

       string ret;
       for(auto& s:strs)
       {
        ret+=s;
       }
       if(ret[0]=='0')return "0";
       return ret;
    }
};

有问题请指出,大家一起进步!!!

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

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

相关文章

继续教育自考计算机及应用试题及答案,分享几个实用搜题和学习工具 #经验分享#知识分享

题目类型比较多&#xff0c;包含判断、单选、多选、填空等多种题型&#xff0c;适合各种职业考证搜题&#xff0c;比如医卫类、财会类、海外贸易等&#xff0c;大家可以根据自己的需求进行选择&#xff0c;而且直接输入题目内容就能搜索题目&#xff0c;很是方便。 1.试题猪 …

数据结构:构建完全二叉查找树

文章目录 1、步骤 1: 对给定数组排序2、步骤 2: 递归构建完全二叉查找树3、注意4、在有序数组中寻找根结点位置5、代码实现6、其他方法&#xff1f;基本思路插入操作删除操作特别考虑 对于一个给定序列的二叉查找树&#xff0c;有很多种&#xff0c;但是完全二叉查找树只有一种…

Windows安装Kibana

下载 注意&#xff1a;为了避免一些稀奇古怪的问题&#xff0c;kibana版本最好和es版本保持一致。 es版本查看&#xff1a; 官网下载地址&#xff1a; Download Kibana Free | Get Started Now | Elastichttps://www.elastic.co/cn/downloads/kibana如果是下载最新的&#x…

41---音频电路设计

视频链接 音频电路设计01_哔哩哔哩_bilibili 音频电路设计 1、音频基本介绍 1.1、设备 1.1.1、音频接口 型号&#xff1a;ABA-JAK-038-K44 电脑主机上的音频输出插口&#xff0c;一个是粉色的&#xff0c;用来连接麦克风或话筒&#xff0c;一个是绿色的&#xff0c;用来连…

【数据结构与算法】:归并排序和计数排序

1. 归并排序 归并排序是一种效率仅次于快速排序的排序算法。它有非递归和递归两种实现方式(本文只讲述递归实现&#xff0c;非递归实现以后有专门的文章)。 其实&#xff0c;归并排序也叫外排序。它不仅可以对内存中的数据进行排序&#xff0c;还能对文件里的数据排序。 比如&…

网站压力测试和Locust

一、压力测试介绍 网站压力测试是一种评估网站性能、可靠性和稳定性的方法。它通过模拟大量用户同时访问网站,来测试网站的响应时间、吞吐量、资源利用率等指标,从而发现网站的潜在问题和瓶颈。下面我将从几个方面详细介绍网站压力测试: 1、压力测试的目的 评估网站在高并发…

路由器端口映射是什么意思?

路由器端口映射是一种网络配置技术&#xff0c;在私有网络中允许外部网络访问特定的服务或应用程序。通过将路由器的端口映射到内部客户端设备&#xff0c;可以实现从公共网络访问内部网络资源的目的。 天联组网介绍 天联是一款异地组网内网穿透产品&#xff0c;由北京金万维科…

【Qt】:常用控件(九:容器类控件)

常用控件 一.Group Box&#xff08;分组框&#xff09;二.Tab Widget&#xff08;标签页&#xff09; 一.Group Box&#xff08;分组框&#xff09; 使用QGroupBox实现一个带有标题的分组框.可以把其他的控件放到里面作为一组.这样看起来能更好看一点.&#xff08;换言之&…

复现bytetrack时,安装依赖项报错“: ERROR: Failed building wheel for lap

报错原因&#xff1a; lap 库的构建失败&#xff0c;因为缺少了 NumPy 库。 解决办法&#xff1a; 安装 NumPy 库&#xff1a;NumPy 是 Python 中用于科学计算的基础库&#xff0c;lap 依赖于它 pip install numpy 重新安装 lap 库&#xff1a; pip install lap

代码随想录|Day32|贪心算法 part02|● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

122.买卖股票的最佳时机II class Solution: def maxProfit(self, prices: List[int]) -> int: result 0 for i in range(len(prices) - 1): count prices[i1] - prices[i] if count > 0: result count return result 方法二&#xff1a;把if条件变成max class Solutio…

智能配电能效平台与照明系统在某地下污水处理厂中的应用

安科瑞薛瑶瑶18701709087 1、引言 随着互联网、芯片技术、通信传输的技术革新和成熟&#xff0c;智能照明已经广泛应用于居民生活和工业发展领域。传统的工业照明设计&#xff0c;常在门口附近设置集中控制箱&#xff0c;由控制箱内相应开关控制照明。当工厂面积较大&#xf…

ONERugged车载平板终端:提升港口运输水平

现代港口是国际贸易中至关重要的枢纽&#xff0c;而提高港口运输效率对于促进贸易流通和经济发展至关重要。近年来&#xff0c;车载平板技术的快速发展为港口运输行业带来了巨大的变革和机遇。车载平板的广泛应用不仅提高了港口的操作效率&#xff0c;还改善了货物跟踪、通信和…

Vue3中使用的富文本编辑器(详细实现流程)

文章目录 1. 前言2. 项目初始化3. 下载4. 使用富文本编辑器5. 注意点6. 效果图 1. 前言 有不少的前端需求都需要使用到富文本编辑器,但是富文本编辑器百花齐放,每次使用可能都会重新找一个编辑器,所以有了这篇文章. 当项目中需要使用到富文本编辑器时,可以直接按照这篇文章的步…

动态分区算法

一个不知名大学生&#xff0c;江湖人称菜狗 original author: Jacky Li Email : 3435673055qq.com Time of completion&#xff1a;2024.04.09 Last edited: 2024.04.09 目录 动态分区算法 第1关&#xff1a;首次适应算法 任务描述 相关知识 内存分配 内存回收 编程要求…

chronyd服务

一、介绍 chronyd服务是CentOS8系统之后提供时间服务的应用&#xff0c;和之前的ntp服务功能是一样的。 chronyd服务的配置文件默认存在在/etc/chrony.conf中。 chronyd服务的开启方式和关闭&#xff1a; systemctl start chronyd systemctl status chronyd systemctl st…

每天好好学习java第一天--复习巩固基础

1.浮点数数据特殊&#xff1a; float z 2.0e8F; float类型要在后面加f或者F。但是double类型可以省略。 2.强制转换数据类型&#xff1a; 格式&#xff1a; (类型名)变量名 例 float z 2.0f; int x(int)z; 3.逻辑运算符 注意异或 4.条件运算符 每天学习一会java&…

性能分析-数据库与磁盘知识

数据库 数据库&#xff0c;其实是数据库管理系统dbms。 数据库管理系统&#xff0c; 常见&#xff1a; 关系型数据库&#xff1a; mysql、pg、 库的表&#xff0c;表与表之间有关联关系&#xff1b; 表二维表统一标准的SQL&#xff08;不局限于CRUD&#xff09;非关系型数据…

配置VM开机自启动

1. 在此电脑-右键选择“管理”-服务和应用程序-服务中找到VMware Workstation Server服务&#xff08;新版名称也可能是VMware自启动服务&#xff0c;自己找一下&#xff0c;服务属性里有描述信息的&#xff09;&#xff0c;将其启用并选择开机自动启动 新版参考官方文档&…

C语言 函数——函数原型

目录 如何合并成一个完整的程序&#xff1f; 函数原型与函数定义的区别 函数原型的作用 如何合并成一个完整的程序&#xff1f; 问题&#xff1a;在一个函数中调用另一个函数&#xff0c;需要具备哪些条件呢&#xff1f; 若函数的定义出现在函数调用之前 若函数的定义出现…

跨云迁移实操:AWS RDS for mysql 迁移至腾讯云mysql --DTS方式

实操场景&#xff1a;从AWS RDS for mysql 迁移至腾讯云云数据库Mysql&#xff0c;通过腾讯云数据传输服务DTS,进行实时全量增量迁移. 下面九河云给大家带来具体实践介绍 购买迁移数据库--目的端机器&#xff08;腾讯云MYSQL&#xff09; 可以源端为5.7所以新建一个参数模版 其…