【贪心算法】贪心算法四

news/2024/11/26 3:11:20/

算法>贪心算法

  • 1.最长回文串
  • 2.增减字符串匹配
  • 3.分发饼干
  • 4.最优除法

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

1.最长回文串

题目链接: 409. 最长回文串

题目分析:

在这里插入图片描述

给一个包含大小字母的字符串,从里面挑选出来一些字母构成一个最长回文串,然后返回它的长度。

算法原理:

我们可以先统计每个字符的个数,为什么先统计次数呢,我们发现构建的回文串从中间劈开后,相同的字符左边放一个右边放一个。把所有能用的字符能放就全部放那就是我们的贪心策略。

所以先统计每个字符出现的个数,然后以中间线为分割线左边放一个右边放一个。

在这里插入图片描述
上面是我们的总体思路,接下来考虑一下细节问题。字符可能是偶数个,也可能是奇数个。如果是偶数的话太好了全都放。但是如果是奇数个就有问题了,因为我们要左边放一个右边放一个要能对称,此时最贪心的想法就是奇数-1变成偶数然后放。

在这里插入图片描述
虽然上面把一左一右的搞定的,但是还是有一个小问题,回文串中间这个分割线也是可以摆一个字符,只要我们在统计字符个数的时候发现某个字符出现了奇数次,一左一右我们肯定会漏这一个字符,所以中间这里可以把这个字符加上。

在这里插入图片描述
所以我们策略出来了,如果偶数全部加上,如果是奇数 - 1 后在加上,所以情况都考虑完,在考虑中间这个地方能不能摆,取决于有没有出现一个字符出现奇数次,如果出现就在中间摆一个。

写代码的时候奇偶是可以放在一块写的,假设字符出现 x 次,ret += x / 2 * 2。因为 算 / 2 是一个向下取整 , 7 / 2 = 3, 3 * 2 =6,相当于就是7 - 1 = 6,如果是偶数 / 2 * 2 是不变的。

还有在最后要统计一下是否有个字符出现奇数次,其实也没有必要,其实用最后统计出来的ret和s.size()比较一下,如果小于 ret + 1,原因就是如果字符都出现偶数那么ret = s.size() 一左一右,如果小于那肯定有字符出现了奇数次。

class Solution {
public:int longestPalindrome(string s) {// 1.计数 -- 用数组模拟哈希表int hash[127] = {0};for(auto ch : s) hash[ch]++; // 2.统计结果    int ret = 0;for(auto x : hash) ret += x / 2 * 2;if(ret < s.size()) ++ret;return ret;}
};

2.增减字符串匹配

题目链接: 942. 增减字符串匹配

题目分析:

在这里插入图片描述

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ,其中:

如果 perm[i] < perm[i + 1] ,那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ,那么 s[i] == ‘D’

其实s字符串就是描述[0,n]组成的数组的序列增减情况。

在这里插入图片描述

算法原理:

下面用一个例子说明一下

在这里插入图片描述
刚开始要符合一个增的形式,此时有很多选项可以放这里,那放5好不好?肯定是不好的,5是当前最大的数,接下来是一个增长趋势这里放5,下一个放谁都增不了,这里就有一个贪心的策略,我不会把最大的数放这里,因此我就贪到底,把最小的数放这里。

在这里插入图片描述

接下来是降,如果是降,会把1放这里吗?绝对不会,如果把最小的数放在这里接下来还降个锤子,此时还是贪到底,把最大的数放这里。

在这里插入图片描述
同理后面都是这样选择的。

在这里插入图片描述

最后在把最后一个数放在后面

在这里插入图片描述
我们的贪心策略:

  1. 当遇到 " I ",选择当前最小的那个数
  2. 当遇到 " D ",选择当前最大的那个数

这里简单证明一下我们这个策略是正确的。

当在增长的时候,如果我们选择较小的数摆,那无论接下来下一个数选谁绝对都是符合情况的。后面的数都是比我大。所以是绝对正确的。

在这里插入图片描述

同理如果第一个是降的话,拿最大的数摆,那括号里待选的数都是比我选的,无论较小的数如何排列,接下来下一个数绝对呈现下降趋势。

在这里插入图片描述

处理完之后,接下来对括号里面处理是一样的,这其实就是一个递归的过程,当算法一直递归下去的时候,每一个摆放都是合理的,所以我们和用归纳法来证明我们这个贪心策略是正确的。

在这里插入图片描述

class Solution {
public:vector<int> diStringMatch(string s) {int left = 0, right = s.size();// 用 left,right 标记最小值最大值vector<int> ret;for(auto ch : s){if(ch == 'I') ret.push_back(left++);else ret.push_back(right--);}ret.push_back(left); // 把最后一个数放进去return ret;}
};

3.分发饼干

题目链接: 455. 分发饼干

题目分析:

在这里插入图片描述

有一群孩子,还有一堆饼干,拿着这些饼干去喂这些孩子,问最多能喂饱多少孩子?喂饱孩子的要求是饼干尺寸要大于等于孩子的胃口。

算法原理:

看下面这个示例,我们来想贪心策略。首先我们要将胃口和饼干升序排列,如果数组乱序我们找的时候还需要去遍历数组很麻烦。所以我们先要把数组排序。

在这里插入图片描述

如果搞清题意的话,不知道会不会想到《优势洗牌 - 田忌赛马》这道题,田忌赛马这道题也是给数组之后我们给数组排下序,然后尽可能多的去赢。这道题是数组排序后,然后挑一些去满足上面的数,其实也是打败它。所以田忌赛马这道题的经验是有可能应用到我们这道题的。

这里我们就针对某个孩子然后去挑选饼干。

此时挑的时候发现,当前最小的饼干就能满足孩子,此时贪心就来了,如果最小的饼干就能这个孩子,后面的饼干肯定更能满足,此时我们的贪心就是选择较小的饼干去满足,尺寸较大的饼干可以去满足胃口更大的孩子。

在这里插入图片描述

如果此时最小的饼干满足不了孩子胃口,在田忌赛马哪里我们是让它直接去拖累掉最后一个元素,但是我们这里是喂孩子,不能拿最小的饼干去喂孩子,所以当我们发现当前数组中最小的饼干都不能满足孩子胃口的时候,那上面所有孩子胃口都不能满足,因为我们是升序排序的,所以当前这个饼干删掉,然后针对这个孩子,再去选前提饼干。

在这里插入图片描述

后序操作如上,直到所有饼干用完,那 i 前面这堆孩子是全部都能满足的,返回它的数量就可以了。

在这里插入图片描述

总结一下贪心策略:

排序,针对当前胃口最小的孩子,然后挑选饼干

  1. 能满足,直接喂
  2. 不能满足,直接删掉这个饼干
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 先排序sort(g.begin(), g.end());sort(s.begin(), s.end());// 利⽤双指针找答案int ret = 0, m = g.size(), n = s.size();for(int i = 0, j = 0; i < m && j < n; ++i, ++j){while(j < n && s[j] < g[i]) ++j;// 找饼⼲if(j < n) ret++;}return ret;}
};

证明:

证明方法:交换论证法

最优解在不失去最优性的前提下能调整成贪心解,就说明贪心解是正确的。

从左往右扫描贪心解和最优解饼干匹配情况,当第一次遇到匹配不相等,此时根据贪心解的策略,分两种情况讨论:

  1. 喂不饱

贪心策略是删去这个饼干,最优解如果和贪心解不一样的话,最优解会让这个饼干去喂某个孩子。但是这种情况是不可能发生的,因为我们是升序的,如果当前饼干连最小的孩子都不能满足,那后面的孩子也满足不了,所以这个贪心和最优是一样的,都是直接删掉。

在这里插入图片描述
2. 能喂饱

能喂饱我们的贪心是直接喂,最优解其实是有两种情况,要么这个饼干喂后面的孩子,要么这个饼干压根就没用。这个孩子也有情况情况,要么后面有饼干来喂这个孩子,要么没有饼干来喂这个孩子。两两结合我们要分四种情况讨论。

在这里插入图片描述

一:饼干用了,这个孩子也被后面饼干满足了。
二:饼干用了,孩子没被满足
三:饼干没用,孩子被满足
四:饼干没用,孩子没被满足

考虑第一种情况:

在这里插入图片描述

此时调整就是,就是绿色情况,只要证明绿色和紫色同样优秀就可以了

紫色的线有两个不等式,b > x1, a > x2,又因为升序 b > a,所以 b > a > x2,
所以b一定能喂x2,a调整喂x1贪心告诉我们是可以的。 调整前喂得饱,调整后也喂得饱,所以第一种情况是可以的。
在这里插入图片描述

考虑第二种情况:
饼干喂了后面孩子x2,但是x1这个孩子没人喂。

此时调整a去喂x1也不会破坏最优,把a喂x2可以填饱肚子,那此时不喂x2,去喂x1也是可以填饱肚子,并且孩子个数没有发生改变,所以第二种情况是可以的。

在这里插入图片描述

考虑第三种情况:
没有用a这个饼干,x1这个孩子被后面b喂。

此时调整,不用b喂了,用a喂,也是可以的,在贪心解里知道a 是可以满足x1的,所以也是可以的。

在这里插入图片描述

考虑第四种情况:
没有a饼干,也没有x1这个孩子

此时调整a去喂x1,相当于在之前最优解的情况下又多了一个能喂饱的孩子,所以贪心更优最优解,所以绝对是可以的。

在这里插入图片描述

综上所述,无论是上述情况哪一种我们都可以调整的,所以能喂饱也是可以的。
此时我们的贪心就是正确的。

4.最优除法

题目链接: 553. 最优除法

题目分析:

在这里插入图片描述
给定一正整数数组 nums,nums 中的相邻整数将进行浮点除法。

例如,nums = [2,3,4],我们将求表达式的值 “2/3/4”。
但是,你可以在任意位置添加任意数目的括号,来改变算数的优先级。

在这里插入图片描述

你需要找出怎么添加括号,以便计算后的表达式的值为最大值。

题意其实就是数组给一堆数,数中间其实都有除法的,此时让我们任意位置添加一些括号,使表达式的值为最大值,最后返回的是以字符串格式返回具有最大值的对应表达式。

注意:你的表达式不应该包含多余的括号。

原本括号里面顺序是3/4/5,现在多添加一个括号还是3/4/5。

在这里插入图片描述
算法原理:

举一个例子来提取我们的贪心策略

在这里插入图片描述

这个时候我们要明白一点,在这个表达式中添加括号最终都会转换为 x/y 的形式。也就是从这些数中挑一些放在分子上,一些数放在分母上,

在这里插入图片描述
我们最终要的是 x/y 是最大的,一个分数要最大,要么就是分子变大,要么就是分子变小。接下来我们设计表达式就是尽可能让分子大,分母小。这就是我们的贪心方向。

在这里插入图片描述

还有一点无论在表达式哪里填上括号,a都是在分子上,b都是在分母上,所以a和b这两个无法通过添加括号去改变的a/b。所以最终a一定在分子上,b一定在分母上。

在这里插入图片描述

现在可供我们选择的就是c、d、e、f,为了使最终结果最大,我们就想无脑的把c、d、e、f和a一起放在分子上。

在这里插入图片描述

这里可以用贪心优化就是因为这个值乘起来是越来越大的

在这里插入图片描述

贪心策略:除了前两个数以外,其余的数全部放在分子即可

如何实现贪心策略呢?
这里我们用小学就学过的知识,负负得正。除除得正。因此我们仅需在b之前填一个(,f后填一个)

在这里插入图片描述

括号里面得除法全都因为括号外面得除法变成除除得正,

在这里插入图片描述

class Solution {
public:string optimalDivision(vector<int>& nums) {int n = nums.size();// 先处理两个边界情况if(n == 1) return to_string(nums[0]);if(n == 2) return to_string(nums[0]) + '/' + to_string(nums[1]);string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);for(int i = 2; i < n; ++i){ret += '/' + to_string(nums[i]);}ret += ')';return ret;}
};

http://www.ppmy.cn/news/1549970.html

相关文章

Flutter将应用打包发布到App Store

使用Flutter将应用打包发布到App Store的详细步骤及流程图&#xff1a; 流程图 #mermaid-svg-X09iOP2FtRxwKsWw {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-X09iOP2FtRxwKsWw .error-icon{fill:#552222;}#mermai…

IDEA+Docker一键部署项目SpringBoot项目

文章目录 1. 部署项目的传统方式2. 前置工作3. SSH配置4. 连接Docker守护进程5. 创建简单的SpringBoot应用程序6. 编写Dockerfile文件7. 配置远程部署7.1 创建配置7.2 绑定端口7.3 添加执行前要运行的任务 8. 部署项目9. 开放防火墙的 11020 端口10. 访问项目11. 可能遇到的问题…

C语言练习.if.else语句.strstr

今天在做题之前&#xff0c;先介绍一下&#xff0c;新学到的库函数strstr 想要使用它&#xff0c;要先给它一个头文件<string.h> char *strstr(const char*str1,const char*str2); 首先&#xff1a;1.strstr的返回值是char&#xff0c;字符类型的。 2.两个实参&#xff…

2025-2026财年美国CISA国际战略规划(下)

文章目录 前言四、加强综合网络防御&#xff08;一&#xff09;与合作伙伴共同实施网络防御&#xff0c;降低集体风险推动措施有效性衡量 &#xff08;二&#xff09;大规模推动标准和安全&#xff0c;以提高网络安全推动措施有效性衡量 &#xff08;三&#xff09;提高主要合作…

k8s1.30.0高可用集群部署

负载均衡 nginx负载均衡 两台nginx负载均衡 vim /etc/nginx/nginx.conf stream {upstream kube-apiserver {server 192.168.0.11:6443 max_fails3 fail_timeout30s;#server 192.168.0.12:6443 max_fails3 fail_timeout30s;#server 192.168.0.13:6443 max_fails3…

如何在 .gitignore 中仅保留特定文件:以忽略文件夹中的所有文件为例

在日常的开发工作中&#xff0c;使用 Git 来管理项目是不可或缺的一部分。项目中的某些文件夹可能包含大量的临时文件、生成文件或不需要版本控制的文件。在这种情况下&#xff0c;我们通常会使用 .gitignore 文件来忽略这些文件夹。然而&#xff0c;有时我们可能希望在忽略整个…

PDF内容提取,MinerU使用

准备环境 # python 3.10 python3 -m pip install huggingface_hub python3 -m pip install modelscope python3 -m pip install -U magic-pdf[full] --extra-index-url https://wheels.myhloli.com下载需要的模型 import json import osimport requests from huggingface_hub…

力扣hot100-->栈/单调栈

栈/单调栈 1. 20. 有效的括号 简单 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每…