算法沉淀——贪心算法四
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 <= 2000s 只由小写 和/或 大写英文字母组成
思路
首先我们想到如果某个字符出现偶数次，那么它一定可以构成回文串，所以我们利用这个思想将所有字符的偶数个都计入回文串的个数中，若该个数不超过给出的字符串长度，那么我们可以再加上任意字符，即为最长的回文字符串。
代码
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 } }; 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 <= 105s 只包含字符 "I" 或 "D" 思路 当遇到字符I时，为了让上升的数有更多选择空间，我们可以选择当前可选择最小的那个数，反之，选择最大的数。 代码 class Solution { public: vector int n=s.size(); int left=0,right=n; vector for(int i=0;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 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 1 思路 我们使用最小匹配的方式，将两个数组进行排序，找到每一个刚好能够逐个满足小孩的饼干，直至饼干消耗完结束。 代码 class Solution { public: int findContentChildren(vector 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 while(j if(j } 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 <= 102 <= nums[i] <= 1000对于给定的输入只有一种最优除法。 思路 我们可以通过例子发现，前两个位置的数无法被改变，在这道题中，为了让结果最大，我们应将第二个位置之后的数都变成分子，所以我们只需要将括号加在第二位至最后一位即可得出最大数。 代码 class Solution { public: string optimalDivision(vector 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 } ret+=")"; return ret; } }; 推荐链接
发表评论