Leetcode46. Permutations | 模拟 | 递归 | 记忆化搜索

1.题意

求给定数组的全排列。细节：
1.数组不含重复元素
2.数组长度介于[1, 6]之间。因为最长是6所以其实C++可以开一个三维数组做，但考虑到更普遍的情况，还是用了向量。
3.输出全排列时没有顺序要求

2.算法

模拟

3.分析

【模拟】
n个数的全排列，其实是在n-1个数字的全排列基础上加上第n个数。第n个数一共有n个位置可以插入，每种不同的插入方式就是对应的全排列。
所以从第1个数字开始（它本身），依次保留i个数字情况下的全排列，对第i+1个数字，它的全排列就是i个数字全排列的每种情况依次在每个位置插入第i+1个数字。
【记忆化搜索/递归】
两种方法的本质其实是一样的，递归也是将问题转化为n-1个数字的子问题+第n个数字的插入。
本问题的核心其实是回溯的技巧，通过每轮循环的回溯，节省了储存空间也提升了效率。假设不使用回溯的技巧，按照我们的思路实际去写会多出许多代码量。回溯在本题中具体来说就是在第n个数字插入到子问题的解决方案时，“依次插入“具体是如何实现的。模拟里是每次加入之后，就在这一轮循环的最后把对应位置删掉，如此重复。而递归里则是通过每次dfs之后再换回来结束（其实这个结构是一致的，好比在一些迷宫寻路问题里，在每次写完下一轮的dfs之后把标记改掉）。

4.代码

【模拟】
其实我觉得没必要叫它DP，感觉算成模拟更合适一些。
这里Java的简洁性真的非常优越……C++需要三维vector，操作起来非常麻烦（但其实我们也可以开个666的数组应付，不过那样只针对这一道题就没意思了）

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        
        for(int i:nums){
            List<Integer> tmp;
            List<List<Integer>> ans = new ArrayList<>();
            for(List<Integer> j:res){
                for(int k=0;k<j.size()+1;k++){
                    tmp = new ArrayList<>();
                    tmp.addAll(j);
                    tmp.add(k,i);
                    ans.add(tmp);
                }
            }
            if(ans.isEmpty()){
                tmp = new ArrayList<>();
                tmp.add(i);
                res.add(tmp);
            }
            else
                res = ans;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

【记忆化搜索】
Java这里要注意List和Array的互相转化，如果只是直接用Arrays.toList()出来的是一个伪List，是固定的没办法增添元素，查了半天应该是没有什么捷径，一定要转换就是得遍历一遍。
另外Java的swap是要自己实现的，我查了查好像应该是内置了swap(数组，index a, index b）的，但不知道为什么没有用……最后还是自己定义了一个😭

class Solution {
    public List<Integer> swap(List<Integer> list, int a, int b){
        Integer[] array = new Integer[list.size()];
        for(int i = 0;i<list.size();i++){
            array[i] = list.get(i);
        }
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
        
        list = Arrays.asList(array);
        
        return list;
    }
    
    public void permutation(List<List<Integer>> ans, List<Integer> tmp, int len, int n){
        if(len == n){
            ans.add(tmp);
            return;
        }
        for(int i = len;i < n;i++){
            tmp = swap(tmp,i,len);
            permutation(ans, tmp, len+1, n);
            tmp = swap(tmp,i,len);
        }
    }
    
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> intList = new ArrayList<Integer>();
        for(int index = 0;index < nums.length;index++)
            intList.add(nums[index]);
        permutation(ans, intList, 0, nums.length);
        
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    void permutation(vector<vector<int>>& ans, vector<int>& tmp, int len, int n){
        if(len == n){
            ans.push_back(tmp);
            return;
        }
        for(int i = len;i < n;i++){
            swap(tmp[i], tmp[len]);
            permutation(ans, tmp, len+1, n);
            swap(tmp[i], tmp[len]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        permutation(ans, nums, 0, nums.size());
        return ans;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5.复杂度

时间复杂度：O(nn!) 子问题个数子问题的时间复杂度
空间复杂度：O(n!)