Code & Fun

第20天,第二次超级快的刷完了一道题。。。要不明天试试刷hard

今天的题目是Permutations,emmm,之前好像好几次都忘记加地址了。

Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:

1
2
3
4
5
6
7
8
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

总感觉之前遇到过类似的题目,然后思路也是很简单的,直接递归的做就好了:

这里如果不算是push_back中的拷贝数组,应该已经是拷贝数组次数最少的了,做的时候以为push_back不会拷贝,不过在dicuss中看的做法是只在push_back中进行拷贝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int> > ret;
vector<vector<int>> permute(vector<int>& nums) {
//if (nums.size() == 0 || nums.size() == 1) return {nums};
permute(nums,0);
return ret;
}
void permute(vector<int> &nums,int beg) {
if (nums.size() - beg <= 1) {
ret.push_back(nums);
return ;
}
permute(nums,beg+1);
for(int i = beg+1;i<nums.size();i++) {
vector<int> vec = nums;
swap(vec[beg],vec[i]);
permute(vec,beg+1);
}
}

dicuss中的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;

permuteRecursive(num, 0, result);
return result;
}

// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result) {
if (begin >= num.size()) {
// one permutation instance
result.push_back(num);
return;
}

for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + 1, result);
// reset
swap(num[begin], num[i]);
}
}

他的做法和我一开始的时候类似,但是我没想到可以换回来。。。


本文首发于Code & Fun