算法沉淀——贪心算法四（leetcode真题剖析）

算法沉淀——贪心算法四

• 01.最长回文串
• 02.增减字符串匹配
• 03.分发饼干
• 04.最优除法

01.最长回文串

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

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输出:1

示例 3：

输入:s = "aaaaaccc"
输出:7

提示:

• 1 <= s.length <= 2000
• s 只由小写 和/或 大写英文字母组成

思路

首先我们想到如果某个字符出现偶数次，那么它一定可以构成回文串，所以我们利用这个思想将所有字符的偶数个都计入回文串的个数中，若该个数不超过给出的字符串长度，那么我们可以再加上任意字符，即为最长的回文字符串。

代码

class Solution {
public:
    int longestPalindrome(string s) {
        int hash[128];
        int ret=0;
        for(auto ch:s) hash[ch]++;
        for(auto c:hash) ret+=c/2*2;

        return ret<s.size()?ret+1:ret; 
    }
};

02.增减字符串匹配

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

由范围 [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，则返回其中 任何一个 。

示例 1：

输入：s = "IDID"
输出：[0,4,1,3,2]

示例 2：

输入：s = "III"
输出：[0,1,2,3]

示例 3：

输入：s = "DDI"
输出：[3,2,0,1]

提示：

• 1 <= s.length <= 105
• s 只包含字符 "I" 或 "D"

思路

当遇到字符I时，为了让上升的数有更多选择空间，我们可以选择当前可选择最小的那个数，反之，选择最大的数。

代码

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n=s.size();
        int left=0,right=n;
        vector<int> ret;

        for(int i=0;i<n;i++){
            if(s[i]=='I') ret.push_back(left++);
            else ret.push_back(right--);
        }
        ret.push_back(left);
        return ret;
    }
};

03.分发饼干

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

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示：

• 1 <= g.length <= 3 * 104
• 0 <= s.length <= 3 * 104
• 1 <= g[i], s[j] <= 231 - 1

思路

我们使用最小匹配的方式，将两个数组进行排序，找到每一个刚好能够逐个满足小孩的饼干，直至饼干消耗完结束。

代码

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;
    }
};

04.最优除法

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

给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如， [2,3,4] -> 2 / 3 / 4 。

• 例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

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

示例 1：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

示例 2:

输入: nums = [2,3,4]
输出: "2/(3/4)"
解释: (2/(3/4)) = 8/3 = 2.667
可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。

说明:

• 1 <= nums.length <= 10
• 2 <= nums[i] <= 1000
• 对于给定的输入只有一种最优除法。

思路

我们可以通过例子发现，前两个位置的数无法被改变，在这道题中，为了让结果最大，我们应将第二个位置之后的数都变成分子，所以我们只需要将括号加在第二位至最后一位即可得出最大数。

代码

class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int n=nums.size();
        string ret;
        if(n==1) return to_string(nums[0]);
        else if(n==2) return to_string(nums[0])+"/"+to_string(nums[1]);
        else{
            ret+=to_string(nums[0])+"/("+to_string(nums[1]);
            for(int i=2;i<n;i++) ret+=("/"+to_string(nums[i]));
        }
        ret+=")";
        return ret;
    }
};