全排列

Posted on In
这种经典的算法题，最开始可能纠结于代码的执行顺序，这种情况，可以在运行环境中打断点，一步一步执行，看看顺序。

全排列1

  • 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
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
var permute = function(nums) {
    if(nums.length == 0 ){
        return nums;
    }
    
    const res = [], path = [], used = [];

    dfs(res, nums, 0, path, nums.length, used);

    return res;
};

function dfs(res, nums, depth, path, len, used){
    if(depth == len){
        res.push([...path]);
        return;
    }  

    for(let i = 0; i < len;i++){
        if(!used[i]){
            path.push(nums[i]);
            used[i] = true;

            dfs(res, nums, depth + 1 , path, len, used)
			
            path.pop();
            used[i] = false;
        }
    }
    
}

这种经典的算法题，最开始可能纠结于代码的执行顺序（可以在运行环境中打断点，一步一步执行，自己看看顺序），在我看来最重要的是算法结构，比如这里解决问题的思路就是通过for循环里加递归的结构，使用这个结构的特点是，执行递归后面的代码之后，会继续参加for循环，就是在这里实现了排列。

全排列2

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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
var permuteUnique = function(nums) {
    if(nums.length === 0){
        return nums;
    }

    const [res,path,used] = [[],[],[]];

    nums.sort((val1, val2) => val1 -val2);

    dfs(res, path, used, nums, nums.length, 0);
    return res; 
};

function dfs(res, path, used, nums, len, depth){
    if(depth === len){
        res.push([...path]);
        return;
    }

    for(let i = 0; i < len;i++){
        //剪枝条件
        if(i > 0 && !used[i-1] && nums[i] === nums[i - 1]){
            continue;
        }

        if(!used[i]){
            path.push(nums[i])
            used[i] = true;

            dfs(res, path, used, nums, len, depth + 1);

            path.pop();
            used[i] = false;
        }
    }
}

这里多了一个剪枝条件，同时注意这里首先进行了排序处理。

参考链接：

https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/