【LeetCode】马三来刷题之Permutations

最近进行了一次在线笔试，用的是codility的在线OJ，结果不是很理想，第一道题22分，第二道题100分，第三道，第四道由于没有提交的了0分（在本地IDE写的代码，因为样例没过就没提交，后来前辈说没过也应该提交的，苦逼~），太丢人了。果然1年多不刷题，手也生了，头脑也不灵光了，痛定思痛，从今天开始恢复每天切题一道。

为了和博客园的博客区别开来，我就把刷题的博客放到CSDN了，以便更好的分类和查看。

第一天恢复刷题，就先从一个简单的入手吧：https://leetcode.com/problems/permutations/     题目如下：

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

Subscribe to see which companies asked this question

很简单，就是求一个数组的全排列，用了两种方法过了这道题，分别是next_permutation（）和DFS。

先来看一下next_permutation（）解法，next_permutation（）是STL库中的一个函数，可以很方便的求出下一个排列。

vector< vector<int> > permute(vector<int>& nums) {vector< vector<int> > result;sort(nums.begin(),nums.end());do{result.push_back(nums);}while(next_permutation(nums.begin(),nums.end()));return result; }

再来看看用DFS如何解答：

void dfs(vector<int> &num, int begin, vector<vector<int> > &result) {if (begin >= num.size()) {result.push_back(num);return;}for (int i = begin; i < num.size(); i++) {swap(num[begin], num[i]);dfs(num, begin + 1, result);swap(num[begin], num[i]);} } vector<vector<int> > permute(vector<int> &num) {vector<vector<int> > result;dfs(num, 0, result);return result; } 每天一道题，保持新鲜感，就这样~

总结

以上是生活随笔为你收集整理的【LeetCode】马三来刷题之Permutations的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。