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

【字典序第k小】

时间:2024-09-05 12:02:43浏览次数:7  
标签:cur int 个数 num 节点 字典

440. 字典序的第K小数字

在0~9的字典树(十叉树)上,首先计算以 cur 为前缀的小于等于n的节点个数有多少,即通过以 cur 为根找子树中小于等于 n 的节点个数

如果子树个数小于k,那么就在同一层向右平移1,
否则就跳到cur的一下层第一个子节点

点击查看代码
class Solution {
    public int findKthNumber(int n, int k) {
        int cur = 1;
        -- k;
        while(k > 0) {
            int num = find(cur, n);
            if(num <= k) {
                k -= num;
                ++ cur;
            } else {
                cur *= 10;
                -- k;
            }
        }
        return cur;
    }

    public int find(int cur, int n) {
        int num = 0;
        long l = cur;
        long r = cur;
        while(l <= n) {
            num += Math.min(r, n) - l + 1;
            l = l * 10;
            r = r * 10 + 9;
        }
        return num;
    }
}

标签:cur,int,个数,num,节点,字典
From: https://www.cnblogs.com/Eve7Xu/p/18398156

相关文章

  • 字典元素的访问示例
    '''可以对字典对象进行迭代或者遍历,默认是遍历字典的键,如果需要遍历字典的元素必须使用字典对象的items()方法明确说明,如果需要遍历字典的值则必须使用字典对象的values()方法明确说明'''Dict={'age':18,'name':'Zheng','sex':'male'}#遍历输出字典的键foriteminDict:  ......
  • 字典get()方法使用案例
    '''字典对象提供了一个get()方法用来返回指定键对应的值,并且允许指定键不存在时返回特定的值'''Dict={'age':18,'sorce':'Zheng','sex':'male'}#输出键对应的值print(Dict['age'])print(Dict['sorce'])print(D......
  • 字典操作示例
    字典用{}标识,它是一个无序的“键(key):值(value)”对集合。在同一个字典中,键必须是唯一的,但值不必唯一,值可以是任何数据类型,但键必须是不可变的,如字符串,数字,元组首先需要先定义一个字典dict1={'Alice':'123','Beth':'456','Cecil':'abc'}输出123print(dict1['Alice'])增......
  • VBA字典与数组第十八讲:VBA中静态数组的定义及创建
    《VBA数组与字典方案》教程(10144533)是我推出的第三套教程,目前已经是第二版修订了。这套教程定位于中级,字典是VBA的精华,我要求学员必学。7.1.3.9教程和手册掌握后,可以解决大多数工作中遇到的实际问题。这套字典教程共两册,一共八十四讲,今后一段时间会给大家陆续推出修订后的教程内容......
  • PowerDesigner生成数据字典文档
    PowerDesigner生成数据字典文档目录1.设置报告2.导出报告3.查看报告设置报告删除多余的选项,只保留【LIstofTableColumns-表%PARENT%的栏的清单】选项。只显示Name、Code、DataType、Length、IsKey等列导出报告查看报告......
  • Python字典操作实现文章敏感词检索
    Python字典操作实现文章敏感词检索在许多应用程序中,特别是在社交平台、评论系统和内容管理系统中,需要对用户提交的文本进行敏感词检索,以确保内容的合规性。Python字典因其高效的键值对存储特性,非常适合用于实现敏感词的检索功能。本文将介绍如何使用Python字典来实现简单的敏感词......
  • 探秘Python字典:解锁数据管理的艺术
    引言字典(Dictionary)是一种可变容器模型,它可以存储任意类型对象。Python字典使用键-值对(key-valuepair)存储数据,其中键必须是不可变的数据类型如数字、字符串等,而值可以是任何数据类型。这种数据组织方式使得字典非常适合用于快速查找、更新信息,特别是在处理大量数据时,字典的高效性......
  • 分享丨【题单】贪心算法(基本贪心策略/反悔/区间/字典序/数学/思维/构造)
    作者:灵茶山艾府链接:https://leetcode.cn/circle/discuss/g6KTKL/一、贪心策略有两种基本贪心策略:从最小/最大开始贪心,优先考虑最小/最大的数,从小到大/从大到小贪心。在此基础上,衍生出了反悔贪心。从最左/最右开始贪心,思考第一个数/最后一个数的贪心策略,把n个数的原问题转......
  • 字典查找对应输入的字符
    一、将文件放入到数据库#include<stdio.h>#include<sqlite3.h>#include<sys/types.h>#include<sys/stat.h>#include<fcntl.h>#include<string.h>#include<unistd.h>intmain(intagrc,char*agrv[]){FILE*fp;fp=fo......
  • Python创建字典与fromkeys的坑
    字典很重要字典dict是Python中很重要的一个数据类型,通过键值映射,能够很好的定位查找.Django,Flask这些Web框架在做前后端分离时,就是用字典传数据的,因为它和列表list配合起来,能够很好的与json格式的数据相互转化.用Flask+Echarts做数据可视化大屏,传的变量都是......