LeetCode46:全排列(八皇后)

2020年3月7日 评论 308 views 1785字阅读5分57秒

前言

本系列文章为《leetcode》刷题笔记。

题目位置:力扣中国

项目位置:我的Github项目

题目

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路

方法一、回溯
这种题目明显是用回溯来做了,因为他的输出结果给的就是回溯的。

回溯的思路就是
1. 先找一个路径出来,记录下来这个路径。
2. 擦掉最后一次的查找记录,返回上一层
3. 重新找倒数第二层,找到以后继续找下一层,直到找到一个新的路径
4. 限定条件:每一层查找出来的数字都必须和其他不同

所以根据我的思路描述和上图,我的算法计划:
1. 使用递归,这样每找一层,找下一层的操作就是调用自己
2. 每层递归都用一个循环遍历原数组所有的元素,每遍历一个就判断一次是否和前面的数重复:所以我们需要一个for循环,需要一个判断用的函数checkIndex
3. 递归就要有终止条件:这里的终止条件有三个

第一个:找到了完整的路径,为了防止进入下一次递归,立刻跳出当前也就是最后一层递归(也就是当前找的元素没有和前面的重合,而且当然找到的是最后一个元素)

    if checkIndex(indexs, current) {
            continue
        }

        if current == len-1 {
            //保存找到的路径
        }

第二个:上一层递归返回,而当前递归的循环已经遍历完了最后一个元素。比如下图的第二层循环已经遍历完了3,所以只能擦掉当前,继续返回了!

代码是:

    for i := 0; i < len; i++ {//此时i==len-1,
        //...
        run(indexs, nums, newCurrent, len)
        indexs[current] = -1

    }

ps: 有没有可能最后一层递归,所有元素都找遍了,都没有找到呢?不可能!因为前面的所有元素都不重复,递归层数和数组长度相等,所以完全不可能找不到。

时间复杂度 O(N^(N+1)): 因为一层循环是n,有n-1层循环嵌套
空间复杂度 O(h(n)):回溯的空间是动态生成的,如果不要求保留答案,只用输出的话那空间使用h(n),也就是深度。但是这里要求保存结果,就多申请了结果 * 深度 个空间。这是个概率论的题目,结果应该有h(n)!个(阶乘)。

方法二、Python3库函数

Python3 itertools 文档

直接调用库函数itertools.permutations即可

代码

Go

var ResRow [][]int

func checkIndex(indexs []int, curret int) bool {
    for i := 0; i < curret; i++ {
        if indexs[i] == indexs[curret] {
            return true
        }
    }
    return false
}

func run(indexs []int, nums []int, current int, len int) {
    for i := 0; i < len; i++ {
        indexs[current] = nums[i]
        if checkIndex(indexs, current) {
            continue
        }

        if current == len-1 {
            res_col := make([]int, len)
            for i := 0; i < len; i++ {
                res_col[i] = indexs[i]
            }
            ResRow = append(ResRow,res_col)
            indexs[current] = -1
            return
        }
        newCurrent := current + 1
        run(indexs, nums, newCurrent, len)
        indexs[current] = -1

    }
}

func permute(nums []int) [][]int {
    indexs := make([]int, len(nums))

    //init num_indexs
    for i := 0; i < len(nums); i++ {
        indexs[i] = -1
    }

    //run
    run(indexs, nums, 0, len(nums))
    var tmpRow = ResRow
    ResRow = [][]int{}
    return tmpRow
}

PS: 其实这一题的名字叫八皇后。

Python3

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))
weinxin
公众号
在号内与我交流,回复【资源】获取技术大礼包
小熊