leetcode 575：Distribute Candies, 266: Palindrome Permutation, 46：Permutations

思路：给我们一堆糖，每种糖的个数不定，分给两个人，让我们求其中一个人能拿到的最大的糖的种类数。那么我们想，如果总共有n个糖，平均分给两个人，每人得到n/2块糖，那么能拿到的最大的糖的种类数也就是n／2种，不可能再多，只可能再少。那么我们要做的就是统计出总共的糖的种类数，如果糖的种类数小于n/2，说明拿不到n/2种糖，最多能拿到的种类数数就是当前糖的总种类数，明白了这点就很容易了，利用集合set的自动去重复特性来求出糖的种类数，然后跟n/2比较，取二者之中的较小值返回即可。

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        unordered_set<int> s;
        for(int candy : candies)
            s.insert(candy);
        return min(s.size(), candies.size()/2);
    }
};

这道题让我们判断一个字符串的全排列有没有是回文字符串的，那么根据题目中的提示，我们分字符串的个数是奇偶的情况来讨论，如果是偶数的话，由于回文字符串的特性，每个字母出现的次数一定是偶数次，当字符串是奇数长度时，只有一个字母出现的次数是奇数，其余均为偶数，那么利用这个特性我们可以使用 unordered_map 建立每个字母和其出现次数的映射，然后我们遍历 HashMap，统计出现次数为奇数的字母的个数，那么只有两种情况是回文数，第一种是没有出现次数为奇数的字母，再一个就是字符串长度为奇数，且只有一个出现次数为奇数的字母。

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> m;
        int cnt = 0;
        for (auto a : s) ++m[a];
        for (auto a : m) {
            if (a.second % 2 == 1) ++cnt;
        }
        return cnt == 0 || (s.size() % 2 == 1 && cnt == 1);
    }
};

解法一：使用C++中的 next_permutation() 函数，头文件是#include<algorithm>

注意：要先对数组进行从小到大排序。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());  //使用next_permutation()之前需要排序
        do{
            vector<int> out(nums);
            res.push_back(out);
        }while(next_permutation(nums.begin(), nums.end()));
        return res;
    }
};

解法二：递归+回溯（backtracking）

 

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> out;
        vector<int> visit(nums.size(), 0);    
        search(nums, visit, out, res);
        return res;
    }
    
    void search(vector<int>& nums, vector<int>& visit, vector<int>& out, vector<vector<int>>& res){
        if(out.size()== nums.size()){
            res.push_back(out);
            return;
        }
        for(int i=0; i<nums.size();i++){
            if(visit[i]==0){
                visit[i] = 1;
                out.push_back(nums[i]);
                search(nums, visit, out, res);
                out.pop_back();
                visit[i] = 0;
            }    
        }
    }
};