go语言刷题:60. 排列序列
程序员文章站
2024-03-23 10:32:04
...
申明:本文只用做自己的学习记录
题目
给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k,返回第 k 个排列。
示例 1:
输入:n = 3, k = 3
输出:“213”
示例 2:
输入:n = 4, k = 9
输出:“2314”
示例 3:
输入:n = 3, k = 1
输出:“123”
代码
//分析:这是典型的回溯算法,回溯算法总共分为以下几步:
//1.建立循环结束条件
//2.遍历操作
//3.根据题目条件减枝,减少不必要的循环
//4.正文操作,回溯函数
//6.复位,也就是回溯,将变量恢复到正文操作前的状态
func getPermutation(n int, k int) string {
result := 0
current := 0
isvisited := make([]bool, n)
count := 0
BackTrack(n, k, isvisited, &count, current, &result)
return strconv.Itoa(result)
}
func BackTrack(n int, k int, isvisited []bool, count *int, current int, result *int) {
//1.循环结束条件
//当数字的长度等于n时,表示这是一个有效数字,有效数字个数+1
if LengthOf(current) == n {
(*count)++
//当遍历到第k个有效数字时符合题意条件,返回第k个有效数字
if (*count) == k {
(*result) = current
return
}
}
//2.开始遍历
for i := 1; i <= n; i++ {
//3.减枝,当当前数字被使用过时则跳过该数字
if isvisited[i-1] {
continue
}
//4.正文操作
//进行数字拼凑,整合数字
current = current*10 + i
//记录该数字的使用情况,true为使用过
isvisited[i-1] = true
//5.进行下一阶段的搜索,回溯函数
BackTrack(n, k, isvisited, count, current, result)
//6.回溯到上一个位置的状态
//当前数字删除最后一位数
current = current / 10
//重置当前数字的使用情况,false表示没有使用
isvisited[i-1] = false
}
}
//判断数字的长度,排除n=0的可能
func LengthOf(current int) (result int) {
temp := 0
for current >= 1 {
current = current / 10
temp++
}
return temp
}
上一篇: go语言刷题:46. 全排列