前言(廢話)

31題是求下一個排列。
寫這題大概花了我一兩的小時的時間吧。
寫完後就去玩樂了，結果呢，回來的時候突然看到46、47。
#46 Permutations
#47 Permutations II
一好奇點進去，46是給妳一個不重複的數列，請輸出全部的排列。
愣了一下，抱著47不會是允許重複吧？結果點開，還真是OAO
那......就作弊吧XD全部都用31題的function來解決囉～

36 NEXT PERMUTATION

題目描述(前言已帶過)

[1,2,3]→[1,3,2]
[1,5,3]→[3,1,5]
[9,8,7]→[7,8,9]
應該不用細說也看得懂。

思維

經過觀察，發現顯示出的下個數列將會是此數列可排成的下一個數字。
舉例來說
123 → 132 → 213 → 231 → 312 → 321 → 123
除卻最後一個，我輸入的數列，他的output就會是下一個數字。

程式碼

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for(int i=nums.size()-1;i>0;i--)
        {
            if(nums[i-1]<nums[i])
            {
                int anchor=nums[i];
                int j=i,e=i;
                while(j<nums.size())
                {
                    if(anchor>nums[j]&&nums[j]>nums[i-1])
                    {anchor=nums[j];e=j;}
                    j++;
                }
                nums.erase(nums.begin()+e);
                nums.insert(nums.begin()+i-1,anchor);
                sort(nums.begin()+i,nums.end());
                return;
            }
        }
        sort(nums.begin(),nums.end());
    }
};

46 Permutations

題目描述

給你一個所有元素都不相同的數列，請輸出所有的排列。

思維

都寫過31題了，還在等什麼？

程式碼

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> end=nums;
        do{
            nums=nextPermutation(nums);
            ans.push_back(nums);
        }while(end!=nums);
        sort(ans.begin(),ans.end());
        return ans;
    }
    vector<int> nextPermutation(vector<int> nums) {
        for(int i=nums.size()-1;i>0;i--)
        {
            if(nums[i-1]<nums[i])
            {
                int anchor=nums[i];
                int j=i,e=i;
                while(j<nums.size())
                {
                    if(anchor>nums[j]&&nums[j]>nums[i-1])
                    {anchor=nums[j];e=j;}
                    j++;
                }
                nums.erase(nums.begin()+e);
                nums.insert(nums.begin()+i-1,anchor);
                sort(nums.begin()+i,nums.end());
                return nums;
            }
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

47 Permutations II

題目描述

給你一個數列，請輸出所有的排列。

思維

我們31提早就也一樣解決數字重複的問題了，所以答案跟46一模模一樣樣。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> end=nums;
        do{
            nums=nextPermutation(nums);
            ans.push_back(nums);
        }while(end!=nums);
        sort(ans.begin(),ans.end());
        return ans;
    }
    vector<int> nextPermutation(vector<int> nums) {
        for(int i=nums.size()-1;i>0;i--)
        {
            if(nums[i-1]<nums[i])
            {
                int anchor=nums[i];
                int j=i,e=i;
                while(j<nums.size())
                {
                    if(anchor>nums[j]&&nums[j]>nums[i-1])
                    {anchor=nums[j];e=j;}
                    j++;
                }
                nums.erase(nums.begin()+e);
                nums.insert(nums.begin()+i-1,anchor);
                sort(nums.begin()+i,nums.end());
                return nums;
            }
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

心路歷程

簡簡單單、輕輕鬆鬆的一次解決3題，一個字 ── 爽！