Code & Func

第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
  [1,2,3],
3
  [1,3,2],
4
  [2,1,3],
5
  [2,3,1],
6
  [3,1,2],
7
  [3,2,1]
8
]

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

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

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

dicuss中的做法：

1
vector<vector<int> > permute(vector<int> &num) {
2
    vector<vector<int> > result;
3

4
    permuteRecursive(num, 0, result);
5
    return result;
6
}
7

8
// permute num[begin..end]
9
// invariant: num[0..begin-1] have been fixed/permuted
10
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)  {
11
    if (begin >= num.size()) {
12
        // one permutation instance
13
        result.push_back(num);
14
        return;
15
    }
8 collapsed lines
16

17
    for (int i = begin; i < num.size(); i++) {
18
        swap(num[begin], num[i]);
19
        permuteRecursive(num, begin + 1, result);
20
        // reset
21
        swap(num[begin], num[i]);
22
    }
23
}

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