LeetCode 最长回文串
在给定包含大小写的字符串中，找出这些字母构成的最长回文串，构造时注意区分大小写
这道题目不同在于可以通过构造找出最长回文串，于是可以通过找规律求得。
首先把每个字母出现的个数统计出来，放进vector中（方便处理）。
查看vector中每个字母出现的次数，如果字母出现的个数时偶数，一定可以构成回文串，则可以把这些个数直接加起来；
如果字母出现的个数是奇数，则要统计出现奇数次数的字母有多少个。经过规律发现，这些奇数次出现的字母个数如果>1，（abdcccc => 1,1,1,4 ）,则最长的回文串只能是总长度-出现奇数次的字母个数+1，加１实质时只能算一个该奇数次的字母（ccacc 或者 ccbcc 或者 ccdcc 总长度是5）；若<1（没有或只有一个），否则直接算总长度即可。
要注意区分大小写，我把A~Z分配到26以后的数组下标，之前的下标用于存放小写字母。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| int longestPalindrome(string s) {
vector<int>num;
int arr[1000] = {0};
char C;
for(char c : s){
if(c >= 'A' && c <= 'Z')
arr[c-'A'+26]++;
else if(c >= 'a' && c<= 'z')
arr[c-'a']++;
}
int odd = 0;
for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
if(arr[i] !=0){
num.push_back(arr[i]);
}
}
int len = 0;
for(int i = 0; i<num.size();i++){
len += num[i];
if(num[i] % 2 != 0){
odd++;
}
}
if(odd >= 2){
return len-odd+1;
}
return len;
}
|
