今日題目共八道

向大家推薦一下我們的社區(qū)：萬(wàn)人千題
同時(shí)向大家推薦一下我們社區(qū)幾位大佬的主頁(yè)
英雄哥
磊哥
解題者大佬

第一題：回文排列.

思路：只有當(dāng)字符個(gè)數(shù)奇數(shù)個(gè)的情況最多有一個(gè)時(shí)，才會(huì)形成回文字符串

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

第二題：有效的回文.

思路：在左指針比右指針小的前提下，比較左右指針?biāo)傅闹凳欠裣嗟?，同時(shí)在比較的時(shí)候使用isalnum()和tolower()函數(shù)。為了不讓字符串越界，特別在循環(huán)里面再次添加了left

isalnum()函數(shù)：判斷一個(gè)字符是否是字母或者十進(jìn)制數(shù)字，若為字母和數(shù)字則返回真，否則返回否

tolower()函數(shù)：把字符轉(zhuǎn)換成小寫(xiě)字母，非字母字符不做出處理。

方法一：雙指針

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

方法二：使用庫(kù)函數(shù)
思路：新建一個(gè)字符串與字符串一相等，使用reverse函數(shù)反轉(zhuǎn)字符，與之比較

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

第三題：驗(yàn)證回文串.與第二題相同，我就不贅述了

第四題：最長(zhǎng)回文串.

思路：使用上詞學(xué)到的哈希映射來(lái)解決問(wèn)題，然后利用
if判斷條件(map[c - ‘A’] & 1) 是否為 0
來(lái)判斷該字母?jìng)€(gè)數(shù)達(dá)到偶數(shù)，若為偶數(shù)，則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;    }};

第五題：最多刪除一個(gè)字符得到回文.

思路：左右雙指針，比較左右指針?biāo)傅闹担钡阶笥抑羔樈徊嬷睾?/p>

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

第六題：驗(yàn)證回文字符串Ⅱ.

與第五題相同

第七題：刪除回文子序列.

思路：主要是題目有點(diǎn)繞，刪除的是回文子序列，不是子字符串
所以一共有三種情況：
空字符返回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;    }};

第八題：最短回文串.

思路：就是將字符串正序和逆序轉(zhuǎn)換為base進(jìn)制的數(shù)，然后比較兩個(gè)數(shù)取模后是否相等，如果相等，表示兩個(gè)字符串相等。
KMP我一時(shí)半會(huì)是搞不定了，但如果是哈希的話，還是可以接受這種思路

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