16 最长回文串

题目

思路

计算得到每个字符出现的次数，如果是偶数个数就直接加上这个个数，如果是奇数个数，保留这个奇数个数-1的数，最后可以留一个奇数在最中间。—>其实最终在做的事情就可以转换为：原字符串长度-出现奇数次数的字符数+1 （这个加1是因为可以有一个奇数在最中间

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> vec(128, 0);
        int odd = 0;
        int n = s.size();
        for(auto ch : s)
        {
            if('A'<= ch <='Z')//大写0-25 小写26开始
            {
                vec[ch - 65]++;
            }
            else //if('a' <= ch <='z')
            {
                vec[26 + ch -97]++;
            }
        }
        for(int i = 0; i < vec.size(); i++)
        {
            if(vec[i]%2 != 0)
            {
                odd++;
            }
        }
        if(odd)
        {
            return n-odd+1;
        }
        else{
            return n;
        }
    }
};
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
29
30
31
32
33

未通过的例子 字符数组不能是52

class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> vec(52, 0);//改成128就ok了  为什么呢？
        int even = 0;
        int odd = 0;
        bool flag=false;
        for(auto ch : s)
        {
            if('A'<= ch <='Z')//大写0-25 小写26开始
            {
                vec[ch - 65]++;
            }
            else //if('a' <= ch <='z')
            {
                vec[26 + ch -97]++;
            }
        }
        for(int i = 0; i < vec.size(); i++)
        {
            if(vec[i]%2 == 0)//是偶数
            {
                even += vec[i];
            }
            else //if(vec[i]%2 != 0)
            {
                 //取出其中偶数的个数 比如5个c 取其中4个为所用 9个d取其中8个为所用
                 odd += vec[i]-1;//1
                 flag=true;
            }
        }
        if(flag)
        {
            odd += 1;//被落下的奇数的其中一个可以放在最中间
        }
        cout<<odd<<" "<<even;
        return even + odd;
    }
};
*/
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
29
30
31
32
33
34
35
36
37
38
39
40