当前位置 博文首页 > 数据结构和算法：LeetCode 409. 最长回文串
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
public int longestPalindrome(String s) {
int[] map = new int[256];
//统计每个字符的个数
for (char ch : s.toCharArray())
map[ch]++;
int res = 0;
int mask = -2;
for (int count : map) {
//每个字符的个数取最大偶数，然后相加
res += count & mask;
}
//如果相加的和小于字符串的长度，最后还要加1
return res < s.length() ? res + 1 : res;
}
上面可能不容易理解的是这样一行代码
res += count & mask;
因为mask是-2，count&-2的意思就是如果count是偶数，计算的结果还是count，如果count是奇数，计算的结果是count-1。直接看可能不直观，把-2转化为二进制就明白了。
11111111 11111111 11111111 11111110
除了上面的统计方式以外，我们还可以使用集合Set来统计，代码如下
public int longestPalindrome(String s) {
int res = 0;
Set<Character> set = new HashSet<>();
for (char ch : s.toCharArray()) {
//如果set中有字符ch，remove方法会
//返回true，否则返回false
if (set.remove(ch)) {
//当前字符ch，出现了2次
res += 2;
} else {
//当前字符ch，只出现1次
set.add(ch);
}
}
return res + (set.isEmpty() ? 0 : 1);
}
或者还可以这样写，但不管怎么写，原理还是不变的，换汤不换药。
public int longestPalindrome(String s) {
boolean[] map = new boolean[256];
int res = 0;
for (int i = 0; i < s.length(); i++) {
res += map[s.charAt(i)] ? 2 : 0;
map[s.charAt(i)] = !map[s.charAt(i)];
}
return res < s.length() ? res + 1 : res;
}
