今日题目共八道

向大家推荐一下我们的社区：万人千题
同时向大家推荐一下我们社区几位大佬的主页
英雄哥
磊哥
解题者大佬

第一题：回文排列.

思路：只有当字符个数奇数个的情况最多有一个时，才会形成回文字符串

class Solution {public:    bool canPermutePalindrome(string s) {        int res = 0;        unordered_map<char, int> map;        for(auto &c : s) {            map[c]++;        }        for(auto &c : map) {            if(c.second&1) res++;        }        return res <= 1;    }};

第二题：有效的回文.

思路：在左指针比右指针小的前提下，比较左右指针所指的值是否相等，同时在比较的时候使用isalnum()和tolower()函数。为了不让字符串越界，特别在循环里面再次添加了left

isalnum()函数：判断一个字符是否是字母或者十进制数字，若为字母和数字则返回真，否则返回否

tolower()函数：把字符转换成小写字母，非字母字符不做出处理。

方法一：双指针

class Solution {public:    bool isPalindrome(string s) {        //双指针        int left = 0, right = s.size()-1;        while(left < right) {            while(left < right && !isalnum(s[left])) {                ++left;            }            while(left < right && !isalnum(s[right])) {                --right;            }            if(tolower(s[left]) != tolower(s[right])) {                return false;            }            ++left;            --right;        }        return true;    }};

方法二：使用库函数
思路：新建一个字符串与字符串一相等，使用reverse函数反转字符，与之比较

class Solution {public:    bool isPalindrome(string s) {        string str1;        for(char &i : s) {            if(isalnum(i)) {                str1 += tolower(i);            }        }        string str2=str1;        reverse(str1.begin(), str1.end());        return str1 == str2;    }};

第三题：验证回文串.与第二题相同，我就不赘述了

第四题：最长回文串.

思路：使用上词学到的哈希映射来解决问题，然后利用
if判断条件(map[c - ‘A’] & 1) 是否为 0
来判断该字母个数达到偶数，若为偶数，则res+2

class Solution {public:    int longestPalindrome(string s) {        int res = 0;        unordered_map<char, int>map;        for(char &c : s) {            map[c - "A"]++;            if((map[c - "A"] & 1) == 0) {                res += 2;            }        }        return res == s.size() ? res : res+1;    }};

第五题：最多删除一个字符得到回文.

思路：左右双指针，比较左右指针所指的值，直到左右指针交叉重合

class Solution {public:    bool validPalindrome(string s) {        int left = 0, right = s.size()-1;        while(left<right && s[left] == s[right]) {            ++left;            --right;        }        return Palindrom(s, left+1, right) || Palindrom(s, left, right-1);    }    bool Palindrom(const string& s, int left, int right) {        while(left < right && s[left] == s[right]) {            ++left;            --right;        }        return left >= right;    }};

第六题：验证回文字符串Ⅱ.

与第五题相同

第七题：删除回文子序列.

思路：主要是题目有点绕，删除的是回文子序列，不是子字符串
所以一共有三种情况：
空字符返回0，回文返回1，否则一次全部删a，一次全部删b，返回2

class Solution {public:    int removePalindromeSub(string s) {        if(s.size() == 0) return 0;        for(int left=0, right=s.size()-1; left<right; left++, right--) {            if(s[left] != s[right]) {                return 2;            }        }        return 1;    }};

第八题：最短回文串.

思路：就是将字符串正序和逆序转换为base进制的数，然后比较两个数取模后是否相等，如果相等，表示两个字符串相等。
KMP我一时半会是搞不定了，但如果是哈希的话，还是可以接受这种思路

class Solution {public:    string shortestPalindrome(string s) {        int n = s.size();        int base = 131, mod = 1000000007;        int left = 0, right = 0, mul = 1;        int best = -1;        for (int i = 0; i < n; ++i) {            left = ((long long)left * base + s[i]) % mod;            right = (right + (long long)mul * s[i]) % mod;            if (left == right) {                best = i;            }            mul = (long long)mul * base % mod;        }        string add = (best == n - 1 ? "" : s.substr(best + 1, n));        reverse(add.begin(), add.end());        return add + s;    }};