这篇文章将为大家详细讲解有关leetcode如何解决全排列问题,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
全排列问题,子集问题,组合和问题都是经典的回溯问题。
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解题思路:
1,可以递归解
2,对于长度为n的全排列,对于任意一个元素,与长度为n-l的全排列拼接而成
3,注意golang slice append的坑
代码:
func permute(nums []int) [][]int {
var a [][]int
if len(nums)==0{
return a
}
if len(nums)==1{
return append(a,nums)
}
for i:=0;i<len(nums);i++{
aa:=permute(rest(nums,i))
for j:=0;j<len(aa);j++{
a=append(a,append([]int{nums[i]},aa[j]...))
}
}
return a
}
func rest(nums []int,i int)[]int{
if i==0{
return nums[1:]
}
if i==len(nums)-1{
return nums[:len(nums)-1]
}
return append(nums[0:i:i],nums[i+1:]...)
}
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解题思路类似,只是求并集的时候,对比如果有就不并入
func permuteUnique(nums []int) [][]int {
var a [][]int
if len(nums) == 0 {
return a
}
if len(nums) == 1 {
return merge(a, nums)
}
for i := 0; i < len(nums); i++ {
aa := permuteUnique(rest(nums, i))
for j := 0; j < len(aa); j++ {
b := append([]int{nums[i]}, aa[j]...)
a = merge(a, b)
}
}
return a
}
func merge(a [][]int, b []int) [][]int {
l := len(a)
if l == 0 {
a = append(a, b)
} else {
m := false
for k := 0; k < l; k++ {
if match(b, a[k]) {
m = true
}
}
if !m {
a = append(a, b)
}
}
return a
}
func match(a, b []int) bool {
if len(a) == 0 {
return false
}
for i := 0; i < len(a); i++ {
if a[i] != b[i] {
return false
}
}
return true
}
func rest(nums []int, i int) []int {
if i == 0 {
return nums[1:]
}
if i == len(nums)-1 {
return nums[:len(nums)-1]
}
return append(nums[0:i:i], nums[i+1:]...)
}
关于“leetcode如何解决全排列问题”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。