627. 最长回文串
给出一个包含大小写字母的字符串。求出由这些字母构成的最长的回文串的长度是多少。 数据是大小写敏感的，也就是说，"Aa" 并不会被认为是一个回文串。 样例 给出 s = "abccccdd" 返回 7 一种可以构建出来的最长回文串方案是 "dccaccd"。 这个题我踩了一个大坑，我先说我一开始想的思路啊，是这样的：要够成回文串除了最中间可以是奇数个相同的字母以外，两边的都必须是对称的，那么我用map统计每个字母出现的次数，然后出现偶数次的都可以加到回文串中，出现奇数个的我把奇数最大的那个加入回文串中，这样就可以得到需要的数目了啊。这样做的代码如下：
int longestPalindrome(string s) {
int res=0;
int ji=0;
map<char,int> num_of_letter;
for(auto ss:s)
{
num_of_letter[ss]++; //统计每个字符出现的个数
}
for(auto num:num_of_letter)
{
if(num.second%2==0) //如果这个字母是偶数个，肯定全部能放到回文串中
{
res+=num.second;
}
else //最后我们加上最大的奇数个数，放在最中间就可以了。
{
if(num.second>ji)
ji=num.second;
}
}
return res+ji;
// write your code here
}测试的时候一半的数据都通过了，但是还是出现了问题，我一开始也想不通为什么，甚至我把每个字母和次数都打印出来也没有看出端倪，于是和振哥交流了一下，我去泡了袋面吃，然后振哥说发现为什么了，知道原因之后只能说自己陷入自己挖的坑里了。 错误的原因是这样的，虽然说奇数个字母是不能放入回文串的，但是并没有人规定说是我必须把这奇数个都放进去，如果一个字母有5个的话我还是可以放4个进去啊。这样一想就知道错在哪里了，在原程序上要进行一些改动，着重要考虑两种情况，并不是简单的把奇数统计那里改一下就行了。 1:考虑全偶的情况。 2:考虑只有一个奇数个字母的情况，这样就要全部放进去 改了之后的代码如下：测试数据可以全部通过
int longestPalindrome(string s) {
if(s.size()==0)
return 0;
int res_ou=0;
int res_ji=0;
int ji=0;
map<char,int> num_of_letter;
for(auto ss:s)
{
num_of_letter[ss]++; //统计每个字符出现的个数
}
for(auto num:num_of_letter)
{
if(num.second%2==0) //如果这个字母是偶数个，肯定全部能放到回文串中
{
res_ou+=num.second;
}
else //最后我们加上最大的奇数个数，放在最中间就可以了。
{
ji++; //还要统计下是否真的有奇数，最后决定是否要加1和加奇数
res_ji+=num.second; //把奇数个的字母个数也加起来,最后减去个数就可以。
}
}
if(ji==0)
return res_ou;
else
return res_ou+res_ji-ji+1;
// write your code here
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.11.29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读