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

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

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

这道题让我们判断一个字符串的全排列有没有是回文字符串的,那么根据题目中的提示,我们分字符串的个数是奇偶的情况来讨论,如果是偶数的话,由于回文字符串的特性,每个字母出现的次数一定是偶数次,当字符串是奇数长度时,只有一个字母出现的次数是奇数,其余均为偶数,那么利用这个特性我们可以使用 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);
    }
};

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

解法一:使用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)

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

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

 

上一篇:poj 2402 Palindrome Numbers 数字回文 (★★☆☆☆)


下一篇:letecode [409] - Longest Palindrome