当前位置：网站首页>golang力扣leetcode 386.字典序排数

golang力扣leetcode 386.字典序排数

2022-04-21 23:07:00 【cheems~】

386.字典序排数

386.字典序排数
题解
代码

386.字典序排数

题解

字典序，简单题，直接看注释即可

代码

/* 字典序 n=13 1 10 11 12 13 2 3 4 5 6 7 8 9 */
//迭代
func lexicalOrder1(n int) []int {
    
	ans := make([]int, n)
	num := 1
	for i := range ans {
    
		ans[i] = num
		if num*10 <= n {
     //如果num*10 <= n,说明num*10是下一个字典序
			num *= 10
		} else {
     //如果num*10 > n,说明num*10不满足字典序,尝试num++,或者缩小
			for num+1 > n {
     //如果num+1>n,说明要缩小,返回上一位
				num /= 10
			}
			for num%10 == 9 {
     //如果num是 9 结尾,说明搜索到末尾,返回上一位
				num /= 10
			}
			num++ //两种情况缩小后，加一
		}
	}
	return ans
}

//递归
func lexicalOrder2(n int) []int {
    
	//因为dfs是闭包捕获了ans切片,所以不用传指针，闭包内外用的是同一个ans
	ans := make([]int, 0, n)
	var dfs func(int, int)
	dfs = func(cur int, limit int) {
    
		//如果超过限制则返回
		if cur > limit {
    
			return
		} else {
    
			//在范围内则添加,因为是dfs，那么是天然满足字典序的
			ans = append(ans, cur)
			//递归放大十倍的下一个字典序
			for i := 0; i <= 9; i++ {
    
				dfs(cur*10+i, limit)
			}
		}
	}
	//入口
	for i := 1; i <= 9; i++ {
    
		dfs(i, n)
	}
	return ans
}