leetcode-440 字典序的第K小数字
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
注意：1 ≤ k ≤ n ≤ 10^9。
示例 :
输入:
n: 13
k: 2输出: 10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
字典排序数的实现可以参考leetcode-386
字典排序数即10叉树的形态，数值排列按照 字符串首字母的ascii码值进行排序
那么数值的字典序即为一个十叉树，比如以1为树顶的树状形式如下：
1
｜
10 11 … 19
｜\
100 101 102…109
可以看到第一层第一个数 1 和第二层之间的计算方式：
1 *10 + (1…9)
第二层 第一个数 100 和第三层之间的计算方式
10*10 + (1…9)
此时我们要在n (1…10^9)的范围内找到第k大的数。
如果一个个查找，势必效率低下。那么可以缩短查找路径，方式如下：
- 获取以1开头和以2开头数值之间的 数值个数，和k值比较
如果大于k,说明在以1开头之下的某一层中，即可增加层数继续在下一层10…11之间的数值个数，缩短k的路径
如果小于k,那么需要更换子树，更改为以 2 开头的字典树 - 计算的数值个数需要在n的范围内，同时每当层数递增时需缩减k的数值，相当于重新找到了计算起点
实现如下:
/*计算[n,n+1]范围内满足小于max的字典数的个数*/
int getCount(long n, int max) {int res = 1;long left = n *10 + 0;//n下一层的第一个数long right = n *10 + 9;//n下一层的第10个数while(left <= max) {if (max <= right) { //max在[n,n+1]之间res += (max - left + 1);} else {res += (right - left + 1);}left = left * 10 + 0;//继续递增层数right = right *10 + 9;}return res;
}int findKthNumber(int n, int k) {//return cur;long l = 1;long r = 9;while(k) {for (long i = l;i <= r; ++i) {int f = getCount(i, n);//获取[i,i+1]之间的字典数的个数，并和k进行比较//发现k大于上一个子树中字典树数的数值个数，那么更换子树iif (f < k) {k -= f;}else {//否则，继续深度搜索，缩减k的范围并进入到当前子树的下一层k --;if(k == 0) return i;l = i *10 + 0;r = i *10 + 9;break;}}}return 0;
}
相关文章：
centos 编译 mysql_Centos编译mysql
下载源码wget http://dev.mysql.com/get/Downloads/MySQL-5.6/mysql-5.6.23.tar.gztar zxvf mysql-5.6.23.tar.gz安装必要的包sudo yum install cmake gcc gcc-c ncurses-devel perl-Data-Dumper cmake ncurses-devel bison autoconf automake zlib* fiex* libxml* libmcrypt* …
java.lang.NoSuchMethodException 错误
报错： Stacktraces java.lang.NoSuchMethodException: com.gssw.action.ProAction.update() java.lang.Class.getMethod(Class.java:1607)org.apache.struts2.interceptor.validation.AnnotationValidationInterceptor.getActionMethod(AnnotationValidationInterce…
tomcat server.xml中文版
为什么80%的码农都做不了架构师？>>> Tomcat Server的结构图 该文件描述了如何启动Tomcat Server <Server> <Listener /> <GlobaNamingResources> </GlobaNamingResources <Service> <Connector /> <Engine> &l…
idea（2）快捷键
CtrlE：最近编辑文件 CtrlJ：自动代码快捷 CtrlN：查找类 CtrlU：大小写转换 CtrlF12：outline Alt1：全屏 AltF1：类定位到左侧目录 AltInsert：万能创建 AltEnter：导入包 CtrlA…
leetcode-102 二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如: 给定二叉树: [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ] 方法一（…
mysql.err日志分析_Mysql日志解析
转载:https://www.cnblogs.com/Fly-Wind/p/5674382.html修改Mysql配置Mysql配置地址为：C:\Program Files (x86)\MySQL\MySQL Server 5.5如果无法修改可以把my.ini拷贝出来，修改完后，再拷贝回去！如果配置了Mysql的日志生成路径&…
linux进程间通信-XSI IPC
一 什么是XSI IPC 有三种 IPC我们称作XSI IPC，即消息队列、信号量以及共享存储器（共享内存），它们之间有很多相似之处。二 标识符和键 每个内核中的 IPC结构（消息队列、信号量或共享内存）都用一个非负整数的…
Linux命令之route - 显示和操作IP路由表
转自： http://codingstandards.iteye.com/blog/1125312 用途说明 route命令用于显示和操作IP路由表（show / manipulate the IP routing table）。要实现两个不同的子网之间的通信，需要一台连接两个网络的路由器，或者同…
ActivityRouter 框架简单实用
ActivityRouter组件化开发小助手用法如下： 跟目录build.gradle dependencies {// activityRouterclasspath com.neenbedankt.gradle.plugins:android-apt:1.8}allprojects {repositories {// ActivityRoutermaven { url "https://jitpack.io" }} } module…
C++ 互斥锁和条件变量实现读写锁
最近的诸多面试经历确实让自己发现内功还不够，还需要持续的学习精进。 实现如下： class RWLock{private:int state;mutex mu;condition_variable cond;public:RWLock():state(0){}void rlock(){mu.lock();while(state < 0){cond.wait(mu);}state;mu…
经常用得到的安卓数据库基类
//创建数据库 public class DBCreate { public static void CreateDatabase(SQLiteDatabase db) { db.beginTransaction(); try { create_NetTaskBuffer(db); insert_SQL(db); db.setTransactionSuccessfu…
mysql5.7 zip安装配置_MySQL5.7的.zip文件的配置安装
由于MySQL5.7之后在javaEE中交互的端口发生了变化，而MySQL官网中5.6、5.7版本64位的只有.zip文件，而.zip文件不像直接下载installer一样可以获取到初始密码，需要通过管理员身份输入命令skip初始密码，所以记录.zip下安装配置过程。…
Linux vsftp配置详解
一.vsftpd说明:LINUX下实现FTP服务的软件很多,最常见的有vsftpd,Wu-ftpd和Proftp等.Red HatEnterprise Linux中默认安装的是vsftpd.访问FTP服务器时需要经过验证,只有经过了FTP服务器的相关验证,用户才能访问和传输文件.vsftpd提供了3种ftp登录形式:(1)anonymous(匿名帐号)使用…
top命令详解-性能分析
top命令是Linux下常用的性能分析工具，能够实时显示系统中各个进程的资源占用状况，常用于服务端性能分析。 top命令说明 [www.linuxidc.comlinuxidc-t-tomcat-188-193 ~]$ top top - 16:07:37 up 241 days, 20:11, 1 user, load average: 0.96, 1.13, 1.2…
leetcode-53 最大子序和
题目描述如下： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，…
docker 离线安装 mysql_Oracle数据库之docker 离线环境安装oracle
本文主要向大家介绍了Oracle数据库之docker 离线环境安装oracle，通过具体的内容向大家展现，希望对大家学习Oracle数据库有所帮助。因测试需要，需在内网的测试环境搭建一套docker Oracle 11g环境进行测试，测试环境为redhat 6.6 安装…
ios Develop mark
App Distribution Guidehttps://developer.apple.com/library/ios/documaentation/IDEs/Conceptual/AppDistributionGuide/Introduction/Introduction.html#//apple_ref/doc/uid/TP40012582 马上着手开发 iOS 应用程序 (Start Developing iOS Apps Today)https://developer.app…
联想打字必须按FN+数字-fn打字
对于联想G40、14英寸系列的本本，好多时候无意间可能把数字键锁定了。 这时候要做的是：打开运行--输入OSK--打开虚拟屏幕键盘。这时候可以找到 选项---打开数字键盘。 有时候某些电脑上没有NUMLOCK这个键。当小键盘打开的时候就又numlock这个键了。这时候…
每日记载内容总结50
Maven中的dependencyManagement 意义【原文链接】 在Maven中dependencyManagement的作用其实相当于一个对所依赖jar包进行版本管理的管理器。 pom.xml文件中，jar的版本判断的两种途径： (1)：如果dependencies里的dependency自己没有声明versio…
leetcode-152 乘积最大子序列
题目描述： 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。 示例 1: 输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 输入: [-2,0,-1] 输出: 0 解释: 结果不能为…
js 监听 安卓事件_百行代码实现js事件监听实现跨页面数据传输
百行代码实现js事件监听实现跨页面数据传输使用场景类似消息队列的使用场景,支持同页面和跨页面通信,发送消息和接收消息技术原理跨页面通信:基于事件监听,通过监听 storage事件监听回调机制,实现跨页面通信,让每个只操作自身页面的操作同页面事件监听:发送事件时,查找回调函数…
Centos安装GD库
tar zxvf ncurses-5.6.tar.gz 进入目录 cd ncurses-5.6 生成 makefile文件，再进一步编译 ./configure --prefix/usr --with-shared --without-debug 编译，编译时间稍微长些，稍等make 编译好最后就是安装了 make install 下面才开始安装 GD库…
centos7安装mongodb3.4
先下载安装包，OS选择RHEL 7.0 Linux 64-bit x64，package选择Server。 这里OS选6.2应该也行，没试过，如果linux版本是6.*的话注意选这个，如果选择7.0安装的时候会提示缺少glibc依赖（glibc版本过低）…
leetcode-300 最长上升子序列
题目描述： 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明: 可能会有多种最长上升子序列的组合，你只需要输出对…
转载自——Json.net动态序列化以及对时间格式的处理
关于我工作中对Json处理的东西 第一:动态序列化类 第二:时间格式处理 通常我们一个类里 可能有十到更多的属性,但是我们序列化通常只需要序列化其中的 三到五个这样的话就会有多余的数据 如果 我只想序列化 id 跟name如何处理 这是我找的网上的方法: using Newtonsoft.Json…
congratulation的用法_congratulation的用法
congratulation用作名词，表示祝贺，恭喜；congratulation表示抽象意义的“祝贺”时，为不可数名词。表示祝贺词时，用作可数名词。1.表示抽象意义的“祝贺”时，为不可数名词。I sent her a gift as a token of …
腾讯微博API时间线相关接口返回的微博信息中head值使用问题
腾讯微博API时间线相关接口返回的微博信息中head值表示作者头像url，这个链接直接访问并不能使用，需要再附加一个参数指定图片的大小（100、50），比如：[head]/100。
java实现https请求
参考： https://www.cnblogs.com/chinway/p/5802541.html java 实现https请求 JSSE是一个SSL和TLS的纯Java实现，通过JSSE可以很容易地编程实现对HTTPS站点的访问。但是，如果该站点的证书未经权威机构的验证，JSSE将拒绝信任该证书从…
设计模式 之美 --- 初篇
接下来的一段时间将按照如下体系导图，对23种设计模式 按照自己的理解一一总结，为后续工作中持续灵活使用做好积累。 学习应用 设计模式的过程有如下好处 提高复杂代码的设计开发能力让阅读源码 和 学习框架事半功倍告别被别人吐槽的烂代码为职场发展做…
C语言中将0到1000的浮点数用强制指针类型转换的方式生成一幅图像
搞过计算机图像的人都知道，图像中的每一个像素通常为一个整型数，它可以分成4个无符号的char类型，以表示其RGBA四个分量。一幅图像可以看做是一个二维整型数组。这里我会生成一个float数组，其数组大小为1000000，刚好100…