46. 全排列

[crawler-django]

题目描述:

原题地址: https://leetcode-cn.com/problems/permutations/

这题的思路跟高中做数学的思路一样, n! , 也是一样按n!列出来. 但是按以前的想法写成代码是不好写的, 这时如果用个树当例子就会好写很多.

把第一次的选择当做树的根节点. 就像[1, 2, 3] 我们要选择1 / 2 / 3�当根节点, 跟 1, 2, 3我们要选一个做第一个数一样, 然后选择第二个 第三个, 同理选了根节点后, 继续选择不同的子节点, 然后最后总结所有的结果.

代码如下:

var permute = function(nums) {

    let arr = []

    let len = nums.length

    let tempItemArr = []

    let depth = 0

    const generalAll = (nums) => {

        if (!nums.length) {
            depth--
            arr.push(tempItemArr.slice())
            return
        }

        for (let i = 0; i < nums.length; i += 1) {

            let tempNums = nums.slice() 

            if (nums.length === len) {
                depth = 0
                tempItemArr = []
            }

            let item = tempNums.splice(i, 1)[0]

            tempItemArr[depth++] = item

            generalAll(tempNums)
        }

        depth--
    }

    generalAll(nums)

    return arr
};

运行结果:

---

还有一种思路是交换法, 但是其实也是暴力解, 只是不同思路的暴力解. 但是交换法不会额外的创建空间, 时间复杂度是一样的.

交换法代码:

var permute = function(nums) {

    const swap = (a, b, numsArr) => {
        let temp = numsArr[a]
        numsArr[a] = numsArr[b]
        numsArr[b] = temp
    }
    let arr = []
    let count = 0

    const generalAll = (count) => {

        if (count === nums.length) {
            arr.push(nums.slice())
        } else {
            for (let i = count; i < nums.length; i += 1) {
                if (i !== count) {
                    swap(i, count, nums)
                    generalAll(count + 1)
                    swap(count, i, nums)
                } else {
                    generalAll(count + 1)
                }
                
            }
        }
    
    }

    generalAll(0)

    return arr
};

运行结果:

执行用时有时候跟网速有点关系, 不必太在意. 但是空间基本是准的.