今日題目共八道

向大家推薦一下我們的社區：萬人千題
同時向大家推薦一下我們社區幾位大佬的主頁
英雄哥
磊哥
解題者大佬

第一題：回文排列.

思路：只有當字符個數奇數個的情況最多有一個時，才會形成回文字符串

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;    }};