贪心算法入门(三)

devtools/2024/11/18 23:22:09/

相关文章

算法>贪心算法入门(一)-CSDN博客

算法>贪心算法入门(二)-CSDN博客

1.什么是算法>贪心算法

        算法>贪心算法是一种解决问题的策略,它将复杂的问题分解为若干个步骤,并在每一步都选择当前最优的解决方案,最终希望能得到全局最优解。这种策略的核心在于“最优”二字,意味着我们追求的是以最少的时间和精力,快速获得正确的结果。

        然而,“希望得到全局最优解”就表示算法>贪心算法并不意味着一定能得到全局最优解。实际上,并不是所有问题都可以通过贪心策略解决。为了确保贪心策略的有效性,需要对其进行严格的证明。而且,不同的问题往往需要采用不同的贪心策略。

        如果你觉得这一点仍然比较抽象,接下来我将通过5道具体的例题来详细说明算法>贪心算法的应用及其背后的思路。

2. 按身高排序

2418. 按身高排序 - 力扣(LeetCode)

这道题要求很简单,根据身高排序,但是输出的是名字。对身高排序很简单,可以直接用sort,但是真正需要排序的数组是name姓名数组。但是比较方法又是根据身高比较的,所以想一个办法绑定这两个数组。可以使用一个中间数组index下标数组,里面存放每个下标,然后对index数组排序,比较的规则可以自己写入用身高大小排序。排序之后的index数组就是按照身高下标来排序的了,比如index[0]的值为2就表示身高最高的人的下标为2,那么应该先输出name[2]的值。

2.1 代码实现

java">class Solution {public String[] sortPeople(String[] names, int[] heights) {int n = names.length;Integer[] index = new Integer[n];for(int i = 0; i < n; i++) index[i] = i;Arrays.sort(index, (a, b) -> heights[b] - heights[a]);String[] ret = new String[n];for(int i = 0; i < n; i++) ret[i] = names[index[i]];return ret;}
}

3. 优势洗牌

870. 优势洗牌 - 力扣(LeetCode)

题目解析:可以任意重组nums1的顺序,并且该顺序可以让nums1和nums2依次比较大小时,nums1优胜的次数更多。

该题的贪心策略跟田忌赛马很像,可以对nums1和nums2数组都按从小到大排序。然后再依次比较如果第一个位置nums1就小于nums2,相当于两个数组最小的值比较nums1都输了,此时把这个最小的数去匹配nums2最大的数,然后nums1再用下一个数继续比较nums2的数。依次类推。这样做的好处就是知道nums1最小的数已经对于nums2中的任何数字都取得不了优胜了,那么就不要选择匹配当前nums2最小的数,选择匹配最大的数,这样就可以留着nums1最大的数去匹配nums2前面的数,增大优胜的概率。

上图为整个逻辑流程图,依次扫描nums1数组的每个数,每次扫描都可以确定扫描的数匹配nums2的哪一个数。匹配规则为当前nums1扫描的数小于等于nums2[left]的数就让其匹配nums2[right]的数,否则匹配nums2[left]的数。

还需要注意的一点,这样的做法并不是最终答案,因为我们只能改变nums1的顺序不能改变nums2的,要根据原有的nums2的顺序,去填入nums1的值。所以该题依然需要一个中间变量下标数组去绑定两个数组下标的对应关系。

3.1 代码实现

java">class Solution {public int[] advantageCount(int[] nums1, int[] nums2) {int n = nums1.length;Integer[] index = new Integer[n];for(int i = 0; i < n; i++) index[i] = i;Arrays.sort(index, (i, j) -> nums2[i] - nums2[j]);Arrays.sort(nums1);int[] ret = new int[n];int right = n - 1, left = 0;for(int x : nums1){if(x  > nums2[index[left]]) ret[index[left++]] = x; // index[left]表示当前nums2最小值的下标else ret[index[right--]] = x; // index[right]表示当前nums2最大值的下标}return ret;}
}

4. 最长回文串

409. 最长回文串 - 力扣(LeetCode)

这道题要构造回文串,构成回文串有两种可能,一种是回文串中每个字母都是偶数,这样可以对称的分为两边构成回文,还有一种是偶数对称之后,中间单夹一个任意字母。

故这道题的贪心思路很简单,首先就需要统计字符串中每个字母的个数,这里可以有一个优化的小tip就是不适用map表来统计,而是使用数组来代替map表,因为大小字母的asc码值最大也不超过126,所以新建一个大小为126的int数组就可以将所有字母的个数统计完整。

继续优化:可以在循环字符串时一边统计字母个数时一边更新长度,因为只要统计到当前字母的个数等于2了,就可以把它往回文串里面加,让ret长度加2,然后再让hash表中该字母的个数重置为0。现在还有一个问题,当循环完成之后就是最终答案了吗?其实不是,因为循环里面统计长度的规则只考虑了偶数回文串的情况,这时需要判断ret的值是否小于字符串s的长度,如果小于说明还可以有单的字母加进去,这个字母可以是字符串中剩下字母中的任何一个。那么此时更新ret加1,否则直接返回ret。

4.1 代码实现

java">class Solution {public int longestPalindrome(String s) {int[] hash = new int[126];char[] ss = s.toCharArray();int ret = 0;for(char ch : ss){hash[ch] += 1;if(hash[ch] == 2){ret += 2;hash[ch] = 0;}}return ret < s.length() ? ret + 1 : ret;}
}

5. 增减字符串

942. 增减字符串匹配 - 力扣,然后(LeetCode)

 题目解析:输出的int数组中每个位置的值都是由0-n组成的,n为s字符串的长度。每个位置的值要根据s字符串的字母确定,例如示例1中,s字符串的长度为4,所以最终返回的int数组长度为n + 1。s字符串中第一个字母是I表示,int数组要进行上升,比如0到4就是一个上升。第二个字母是D表示要下降,4到1就是下降。以此类推。

贪心策略,遇到字母是I上升趋势的时候,确定当前int数组的数字为0-n中剩下可以挑选的数字中的最小的一个,因为选择最小的一个下一个位置的数字就只用受下一个字母的条件限制,而不用管上一个字母的限制,因为此时的任何数字都会比最小的数字大。拿示例1举例,第一个字母是I,如果此时int数组不选择0选择其他数字比如1。第二个字母是D,选择的数字不能是0和1,1被选过了,也不能选0因为0比1小,不满足第一个字母的I。但是如果第一次选择0,第二次选择数字的时候就不用考虑前一个字母的条件,因为剩下的数字1-n都比0大,所以只用考虑第二个字母D下降,同理此时应该选择最大的数字n,因为下一个选择的数字都可以从剩下的数中任意挑选,并且肯定满足条件。

5.1 代码实现

java">class Solution {public int[] diStringMatch(String s) {int n = s.length();int[] ret = new int[n + 1];int left = 0, right = n;for(int i = 0; i < n; i++){if(s.charAt(i) == 'I') ret[i] = left++;else ret[i] = right--;}ret[n] = left;return ret;}
}

6. 分发饼干

455. 分发饼干 - 力扣(LeetCode)

 这道题跟优势洗牌思路一样,就是对两个数组进行排序,然后依次比较,如果不满足当前孩子的胃口就让饼干数组往后一位继续比较知道满足为止。贪心的策略就是尽量用小的饼干尺寸去满足孩子胃口。

6.1 代码实现

java">class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g); Arrays.sort(s);int ret = 0;for(int i = 0, j = 0; i < g.length && j < s.length; j++){if(s[j] >= g[i]){i++; ret++;}}return ret;}
}


http://www.ppmy.cn/devtools/135060.html

相关文章

2023年MathorCup数学建模A题量子计算机在信用评分卡组合优化中的应用解题全过程文档加程序

2023年第十三届MathorCup高校数学建模挑战赛 A题 量子计算机在信用评分卡组合优化中的应用 原题再现&#xff1a; 在银行信用卡或相关的贷款等业务中&#xff0c;对客户授信之前&#xff0c;需要先通过各种审核规则对客户的信用等级进行评定&#xff0c;通过评定后的客户才能…

Mysql-DQL条件查询

文章目录 条件查询比较运算符逻辑运算符范围like 关键字排序单列顺序组合排序 聚合函数分组基本的分组流程参数的区别 limit 语句limit 语法格式limit 的使用场景 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Mysql专栏&#xff1a;点击&#xff01; ⏰…

本草智链:中药实验管理的区块链应用

5系统详细实现 5.1 管理员模块的实现 5.1.1 教师信息管理 中药实验管理系统的系统管理员可以管理教师&#xff0c;可以对教师信息添加修改删除以及查询操作。具体界面的展示如图5.1所示。 图5.1 教师信息管理界面 5.1.2 学生信息管理 系统管理员可以查看对学生信息进行添加&a…

Ubuntu 的 ROS 操作系统 turtlebot3 gazebo仿真

引言 TurtleBot3 Gazebo仿真环境是一个非常强大的工具&#xff0c;能够帮助开发者在虚拟环境中测试和验证机器人算法。 Gazebo是一个开源的3D机器人仿真平台&#xff0c;它能支持物理引擎&#xff0c;允许机器人在虚拟环境中模拟和测试。结合ROS&#xff0c;它能提供一个完整的…

介绍一下整数在内存的储存形式(c基础)

整数在内存中以补码形式储存(32位机器) 介绍三码 原码 反码 补码 正数 原码反码补码三码合一 把整数以二进制形式写出在前面补零(保证32位) 负数 原码&#xff08;第一位为符号位负数为1&#xff0c;正数为0&#xff09; 把整数以二进制形式写出在前面补零&#xff08…

室内定位论文精华-无人机与机器人在地下与室内环境中的自主导航与定位新技术

天文导航算法在低成本视觉系统中的应用 关键词 天文导航;自主无人机;GNSS拒止环境;稳定成像系统;星图识别;姿态估计;位置估算 研究问题 现代无人驾驶飞行器(UAV)中,很少使用天文学导航技术。传统的天文学导航依赖于稳定的成像系统,这不仅体积大且重量重,难以满足…

RabbitMQ高效的消息队列中间件原理及实践

RabbitMQ&#xff1a;高效的消息队列中间件及其 PHP 实现 一、什么是 RabbitMQ&#xff1f; RabbitMQ 是一个开源的消息队列中间件&#xff0c;使用 Erlang 编写&#xff0c;遵循 AMQP&#xff08;Advanced Message Queuing Protocol&#xff09;协议。它的主要功能是提供一种…

Failed to create a temp file - Jenkins 无法创建任务

近日&#xff0c;突然发现任务集群的jenkins异常退出了&#xff0c;没有任何的迹象。后来排查到jenkins的job的日志后&#xff0c;找到了以下错误日志。 Started by user unknown or anonymous Running as SYSTEM Building in workspace /Users/xxxxx/work/jenkins2/jenkins_h…