前言
本系列文章为《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))
评论