golang力扣leetcode 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
}