网站推广的阶段目标,建设自己的网站怎么这么难,珠海广告设计与制作公司,衡水网站制作报价算法沉淀——贪心算法四 01.最长回文串02.增减字符串匹配03.分发饼干04.最优除法 01.最长回文串
题目链接#xff1a;https://leetcode.cn/problems/longest-palindrome/
给定一个包含大写字母和小写字母的字符串 s #xff0c;返回 通过这些字母构造成的 最长的回文串 。 … 算法沉淀——贪心算法四 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 ret0;for(auto ch:s) hash[ch];for(auto c:hash) retc/2*2;return rets.size()?ret1: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:vectorint diStringMatch(string s) {int ns.size();int left0,rightn;vectorint ret;for(int i0;in;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(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int ret0,mg.size(),ns.size();for(int i0,j0;imjn;i,j){while(jns[j]g[i]) j;if(jn) ret;}return ret;}
};04.最优除法
题目链接https://leetcode.cn/problems/optimal-division/
给定一正整数数组 numsnums 中的相邻整数将进行浮点除法。例如 [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(vectorint nums) {int nnums.size();string ret;if(n1) return to_string(nums[0]);else if(n2) return to_string(nums[0])/to_string(nums[1]);else{retto_string(nums[0])/(to_string(nums[1]);for(int i2;in;i) ret(/to_string(nums[i]));}ret);return ret;}
};
