稀碎从零算法笔记Day35-LeetCode:字典序的第K小数字

要考虑完结《稀碎从零》系列了哈哈哈

这道题和【LC.42 接雨水】,我愿称之为【笔试界的颜良&文丑】

题型:字典树、前缀获取、数组、树的先序遍历

链接:440. 字典序的第K小数字 - 力扣(LeetCode)

来源:LeetCode

题目描述(红字为笔者添加)

这道题说实话,看不懂是其hard的很大一个原因

给定整数 n 和 k,返回  [1, n] 中字典序第 k 小的数字。

这边笔者解释下什么是字典序

440. 字典序的第K小数字 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1358635/zi-dian-xu-de-di-kxiao-shu-zi-by-leetcod-bfy0/

笔者的理解是:【字典序】重点在上,那么作为一个【排序方式】,它的法则即使”按照数字的前缀的大小、长度进行排序“(例子:1,10,100,101,102,11,2……11在101前面,因为11的前缀是”1“,而101前缀是”10“,因此101在11前面;2前缀(虽然没有前缀吧)是2,比1大,因此凡是2打头的,都排在1打头的后面)

题目样例

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

提示:

  • 1 <= k <= n <= 109

题目思路

笔者的思路来自LC宫水三叶(他的题解有点难看懂,但好在最后还是看懂了,需要有不错的code经验和思路)

LC宫水三叶题解icon-default.png?t=N7T8https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1360662/by-ac_oier-m3zl/

这道题第一个难点,就是知道他是怎么排序的
配合题目描述那里的”十叉树“ ,不难可以看出,遍历方式是”十叉树的先序遍历“,那么本题就是【返回十叉树的先序遍历的第K个数】——>通关了(bushi)

这种方法固然可行,但本题只给了k和n(右边界),创一个不熟悉的数据结构(二叉树笔者都不是很熟悉)不为明智之举。

但这个思路还是很重要的突破口,这时候可以转换一个这个遍历方式:起点是1,1遍历的方向只有【下】和【左】,且以后的节点也是如此。”1向左走“需要满足1这个树下面,没有其他的分支,连10都不能有,这就要求n是小于10的。而”1向下走“,就需要1有”孩子节点“,即以1为前缀的一众节点

那么问题,就可以转化为”看看第k个数是以谁为前缀的?“这个问题。而这个问题,难点就是”求出以各个数为前缀的数的个数“,然后看看k是否在这个范围内:①k在的话,那么k-1,i*10(k-1是跳过i这个数,i*10是i后面的第一个数,即使 i0 )。②k不在,即k>num的话,说明以 i 为前缀的所有数都不满足条件,那么i+1(相当于从1走向2),k-num。③如果k = num,说明第k个数就是最后一个以 i 为前缀的数(这种情况可以归于情况①)

然后就是”求满足条件的数的个数“:举个例子比较直观——比如说n是12345,要求以122为前缀的数的个数。那么截取12345的前3位【123】。以122为前缀的数中,1220—1229是一定<12345的,因此ans+=10。而122又是小于123的,那么说明,所有122为前缀的数都满足条件,即ans+=pow(10,2).。
以上例子是122<123的情况,假如是125>123,那么满足条件的只能是125X系列,即10个
                                              假如是 123 == 123,那么满足条件的除了123X系列,还有【12300,12345】这个区间内的

C++代码

参考三叶思路的CPP coding

class Solution {
public:
    int findKthNumber(int n, int k) {
    //题目需求:返回第K小的数字,排序是按照:前缀越小,越靠前 
    // 三叶的题解 
    int ans = 1;
    while(k > 1)
    {   
        int num = getNum(ans,n);//num是以ans为前缀的数字的个数
        if(num >= k)//第K个数在以ans为前缀的数字中
        {
            ans *=10;
            k--;
        }
        else
        {
            ans ++ ;//以ans为前缀的这一大堆都不行,得换一个前缀
            k-=num;//相当于抛弃了以ans为前缀的那一大堆,从ans+1开始数
        }
    }
    // k == 1,说明1就是答案
    return ans;
    }
    // 获取合法前缀的数字个数
    int getNum(int ans,int n)
    {
        string temp1 = to_string(ans),temp2 = to_string(n);
        int len1 = temp1.length(),len2=temp2.length(),div = len2 - len1;//div表示n比ans多了多少位
        string temp3 = temp2.substr(0,len1);
        int answer = 0;//接收前缀的个数
        int int3 = stoi(temp3);
        // 把位数短的数字的个数先获取出来
        for(int i=0;i<div;i++)
            answer += (int)pow(10,i);//n比ans长的部分
        if(ans < int3)
        {
            answer += (int)pow(10,div);//pow返回double类型
        }
        if(ans == int3)//前缀相等
            answer += n - ans * (int)pow(10,div) + 1;//以1024和10为例子,那么10为前缀的个数是[00-24],工24+1 = 25 个数字;
        return answer;
    }
};

结算页面

 

还需要努力!

你好,四月

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506181.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

el-upload上传图片图片、el-load默认图片重新上传、el-upload初始化图片、el-upload编辑时回显图片

问题 我用el-upload上传图片&#xff0c;再上一篇文章已经解决了&#xff0c;el-upload上传图片给SpringBoot后端,但是又发现了新的问题&#xff0c;果然bug是一个个的冒出来的。新的问题是el-upload编辑时回显图片的保存。 问题描述&#xff1a;回显图片需要将默认的 file-lis…

从0配置React

在本地安装和配置React项目&#xff0c;您可以使用create-react-app这个官方推荐的脚手架工具。以下是安装React的步骤&#xff0c;包括安装Node.js、使用create-react-app创建React应用&#xff0c;以及启动开发服务器。 下载安装node.js运行以下命令&#xff0c;验证Node.js…

施耐德 Unity Pro PLC 编程软件介绍

Unity Pro 软件基本介绍 Unity Pro 是施耐德中大型 PLC 的编程软件&#xff08;<–> 对应西门子 Step7&#xff09; 支持的 PLC&#xff1a;施耐德中大型 PLC 中型 PLC&#xff1a;Premium、M340&#xff08;<–> 对应西门子 S7-300、S7-1200&#xff09;大型 PL…

精读 Generating Mammography Reports from Multi-view Mammograms with BERT

精读&#xff08;非常推荐&#xff09; Generating Mammography Reports from Multi-view Mammograms with BERT&#xff08;上&#xff09; 这里的作者有个叫 Ilya 的吓坏我了 1. Abstract Writing mammography reports can be errorprone and time-consuming for radiolog…

C++项目——集群聊天服务器项目(十)点对点聊天业务

本节来实现C集群聊天服务器项目中的点对点聊天业务&#xff0c;一起来试试吧 一、点对点聊天业务 聊天服务器中一个重要的功能就是实现点对点聊天&#xff0c;客户端发送的信息包含聊天业务msgid、自身 的id和姓名、聊天对象的id号以及聊天信息&#xff0c;例如&#xff1a; …

uniapp uni.scss中使用@mixin混入,在文件引入@include 样式不生效 Error: Undefined mixin.(踩坑记录一)

问题&#xff1a; 在uni.scss文件定义mixin 2. 在vue文件引入: 3. 出现报错信息: 4. 问题思考&#xff1a; 是不是需要引入uni.scss &#xff1f; 答案不需要 uni.scss是一个特殊文件&#xff0c;在代码中无需 import 这个文件即可在scss代码中使用这里的样式变量。uni-app的…

ubuntu23.10配置RUST开发环境

系统版本: gcc版本 下载rustup安装脚本: curl --proto https --tlsv1.2 https://sh.rustup.rs -sSf | sh下载完成后会自动执行 选择默认安装选项 添加cargo安装目录到环境变量 vim ~/.bashrc 默认已添加 使用环境变量立即生效 source ~/.bashrc 执行rust开发环境,在终端输入…

Vitepress部署到GitHub Pages,工作流

效果&#xff1a; 第一步&#xff1a; 部署 VitePress 站点 | VitePress 执行 npm run docs:build&#xff0c;npm run docs:preview&#xff0c;生成dist文件 第二步&#xff1a; 手动创建.gitignore文件&#xff1a; node_modules .DS_Store dist-ssr cache .cache .temp *…

KMP哈希算法

KMP算法 KMP算法是一种字符串匹配算法&#xff0c;用于匹配模式串P在文本串S中出现的所有位置。 例如S“ababac”,P"aba",那么出现的所有位置是1 3 KMP算法将原本O&#xff08;n^2&#xff09;的字符串匹配算法优化到了O&#xff08;n&#xff09;&#xff0c;其精…

MySQL使用C语言连接

要使用C语言连接mysql&#xff0c;需要使用mysql官网提供的库&#xff0c;大家可以去MySQL官网下载。 1.引入库 1.选择Download Archivs 因为我们要连接的是C语言&#xff0c;所以选择Connector/C。 选择合适的版本下载&#xff0c;我这里 下载完之后&#xff0c;我们使用rz命…

AtCoder Beginner Contest 347 (ABCDEF题)视频讲解

A - Divisible Problem Statement You are given positive integers N N N and K K K, and a sequence of length N N N, A ( A 1 , A 2 , … , A N ) A(A_1,A_2,\ldots,A_N) A(A1​,A2​,…,AN​). Extract all elements of A A A that are multiples of K K K, divi…

鸿蒙HarmonyOS应用开发之HID DDK开发指导

场景介绍 HID DDK&#xff08;HID Driver Develop Kit&#xff09;是为开发者提供的HID设备驱动程序开发套件&#xff0c;支持开发者基于用户态&#xff0c;在应用层开发HID设备驱动。提供了一系列主机侧访问设备的接口&#xff0c;包括创建设备、向设备发送事件、销毁设备。 …

腾讯云2核4G服务器优惠价格165元一年,限制500GB月流量

腾讯云轻量2核4G5M服务器租用价格165元1年、252元15个月、三年900元&#xff0c;配置为轻量2核4G5M、5M带宽、60GB SSD盘、500GB月流量、上海/广州/北京&#xff0c;腾讯云优惠活动 yunfuwuqiba.com/go/txy 腾讯云轻量2核4G5M服务器租用价格 腾讯云&#xff1a;轻量应用服务器1…

SpringBoot + Vue3邮件验证码功能的实现

后端 SpringBootmavenmysqlIDEA 后端负责编写邮件发送的接口逻辑&#xff0c;具体流程如下: 引入相关依赖配置邮箱信息编写邮件发送服务接口OK 引入依赖 <!-- https://mvnrepository.com/artifact/org.springframework.boot/spring-boot-starter-mail --> <dependen…

基于FreeRTOS系统的STM32简易遥控器设计

项目说明 该项目是一个基于FreeRTOS系统的Stm32遥控器设计。使用该项目主要是自己学习FreeRTOS的使用&#xff0c;以及模块化编程的思想。这个项目应该长期会有更新。 项目开源 github:https://github.com/snqx-lqh/Stm32RemoteControl gitee:https://gitee.com/snqx-lqh/S…

conda 创建 python3.10.12 环境

conda 创建 python3.10.12 环境 介绍使用前置条件&#xff1a;安装 conda配置环境变量验证 Conda 安装结果创建环境&#xff1a;python激活 Anaconda 环境 验证 Python 版本。 介绍 Conda是一个开源的包管理和环境管理系统&#xff0c;由Continuum Analytics公司开发。它可以安…

【InternLM 实战营第二期笔记】InternLM1.8B浦语大模型趣味 Demo

体验环境 平台&#xff1a;InternStudio GPU&#xff1a;10% 配置基础环境 studio-conda -o internlm-base -t demo 与 studio-conda 等效的配置方案 conda create -n demo python3.10 -y conda activate demo conda install pytorch2.0.1 torchvision0.15.2 torchaudio2…

使用MySQL和PHP创建一个公告板

目录 一、创建表 二、制作首页&#xff08;创建主题以及显示列表&#xff09; 三、制作各个主题的页面&#xff08;输入回帖和显示列表&#xff09; 四、制作消息的查询界面 五、制作读取数据库信息的原始文件 六、制作数据重置页面 七、效果图 八、问题 1、目前无法处…

轻量应用服务器16核32G28M腾讯云租用优惠价格4224元15个月

腾讯云16核32G服务器租用价格4224元15个月&#xff0c;买一年送3个月&#xff0c;配置为&#xff1a;轻量16核32G28M、380GB SSD盘、6000GB月流量、28M带宽&#xff0c;腾讯云优惠活动 yunfuwuqiba.com/go/txy 活动链接打开如下图&#xff1a; 腾讯云16核32G服务器租用价格 腾讯…

三栏布局——面试/笔试题

目录 三栏布局(两端指定宽度&#xff0c;中间自适应)三栏布局(平均分布) 三栏布局(两端指定宽度&#xff0c;中间自适应) 只介绍简单的写法&#xff0c;圣杯布局之类的比较复杂&#xff0c;实际上越简单越好&#xff0c;所以复杂的就不介绍了 flex布局 <!DOCTYPE html>…