- leetcode之回溯系列基础题目
- 1.打印从1到最大的n位数
- 1.1暴力解法
- 1.2回溯
func printNumbers(n int) []int {
var res []int
if n==0{
return res
}
max := 1
for i :=1;i<=n;i++{
max =max*10
}
max =max-1
for i := 1; i <= max; i++ {
res = append(res, i)
}
return res
}
//时间复杂度 O(10^n)
1.2回溯题目要求打印 “从 1至最大的 n 位数的列表” ，因此需考虑以下两个问题：
1.最大的 n位数（记为max）和位数 n 的关系： 例如最大的 1 位数是9 ，最大的 2 位数是 99 ，最大的 3位数是 999 。则可推出公式：
max= 10^n - 1
2.大数越界问题： 当 n 较大时，max 会超出 int32 整型的取值范围，超出取值范围的数字无法正常存储。但由于本题要求返回 int 类型数组，相当于默认所有数字都在 int32 整型取值范围内，因此不考虑大数越界问题。
因此，只需定义区间 [1, 10^n - 1],通过 forfor 循环生成结果列表 res 并返回即可。
package main
import "fmt"
var res []string
var path string
var num []string = []string{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
func dfs(x, len int) {
if x == len {
s := path
res = append(res, s)
}
var start int
if x == 0 {
start = 1
}
for i := start; i < 10; i++ {
temp := path
path = path + num[i]
dfs(x+1, len)
path = temp
}
}
func printNumbers(n int) []string {
for i := 1; i < n; i++ {
dfs(0, i)
}
return res
}
func main() {
fmt.Println(printNumbers(1))
}
面试时候是会考虑大数情况的
