贪心算法篇——万千抉择中的唯一考量，最优解追寻的跬步累积（5）

用户11379153

发布于 2025-11-05 16:24:01

830

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

引言

初篇我们介绍了贪心算法的相关背景知识，本篇我们将结合具体题目，进一步深化大家对于贪心算法的理解和运用。

一、最长回文串

1.1 题目链接：https://leetcode.cn/problems/longest-palindrome/description/

1.2 题目分析：

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的最长的回文串的长度。
注意区分大小写
构造回文串的途中字母的顺序可以任意调换

1.3 思路讲解：

由于可以任意调换顺序，因此只要同一个字符出现的次数为偶数次，一定可以进行对称回文。故具体步骤如下：

利用哈希存储每个字符出现的次数
最长回文串的长度即为各个字符的最大偶数次再加1（1为单个字符作为最中间时的更长情况）

1.4 代码实现：

class Solution {
public:
    int longestPalindrome(string s) {
        int hash[127];
        for(auto ch :s) hash[ch]++;
        int len=s.size();
        int ret=0;
        for(int x :hash)
        {
            ret+=x/2*2;//偶数直接对称，奇数舍去一个
        }
        return ret<len?ret+1:ret;//最终再判断是否需要补一个奇数串作为中点
        
    }
};

二、增减字符串匹配

2.1 题目链接：https://leetcode.cn/problems/di-string-match/description/

2.2 题目分析：

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
如果 perm[i] < perm[i + 1] ，那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ，那么 s[i] == ‘D’
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。

2.3 思路讲解：

即要求返回一个[0,n]的序列，对应长度为n的字符串，要求满足其对应匹配规则。

回想之前的波峰波谷类型，可以采用相似的方法进行处理：

s[i]='I’表示该位置为波谷，应该选取尽量大的数字
s[i]='D’表示该位置为波峰，应该选取尽量小的数字

2.4 代码实现：

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n=s.size();
        vector<int> ret;
        int left=0,right=n;//left表示小数，right表示大数
        for(auto ch :s)
        {
            if(ch=='I') ret.push_back(left++);//选取最小的
            else ret.push_back(right--);//选取最大的
        }
        ret.push_back(left);
        return ret;
        
    }
};

三、分发饼干

3.1 题目链接：https://leetcode.cn/problems/assign-cookies/description/

3.2 题目分析：

给定两个数组s[i]和g[i]，前者表示饼干尺寸，后者表示孩子胃口
s[i]>=g[i]时，孩子i可以得到满足
求能满足的最大孩子数组

3.3 思路讲解：

观察样例可知，饼干数目可能小于孩子数目，因此我们可以沿用田忌赛马的思路。

先将两个数组排序。
针对胃⼝较⼩的孩⼦，从⼩到⼤挑选饼⼲： i. 如果当前饼⼲能满⾜，直接喂（最⼩的饼⼲都能满⾜，不要浪费⼤饼⼲）； ii. 如果当前饼⼲不能满⾜，放弃这个饼⼲，去检测下⼀个饼⼲（这个饼⼲连最⼩胃⼝的孩⼦都⽆法满⾜，更别提那些胃⼝⼤的孩⼦了）。

3.4 代码实现：

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int m=g.size(),n=s.size();
        //排序
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int ret=0;//最大数目
        int i=0,j=0;
        while(i<m && j<n)
        {
            //可以满足
            if(s[j]>=g[i])
            {
                j++;
                ret++;
                i++;//更新下标
            }
            else
            {
                j++;
            }
        }
        return ret;
    }
};

四、最优除法

4.1 题目链接：https://leetcode.cn/problems/optimal-division/description/

4.2 题目分析：

给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。
可以在任意位置添加任意数目的括号，来改变算数的优先级
以字符串格式返回具有最大值的对应表达式。

4.3 思路讲解

由于括号的添加位置和添加数量都是任意的，因此问题就转化为了求最大数除以最小数

贪⼼策略：

在最终的结果中，前两个数的位置是⽆法改变的。
因为每⼀个数的都是⼤于等于 2 的，为了让结果更⼤，我们应该尽可能的把剩下的数全都放在「分⼦」上。

4.4 代码实现：

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n=nums.size();
        string ret;
        if(n==1)
        {
            return to_string(nums[0]);
        }
        if(n==2)
        return to_string(nums[0])+'/'+to_string(nums[1]);
        ret+=to_string(nums[0])+"/("+to_string(nums[1]);
        for(int i=2;i<n;i++)
        {
            ret+='/'+to_string(nums[i]);
        }//全部存储在分子内
        ret+=')';
        return ret;
        
    }
};