欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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
}