Day8-字符串-最长回文串
一 唠唠
今天开始字符串的算法题
嗯，没了
二 直接上题
Q：已知一个字符串，求该字符串中的字符可以生成的最长回文字符串的长度。
例如：s = “abccccddaa”，可生成的最长回文字符串的长度为9，如“dccaaaccd”，“adccbccda”，“acdcacdca”等都是正确的。
三 冷静分析
字符串问题的解法，用哈希表思想来处理，是十分方便的解法。
那么问题来了，什么是哈希表
知识点回顾-哈希表：
哈希表（Hash table，也叫散列表），是根据关键字值key直接进行访问的数据结构，通过把关键字值映射到表中一个位置（数组下标）来直接访问，以加快查找关键字值的速度。这个函数叫做哈希（散列）函数，存放记录的数组叫做哈希表。
给定表M，存在函数f，对任意的关键字值key，代入函数后若能得到包含该关键字的表中地址，称表M为哈希表，称f为哈希函数。
怎么样，还好理解吗？读到这你的表情是不是
来，上个例题，就都明白了~
例1：统计一个字符串中，各个字符的数量
直接上代码
//
// Created by renyi on 2019-06-12.
//
#include <iostream>
#include <string>
using namespace std;
void calculateCount(string s){
int char_map[128] = {0};
for (int i = 0; i < s.length(); i++) {
char_map[s[i]]++;
}
for (int i = 0; i < 128; i++) {
if (char_map[i] > 0){
printf("[%c][%d] : %d\n", i, i, char_map[i]);
}
}
}
int main(){
string s = "abcdefgabcdaaagg";
calculateCount(s);
return 0;
}
运行结果
当然，不同的整数和字符串，经过哈希函数之后，可能映射到哈希表的同一个位置，就是下标，就会产生哈希冲突，比较经典的方法是，使用拉链法（映射到同一下标的元素，连接在同一个单链表中）解决冲突，在这就不赘述了，原理不难，大家自行学习一下即可。
好了，回到题目本身
对于字符串中的字符，既然是求回文串，那么就可以有中心字符，也可以没有。比如“aabaa”，和“aabb”都是回文串。如果是偶数个的字符，就很好处理，头部出现，尾部就必须出现，所以偶数个数的字符，都可以作为最后的回文串，所以偶数部分字符全都算进去就行。
那么奇数个数的字符呢？比如“abcccdddba”，a和b都是偶数个，直接算进去。当遍历到字符的数量为奇数时，奇数个字符是可以选为中心字符的，设置中心标志位flag，初始为0，遇见奇数个数的字符，将flag置为1，同时将该字符数量减1（因为只有偶数个数时，才能作为回文），然后算进总数就行。
所以对于该字符串，当c作为中心字符时，就需要丢掉一个d，当d作为中心字符时，就要丢掉一个c。比如“abdcccdba”，或“abcdddcba”都是最后的最长回文串。
四 完整代码及注释
//
// Created by renyi on 2019-06-12.
//
#include <iostream>
#include <string>
using namespace std;
int longestPalindrome(string s){
int char_map[128] = {0};//初始化字符哈希表
int max_length = 0;//字符串s的偶数长度字符部分
int flag = 0;//flag为是否有中心字符标志位
for (int i = 0; i < s.length(); i++) {
char_map[s[i]]++;//利用char_map数组的下标实现字符哈希，来统计字符串s中每个字符的个数
}
for (int i = 0; i < 128; i++) {
if (char_map[i] % 2 == 0){
max_length += char_map[i];//偶数个数的字符直接算进总数
} else{
max_length += char_map[i] - 1;//奇数个数的字符，减1个，使成为偶数个数
flag = 1;//同时置标志位为1
}
}
return max_length + flag;//最终返回偶数个数与标志位的和
}
int main(){
string s = "abccccdddaaaffggg";
int result = longestPalindrome(s);
printf("该字符串的最长回文串长度为:%d\n", result);
return 0;
} 运行结果
五 总结
给大家留个作业：实现这两个题的代码，和拉链法解决哈希冲突