LeetCode - 排列相关题目

1、获取全排列

https://leetcode.com/problems/permutations/submissions/

按字典序输出:

这里用的是vector<int>,不是引用、指针,也就是说深层次中的递归不会影响到前面层vector中的数据。

class Solution {
public:
    vector<vector<int>>ans;
    void dfs(vector<int>arr, int k, int n) {
        if (k == n) {
            ans.push_back(arr);
            return;
        }
        for (int i = k; i < n; i++) {
            swap(arr[i], arr[k]);
            dfs(arr, k + , n);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        //sort(nums.begin(), nums.end());     //如果输入顺序是非字典序,那么就一定要先排序一次。为了dfs中的 i = k ~ n 的循环,swap(arr[i],arr[k]),得到的 n-k 个序列是满足字典升序的。
        dfs(nums, , nums.size());
        return ans;
    }
};

这是算法教材书上的写法,理论上引用是会快一点的,这个vector<int>&arr也可以直接用int数组,这题数据量比较小,体现不出来。但是输出顺序非常之古怪,慎用。

class Solution {
public:
    vector<vector<int>>ans;
    void dfs(vector<int>&arr, int k, int n) {
        if (k == n) {
            ans.push_back(arr);
            return;
        }
        for (int i = k; i < n; i++) {
            swap(arr[i], arr[k]);
            dfs(arr, k + , n);
            swap(arr[i], arr[k]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, , nums.size());
        return ans;
    }
};

2、输出不重复的排列方式

https://leetcode.com/problems/permutations-ii/

深搜去重:

DFS中,如果第i个和第k个是相同的,就不往下进行搜索了,去除掉了出现重复的可能性。

LeetCode - 排列相关题目

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int> nums, int n, int k) {
        if (k == n) {
            ans.push_back(nums);
            return;
        }
        for (int i = k; i < n; ++i) {
            if (i != k && nums[i] == nums[k]) continue;
            swap(nums[k], nums[i]);
            dfs(nums, n, k + );
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, nums.size(), );
        return ans;
    }
};

STL: next_permutation

next_permutation: 对于给定的任意一种全排列,给出能求出下一个全排列的情况。默认不会有重复序列出现的。

如果仍然有下一个全排列,返回true,给出下一个全排列;

否则返回false,给出第一个全排列;

因为可能出现的重复序列,让我们无法预知结果的个数,就必须先排序,从头做到尾。

LeetCode - 排列相关题目

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>>ans;
        sort(nums.begin(), nums.end());
        do {
            ans.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return ans;
    }
};

3、按字典序得到下一个全排列

https://leetcode.com/problems/next-permutation/submissions/

STL: next_permutation

这个题目,好像就是为next_permutation量身定做的一样。但其实效果比较一般。

LeetCode - 排列相关题目

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
            ; i < nums.size(); i++) {
                printf("%d ",nums[i]);
            }
            printf("\n");
    }
};

正解:

上一篇:【BZOJ3551】Peaks加强版(Kruskal重构树,主席树)


下一篇:Ansible playbook基础组件介绍