LeetCode精选算法200题------（1）266.回文排列

? ? ? ? 最近算法可能学到了一些瓶颈，单纯听课开始有些听不进去。于是开始在LeetCode上找题目做做。写题解或许是个不错的选择。准备把题解分为两部分：思考（自己怎么做的）+学习（别人怎么做的）。

? ? ? ? 第一道题比较简单，题面如下：

????????

思考：在经历了几分钟的思考后，得出如下结论：1）满足回文字符串的条件？偶数长度的字符串不能存在任何出现次数为奇数的字符，奇数长度的字符串不能存在大于一个出现次数为奇数次的字符。2）利用一个cnt对出现次数为奇数的字符的个数进行标记，这样可以将两种情况统一。（因为偶数长度的字符串，出现次数为奇数的字符必然成对出现，因此两种情况都可以用cnt<1进行判断）如果该字符出现次数变成了偶数则cnt++，否则cnt--。

????????由于字符与其出现次数相对应，因此莫名其妙的想到了哈希表来做。c++代码如下：

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char,int> x;
        int cnt = 0;
        for(int i = 0;i<s.length();i++){
            x[s[i]]++;
            if(x[s[i]]%2==1) cnt++;
            else cnt--;
        }
        if(cnt>1) return false;
        return true; 
    }
};

????????当我高兴于时间击败了100%的人时，空间却只击败了25%的人。。。。。思考了下，肯定是哈希表出现了问题。但是我对哈希表一无所知，于是开始学习。首先，unordered_map可以用【key】访问对应的value......我草 我这都不会啊......然后，哈希表本质上是用空间换时间，因此O（1）的时间复杂度注定了O（n）的空间复杂度。。。。。。数组原来也是O（n）的空间复杂度。。。。

????????那么有没有其他方法？答案显然是有的。

学习：

????????法1：用数组进行储存（

class Solution {
public:
    bool canPermutePalindrome(string s) {
        int map[128];
        memset(map,0,sizeof(map));
        int cnt = 0;
        for(int i = 0;i<s.length();i++){
            if((++map[s[i]])%2) cnt++;
            else cnt--;
        }
        if(cnt>1) return false;
        return true;
    }
};

接近双百，但不完全是双百。好像因为某些原因，每次数组的内存都不太一样.jpg 疑惑

? ? ? ? 法2：位运算

利用一个32位数字储存每一个字符的出现次数为奇数还是偶数，用0/1来表示。这样空间可以被大大的节省。

class Solution {
public:
    bool canPermutePalindrome(string s) {
        int mod = 0,cnt = 0;
        for(auto c:s){
            mod ^= 1<<(c-'a');
        }
        return mod == 0|| (mod&(mod-1)) == 0;
    }
};