【贪心算法】贪心算法四
贪心算法四
- 1.最长回文串
- 2.增减字符串匹配
- 3.分发饼干
- 4.最优除法
点赞 👍👍收藏 🌟🌟关注 💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.最长回文串
题目链接： 409.\ 最长回文串
题目分析：
给定一个由大小写字母组成的字符串S，请从中选出一组字符组成其最长回文子序列，并返回该子序列的长度
算法原理：
为了便于后续操作，我们可以首先统计每个字符的数量。那么为什么要先进行次数统计呢？观察到回文串构造过程中的规律是：将相同的字符均匀地分配在左右两侧。具体而言，在构建回文串时，在左右两侧各放置相同数量的一种字符就是我们采用的主要策略——贪心算法的核心原理。
所以为了统计每个字符出现的数量 我们需要将数据按中间线分割后分别放置于左右两侧
我们首先阐述了整体思路，并进而探讨了相关细节问题。字符的数量可能是偶数量也可能是奇数量。对于偶数量的字符处理较为直接；然而当字符数量为奇数量时则存在问题需要解决：因为左右各放一个必须对称。因此最贪心的策略是将奇数量减一转换为偶数量进行处理。
尽管在前面已经实现了左右两边的任务分配与协调工作（实现了），但其实还存在一个小问题：在处理回文串中间的位置时也需要特别考虑进去。回文串中间的位置也可以放置一个辅助标记符，在后续的数据处理中确保不会遗漏任何关键信息点：当我们在统计每个字符出现次数时发现有某个字符出现奇数次时，在左右两边各放一个的话就会遗漏它；因此，在这种情况下建议将该多余的关键信息点插入到中间位置以实现完整性保障功能。
因此制定出了一套方案。将所有偶数相加，并且对于奇数值的情况，则是先将其减一后再相加。这样所有的情况都已考虑到，在考虑中间这个地方是否能摆放的话，则要看是否存在任何一个字符其出现次数为奇数次。如果存在，则可在中间位置放置该字符
在编程过程中处理字符数量时可以将奇偶性统一处理，在具体实现中假设某个字符出现了x个。我们需要计算 ret += (x // 2) * 2。其中计算除法时采用向下取整的方式：例如7//2=3（舍去小数部分），再乘以二得到6；而如果是偶数则除以二再乘以二结果不变。
另外一种优化方法是：实际上没有必要在最后单独统计每个字符的出现次数；比如可以通过比较最后计算出的ret与字符串长度s.size()来判断是否存在任何一个字符出现奇数次；比如可以通过比较最后计算出的ret与字符串长度s.size()来判断是否存在任何一个字符出现奇数次；具体来说就是：如果通过某种方式得到的结果ret小于 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;
}
};
cpp
2.增减字符串匹配
问题链接：第942题 增删字符串匹配（LeetCode）
题目分析：
属于范围[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作为候选值之一，在后续阶段出现持续增长的趋势时这一位置将无法承受更大的增量因此必须采取另一种策略即从最小值开始逐步递增这样既能满足递增的要求又能避免过大的数值堆积
在下一步中进行递减操作；假如是递减的话，请问是否将数值1放置到这里？答案是不会；因为一旦选择最小值放置在此处，则后续的操作仍会继续递减；此时仍然倾向于向底部移动；而将最大的数值放置此处反而会导致更大的损失
同理后面都是这样选择的。
最后在把最后一个数放在后面
我们的贪心策略：
- 当遇到 " I "，选择当前最小的那个数
- 当遇到 " 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;
}
};
cpp
3.分发饼干
题目标签：455号问题：分发饼干
题目分析：
一群充满活力的孩子面前摆着一堆形状各异的饼干，在这个过程中想知道能够满足多少孩子的饱腹需求吗？要确保每个孩子的食量都能被满足，则所需饼干的大小必须至少与孩子的食量需求相当。
算法原理：
以下面这个示例为例，在探讨贪心策略的过程中我们会遇到一个关键问题：为了便于后续操作我们需要将数据按照一定的顺序进行排列处理。具体来说如果我们遇到数组元素无序的情况在查找的过程中需要频繁地遍历整个数组以寻找符合条件的元素。因此，在开始处理之前我们需要对数据进行排序以提高效率并确保算法能够顺利运行。
若能准确理解题目意图，则可能会联想到一道类似的题目："优势洗牌——田忌赛马"；同样的问题，在田忌赛马中也涉及将一组数据排序，并且尽量多地击败它们。在排序之后出现的问题通常是：选择一部分元素使其能够击败其他元素中的大部分；这种解法的经验可能适用于当前问题。
这里我们就针对某个孩子然后去挑选饼干。
当尝试为孩子挑选时, 发现最小的一块饼干足以满足孩子的需求, 这时候贪心算法便发挥了作用, 因为如果最小的一块饼干能满足孩子的需求, 那么更大的饼干显然能够更好地满足需求, 我们的贪心策略就是优先选择较小尺寸的饼干来解决当前的需求, 尺寸较大的饼干则可以用来应对那些有更大胃口的孩子
当最小的饼干无法满足孩子的食欲时，在田忌赛马的情境下，则让其直接拖累到最后一个元素；然而，在这里则是喂孩子，请将当前数组中最小的饼干移除，并针对该儿童重新选择前导饼干。
后续操作按照上述步骤进行，在所有饼干被耗尽时停止。那么i前面这一堆孩子都是能够满足条件的，返回这一堆的数量即可。
总结一下贪心策略：
排序，针对当前胃口最小的孩子，然后挑选饼干
- 能满足，直接喂
- 不能满足，直接删掉这个饼干
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;
}
};
cpp
证明：
证明方法：交换论证法
最佳方案可以在保证最佳方案不变的前提下能够转换为贪心策略，并由此证明了贪心策略的正确性。
按顺序扫描贪心解与最优解之间的饼干配对关系，在首次出现配对结果不符时，则依据贪心算法的原则分两种情况进行详细分析：
- 喂不饱
按照贪心策略选择，则会将此饼干舍弃。若最优解与贪心解不同，则会将此饼干分配给某个孩子。然而这种情况实际上无法出现。由于我们采用的是有序排列的方式，
因为当前的饼干无法满足最小的孩子的需求，
则后续的所有孩子自然也无法得到满足。
因此该贪心策略与整体最优解一致。
2. 能喂饱
我们的贪心能够被满足的方式是直接给予食物。在寻找最优解的过程中需要注意的是有两种不同的情形：一种是将当前饼干供给后面的某个孩子；另一种则是当前饼干无法满足任何后续需求。对于每一个孩子来说情况都有所不同：要么后续会有饼干来完成其需求；要么则会因为缺乏足够的食物而无法得到满足。在上述各种可能性下我们需要分别探讨这四种不同的组合方式以找到最合适的解决方案。
一：当使用后，“后面的奖励”让这个孩子感到激励。
二：尽管使用了奖励，“孩子的兴趣”却没有得到回应。
三：如果没有给予奖励，“孩子的兴趣”反而得到了回应。
四：既没有给予奖励，“孩子的兴趣”也没有得到回应。
考虑第一种情况：
此时调整就是，就是绿色情况，只要证明绿色和紫色同样优秀就可以了
该线包含两个不等式：b > x_1和a > x_2；由于b按升序排列位于a之后（即b \geq a），因此有b \geq a \geq x_2；这样就能确保x_2被喂饱；通过调整a来喂养x_1（在贪心算法的指导方针下）是可行的）。在未进行任何调整时即可满足条件，在进行了相应的调整后同样能够满足条件。
考虑第二种情况：
饼干喂了后面孩子x2，但是x1这个孩子没人喂。
此时将a切换至喂养x_1不会影响整体最佳状态；若不选择喂养x_2，
则转而选择喂养x_1同样能够满足需求，
并且孩子的数量并未发生改变；
因此这种情形是可行的。
考虑第三种情况：
没有用a这个饼干，x1这个孩子被后面b喂。
在此时采取调整措施，并非必须使用b进行喂养；转而采用a进行喂养也同样可行。在贪心解中已知a能够满足x₁的要求；因此同样可行。
考虑第四种情况：
没有a饼干，也没有x1这个孩子
当切换资源a至给养x1时
综合以上分析可知, 不管哪种情况我们均有可能进行调整, 因此能够喂饱也是可行的. 此时我们的贪欲应当是恰当的.
4.最优除法
题目ID：553. 最优除法
题目分析：
给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。
例如nums = [2, 3, 4]时，“2/3/4”的值是多少？
然而，在任何位置插入任意数量的括号后，“2/3/4”的优先级会有所变化。
你需要找出怎么添加括号，以便计算后的表达式的值为最大值。
题意即为向数组中输入一组数值；这些数值之间都存在除法运算；我们可以在任意位置插入括号；使得整个表达式的计算结果达到最大值；最终输出应是以字符串形式表示具有最大计算结果的表达式。
注意：你的表达式不应该包含多余的括号。
原本括号里面顺序是3/4/5，现在多添加一个括号还是3/4/5。
算法原理：
举一个例子来提取我们的贪心策略
这个时候我们必须意识到，在这个表达式中放置括号的结果总是转化为 x/y 的形式。也就是说，在这些数值中我们需选择将某些数值置于分子位置其余数值则分配到分母部分。
我们的目标是让分数x/y达到最大值；为了使这个分数最大化；可以通过两种途径实现：一是通过增大x；二是通过减少y；这两种方法都可以达到目的；这也是我们在优化过程中需要遵循的原则
无论在哪种情况下，在表达式的任何地方加上括号时，
a始终位于分子位置，
而b始终位于分母位置。
因此，在这种情况下（即无论怎样添加括号），分数的形式始终是 a/b。
由此可见，在所有可能的情况下（即不管怎样添加括号），分数的形式一定是将 a 放置于分子位置而 b 放置于分母位置。
我们现在能够挑选出的就是选项c到f。以最大化最终结果为目标，在分子部分中我们需要将它们全部纳入分子部分。
这里可以用贪心优化就是因为这个值乘起来是越来越大的
贪心策略：除了前两个数以外，其余的数全部放在分子即可
通过建立贪心算法模型来实现这一策略。
基于基础数学法则：负数相乘得正数；除法运算结果为正值。
确保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;
}
};
cpp
