贪心 -力扣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

相关文章

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,:本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文

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

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

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

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