面试金典0104 回文排列

题目：回文排列

解题方法：

1. 位运算：统计某个字符出现的次数是奇数还是偶数，可以用异或^来统计
2. 哈希计数
3. 桶计数（较简单，未给出代码）

• 原理都是统计字符串中每个字符出现的频数，如果奇数的个数小于等于1，则可以产生回文排列，否则不行

• 三种方法时间复杂度相同，但所用到的空间不同，1 < 2 < 3

方法一：位运算

• 代码只存了小写和大写字母，其实可以用两个long int型的来存128个字符，使得代码鲁棒性更强
• 用异或操作来存储字符出现的奇偶，如果奇数则为1，偶数为0
• 最后判断s中字符出现的奇偶次数，奇数个数小于等于1时返回true
  • 奇数个数为1，此时mark为\(2^x\)，也就是\(00..010..0\)这种形式，此时可以用\(mark-1\)，变为\(00...001...1\)的形式，此时两者用与操作，则为0
  • 奇数个数为0，此时mark为0，mark-1为\(111...1\)，此时与操作也是0

class Solution {
public:
    bool canPermutePalindrome(string s) {
        long int mark = 0;// 用bit来存储
        for(int i=0; i<s.size(); ++i)
        {
            int tmp = int(s[i] - 'a');
            if(tmp>=0 && tmp<=25)
            {
                long int num = long(1) << tmp;
                mark = mark ^ num; // 异或
            }
            int tmp2 = int(s[i] - 'A');
            if(tmp2>=0 && tmp2<=25)
            {
                long int num = long(1) << (tmp2 + 26);
                mark = mark ^ num;
            }
        }
        // s中最多只能有一个字母出现的频数是奇数
        /*
        if(mark == 0) return true;
        for(int i=0; i<64; ++i)
        {
            long int num = long(1) << i;
            if(num == mark) return true;
        }
        return false;
        */
        // 以上注释地方可以用这个替换
        return ((mark & (mark-1)) == 0);
    }
};

方法二：哈希

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> map;
        int count_odd = 0;
        for(int i=0; i<s.size(); ++i)
        {
            map[s[i]] += 1;
        }
        for(unordered_map<char, int>::iterator it = map.begin(); it != map.end(); ++it)
        {
            if(it->second % 2 != 0)
            {
                count_odd++;
            }
        }
        if(count_odd > 1)
        {
            return false;
        }
        return true;
    }
};