首页 > 其他分享 >字典序第k小数字

字典序第k小数字

时间:2022-08-18 18:45:29浏览次数:77  
标签:10 return cur int dfs cnts 字典 数字

 

 

 

 

https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solution/pythonjavajavascriptgo-di-gui-by-himymbe-5mq5/

 

func findKthNumber(n int, k int) int {
    cur := 1
    k--
    for k > 0 {
        cnts := dfs(cur, cur,n)
        fmt.Println(cnts)
        if cnts <= k { //当前层cur,第cnts小的数比第k小还小,那么当前层的所有cnts个数都可以取,递归到下一层去找
            k -= cnts
            cur++
        } else {// 答案在当前节点的子节点中,则从当前cur层的最小子节点开始找,cur=cur*10
            k--
            cur *= 10
        }
    }
    return cur
}

func dfs (l, r,n int) int{//l,r分别是最小和最大子节点,返回值是递归开始层~当前层所有的子节点数
    //两个递归终止条件
    if l > n {
        return 0
    }
    if r > n {
        r = n
    }

    //当前层有 r - l + 1 个节点可取,递归到下一层。
    // l * 10: 从10变成100, r * 10 + 9: 从19变成199
    return r - l + 1 + dfs(l * 10, r * 10 + 9,n)
}

 

 

标签:10,return,cur,int,dfs,cnts,字典,数字
From: https://www.cnblogs.com/-citywall123/p/16599745.html

相关文章