贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列

本文主要是介绍贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

目录

力扣860.柠檬水找零

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

力扣179.最大数

力扣376.摆动序列


贪心策略,局部最优->全局最优

1.把解决问题的过程分为若干步骤

2.解决每一步的时候,都选择当前看起来“最优秀的”解法

3.希望能够得到全局最优解

例子1:找零问题 50-4=46  ->[20,10,5,1] 46->26->6->5->1   找当前能够找到的最大解法。

例子2:最小路径和(当初动态规划)

每次只能向下,或者向右侧,找到最小的路径,                                                                              11611,这个不一定对,但是符合贪心的策略,鼠目寸光

例子三:背包问题

疯狂装体积小的,直接塞满(只去考虑体积,考虑价值,则去疯狂交给价值)

1.贪心策略的特点:

1.贪心策略的提出是没有标准和模版的

2.可能每一道贪心策略都是不同的

2.贪心策略的正确性

贪心策略可能是一个错误的方法,正确的贪心,是需要一个证明的

常用的证明方法:数学中见过的所有方法

找零问题:【20,10,5,1】

力扣860.柠檬水找零

class Solution {public boolean lemonadeChange(int[] bills) {
if(bills[0]>5){return false;
}
//找钱也就是15块和5块
int five=0;int ten=0;
for(int i=0;i<bills.length;i++){if(bills[i]==5){five++;}else if(bills[i]==10){ten++;five--;}else if(bills[i]==20){if(ten>0){ten--;five--;}else{five=five-3;}}if(five<0||ten<0){return false;
}}return true;}
}

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

class Solution {//贪心,每次都去挑选数组中最大的数,然后减半,知道数组和到原来的一半public int halveArray(int[] nums) {int count=0;//每次都挑选最大的数,借助一个数据结构(大根堆)
//拿到堆顶,然后再去/2放到大根堆里面PriorityQueue <Double>priorityQueue=new PriorityQueue<>((a,b)->b.compareTo(a));double sum=0;for(double num:nums){priorityQueue.add(num);sum+=num;}sum=sum/2.0;
while(sum>0){double p=priorityQueue.poll()/2.0;count++;sum=sum-p;priorityQueue.add(p);
}
return count;}
}

力扣179.最大数

正常的排序:确定元素的先后顺序:谁在前面,谁在后面

a和b是同一数量级,比如 8,9 或者10,11或者34, 36。我的意思是,两位数和两位数比,一位数和一位数比

a和b不是统一数量级,假如位数不一样,那么就依次循环,来确定首尾

谈谈这块,首先这个sort的使用比较器的方法,只适用于包装类的逆序,并不适用于基础类型

      Integer []nums={1,2,3,4};//排序Arrays.sort(nums,Comparator.reverseOrder());for(int x:nums){System.out.println(x);}

在Java中,当你尝试对字符串数组使用Lambda表达式进行排序,并且使用(b+a).compareTo(a+b)作为比较逻辑时,b+a和a+b在大多数情况下看起来可能相同,因为它们都是将两个字符串拼接起来。但是,这里的关键在于这两个表达式在特定的字符串上可能会产生不同的结果,特别是当涉及到字符串连接时的数值解释时。

考虑以下情况:

当a和b都是数字字符串时(例如a="12",b="3"),b+a和a+b拼接后的字符串在数值上可能不同,但它们在字典顺序上可能是相同的。例如,"312"和"123"作为字符串在字典顺序上是不同的。
当a和b中包含非数字字符时,拼接后的结果将完全基于字符串的字典顺序,而不是任何潜在的数值解释。

现在,让我们详细分析(b+a).compareTo(a+b)的比较逻辑:

如果b+a在字典顺序上位于a+b之前,则compareTo方法将返回一个负数,表示b应该在a之前。
如果b+a和a+b在字典顺序上相同,则compareTo方法将返回0,表示a和b的位置不变。
如果b+a在字典顺序上位于a+b之后,则compareTo方法将返回一个正数,表示b应该在a之后。

这种比较逻辑在某些特定情况下可能看起来有些奇怪,特别是当处理数字字符串时。通常,如果你想要按照数值对数字字符串进行排序,你应该先将它们转换为数值类型(如Integer或Long),然后再进行比较。

然而,在你提供的例子中,这种比较逻辑可能用于创建一种特定的排序顺序,该顺序可能基于字符串的某种非直观或特殊的比较逻辑。

最后,值得注意的是,对于非数字字符串,这种比较逻辑可能不会产生有意义的结果,因为字符串的字典顺序和它们的任何潜在数值解释之间可能没有直接关系。

其实不用记住顺序,尝试一遍不就好咯。

class Solution {public String largestNumber(int[] nums) {int n=nums.length;String[] strs=new String[n];for(int i=0;i<n;i++) strs[i]=""+nums[i];//排序Arrays.sort(strs,(a,b)->{return (b+a).compareTo(a+b);});
//提取结果
StringBuffer ret=new StringBuffer();
for(String s:strs) ret.append(s);
if(ret.charAt(0)=='0')return "0";
return ret.toString();}
}

只有符合全序关系,才能说明贪心正确。

证明 ab,ba两个拼接起来都是数,能够比较大小,就算是字符串也是可以比较ac码,所以可以视为数字。

力扣376.摆动序列

class Solution {public  static int wiggleMaxLength(int[] nums) {int n=nums.length;if(n<2){return n;}int left=0;int ret=0;int right=0;for(int i=0;i<n-1;i++){right=nums[i+1]-nums[i];if(right==0){continue;}//y要么是波峰, 要么是波谷//第一个点也考虑进去,注意等于0的情况是第一个点,假如第一个点不是0,那么left*right也不会等于0,因为假如right=0,那么就会跳过了if(left*right<=0){ret++;}left=right;}return ret+1;}}

这篇关于贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/989790

相关文章

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.