LeetCode-400. 第N位数字

题目来源

400. 第 N 位数字

题目详情

给你一个整数 n ,请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

示例 1:

输入: n = 3
输出: 3

示例 2:

输入: n = 11
输出: 0
解释: 第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ,它是 10 的一部分。

提示:

  • 1 <= n <= 231 - 1

题解分析

本题的解题关键是如何定位到指定字符所在的数字。通过仔细观察序列数字串,可以发现,位数为1的数字个数为9,位数为2的数字个数为90,位数为3的数字个数为900,依次类推。

按照上述规律,可以进一步每种位数中包含的字符个数,它们是数字个数与位数的乘积。通过这种模拟法,可以首先求出所述字符是哪种位数的,进而根据除余运算可以计算出这个数字的具体指。最后,问题就转换为了求解某个具体数字的某位上的字符。

算法实现

class Solution {
    public int findNthDigit(int n) {
        // 9 * 1, 90 * 2, 900 * 3, 9000 * 4
        int bit = 1;
        long cnt = 9;
        while (bit * cnt < n) {
            n -= bit * cnt;
            bit++;
            cnt = cnt * 10; 
        }
        // rest表示在bit位数集中的第几字符位,减一是为了下标从0开始计算
        int rest = (int) (n - 1);
        // start表示bit位数集中的起始元素
        int start = (int) Math.pow(10, bit-1);
        // n是bit位数集中的第几个元素
        int pt = rest / bit;
        // num表示第n个字符所在的元素
        int num = start + pt;
        // seq表示对应元素的第几个字符(从左往右)
        int seq = rest % bit;

        // 后续问题转换为求num数字的第seq个字符是什么,1203

        // 去除第seq个字符后面数字后的结果
        int left = num / (int) Math.pow(10, bit - seq -1);
        return left % 10;
    }
}
Either Excellent or Rusty
本文转载于网络 如有侵权请联系删除

相关文章

  • JavaScript 教程「4」:操作符

    运算符(operator),也叫做操作符,主要是用于实现赋值、比较以及执行算数运算等功能的符号。在JavaScript中,主要有以下几类常见的运算符:算数运算符递增递减运算符比较运算符逻辑运算符赋值运算符以下就分别来看看,这些运算符都是怎么用的。算数运算符这个我们应该都不陌生,从小学开始,我们就学习加、减、乘、除、取余等算数运算。而算数运算符也就是供我们算术运算所使用的的符号,主要用来执行两个变量或值的算数运算。varnum1=100; varnum2=5; //105 console.log(num1+num2); //95 console.log(num1-num2); //500 console.log(num1*num2); //20 console.log(num1/num2); //100%5=0 console.log(num1%num2);复制但是在进行算数运算时,特别需要注意的是浮点数的计算,浮点数值的最高精度是17位小数,但算数运算时却远不如整数。同时,我们也需要注意,不要用浮点数来直接进行比较。表达式与返回值所谓表达式,就由数字、运算符、变量等组成的式子。而且表达

  • TypeScript Type Assertions - 类型断言

    有时,您会获得有关TypeScript不知道的值类型的信息。例如,如果你使用document.getElementById,TypeScript只知道这会返回某种HTMLElement,但你可能知道你的页面总是有一个带有给定ID的HTMLCanvasElement。在这种情况下,您可以使用类型断言来指定更具体的类型:constmyCanvas=document.getElementById("main_canvas")asHTMLCanvasElement;复制与类型注释一样,类型断言由编译器删除,不会影响代码的运行时行为。您还可以使用尖括号语法(除非代码在.tsx文件中),它是等效的:constmyCanvas=<HTMLCanvasElement>document.getElementById("main_canvas");复制TypeScript只允许类型断言转换为更具体或不太具体的类型版本。此规则可防止“不可能”的强制,例如:constx=“hello”asnumber;Conversionoftype‘string’toty

  • 不懂源码、NDK、架构设计,只会写业务代码,真的会被淘汰吗?

    无论从事什么职业都有个循序渐进的过程,就拿程序员这个职业来讲,无论多厉害的大师也是从小白一点一滴走过来的,这本身是一件很平常的事情,绝大部分的程序员做的工作就是为了完成业务代码,也就是单元模块,真正去做架构设计的比例少的可怜,如果有机会参与到架构设计里面那是一种幸运,绝大部分程序员一辈子都参与不了架构的设计,很多架构师在工作过程中由于基础积累的还不错,并且在公司中深得信任,于是公司决定让他试一试,如果抓住这种机会出来的了,那就顶上去了,大部分的架构师开始不认为自己能胜任这个角色,挺过来也就过去了。很多程序员在入行之初踌躇满志,结果在遭遇一系列现实的打击之后就会觉得能做个合格的程序员就不错了,因为程序员的技能高低完全靠一点一滴的积累,积累到什么程度技能就达到什么程度,没有所谓的诀窍,只不过有些人理解能力强一些,有些人属于厚积薄发类型的,最终技术岗位靠的就是技术能力的积累,水到渠成顺其自然。题目中的NDK,架构设计完全不同的两种概念,NDK属于安卓下面能够使用C/C++完成应用接口的一套工具集而已,和架构设计完全的两码事,因为很多应用有特殊的功能调用,就通过NDK的方式把C/C++和jav

  • jvm之java类加载机制和类加载器(ClassLoader)的详解

    当程序主动使用某个类时,如果该类还未被加载到内存中,则JVM会通过加载、连接、初始化3个步骤来对该类进行初始化。如果没有意外,JVM将会连续完成3个步骤,所以有时也把这个3个步骤统称为类加载或类初始化。一、类加载过程1.加载加载指的是将类的class文件读入到内存,并为之创建一个java.lang.Class对象,也就是说,当程序中使用任何类时,系统都会为之建立一个java.lang.Class对象。类的加载由类加载器完成,类加载器通常由JVM提供,这些类加载器也是前面所有程序运行的基础,JVM提供的这些类加载器通常被称为系统类加载器。除此之外,开发者可以通过继承ClassLoader基类来创建自己的类加载器。通过使用不同的类加载器,可以从不同来源加载类的二进制数据,通常有如下几种来源。从本地文件系统加载class文件,这是前面绝大部分示例程序的类加载方式。从JAR包加载class文件,这种方式也是很常见的,前面介绍JDBC编程时用到的数据库驱动类就放在JAR文件中,JVM可以从JAR文件中直接加载该class文件。通过网络加载class文件。把一个Java源文件动态编译,并执行加载。

  • 1--安卓多媒体之图片综合篇

    零、前言本篇将涉及: 1.调用系统相机、上传到服务器操作 2.大照片通过采样并压缩尺寸避免OOM 3.media中图片的内容提供者使用方法,增删改查,获取手机所有图片路径 4.显示最近100张照片 5.通过系统图库选择一张加载到界面 实验一:拍一张图片上传到服务器:1.打开系统系统相机//注:Cons.CAMERA_RESULT=1 startActivityForResult(newIntent(MediaStore.ACTION_IMAGE_CAPTURE),Cons.CAMERA_RESULT);复制2.接收返回的Bitmap@Override protectedvoidonActivityResult(intrequestCode,intresultCode,Intentdata){ super.onActivityResult(requestCode,resultCode,data); if(resultCode==RESULT_OK){ //通过intent获取Bundle中的"data"键的数据(即Bitmap) Bitmapbitmap=(Bitma

  • ActionsScript 3.0简易涂鸦板

    使用的编辑器是FlashDevelop(汉化版)需要注意的是,该例子使用到了Button(属于flashcs3/cs4中fl组件,位于fl.controls包下,而此编辑器默认不包含fl包)解决办法:1、在flashcs3/cs4中新建一个fla文件,打开组件库(快捷键Ctrl+F7)将需要用到的组件拖到舞台,如下图:2、打开菜单栏中“文件”——》“发布设置”(快捷键Ctrl+Shift+F12)选中flash项,勾选“导出swc”3、保存fla,ctrl+enter导出影片,在该fla文件同级目录下会有一个同名的且后缀名为.swc的文件,将此文件copy并粘贴至FlashDevelop中bin目录下,默认为正常色,右击选中该swc组件包,点击选中“AddToLibrary”代码中就可以使用Button组件了privatevarbutton:Button;button=newButton; button.label="点击清空舞台"; addChild(button); button.addEventListener(MouseEvent.CLICK,onclick

  • 环境变量

    Linux常见的环境变量决定了shell将到哪些目录中寻找命令或程序:$PATH: 具体介绍参见后面详解。当前用户主目录:$HOME: 当前用户的邮件存放目录:$MAIL: 当前用户用的是哪种Shell:$SHELL: 是指保存历史命令记录的条数$HISTSIZE: 当前用户的登录名:$LOGNAME: 主机的名称,许多应用程序如果要用到主机名的话,通常是从这个环境变量中来取得的:$HOSTNAME: 和语言相关的环境变量,使用多种语言的用户可以修改此环境变量:$LANG/LANGUGE: 基本提示符,对于root用户是#,对于普通用户是$,也可以使用一些更复杂的值:$PS1: 附属提示符,默认是“>”。可以通过修改此环境变量来修改当前的命令符:$PS2: 比如下列命令会将提示符修改成字符串“Hello,MyNewPrompt:)”:PS1="Hello,MyNewPrompt:)"复制输入域分隔符:$IFS: 当shell读取输入时,用来分隔单词的一组字符,它们通常是空格、制表符和换行符。shell脚本的名字:$0: 例如,在我的Linux系统中:$echo

  • 要做大视频付费市场,爱奇艺和吴亦凡的一手“骄傲牌”怎么打?

    明星代言在互联网行业已是打造品牌的常规动作,最近一年互联网公司还玩起了聘请明星做“高管”的花样。不过,视频平台聘请代言人却不多见。互联网时代视频网站和电视台共同承担起了娱乐文化传播的功能。但电视台只会播放其它品牌的广告,不会聘请代言人给自己做广告。而视频网站有例外,那就是爱奇艺,已经多次启用代言人,且针对的是一个特别的产品:会员。 9月6日,爱奇艺VIP会员品牌战略全新升级,正式启用吴亦凡担任爱奇艺“首席会员非凡体验官”,并推出“敢骄傲,一起燥”的生活态度。去年12月,赵丽颖和陈伟霆一起“入职”爱奇艺,做起了首席会员推荐官。2015年,爱奇艺则连续启用杨洋、Angelababy和黄渤担任会员产品代言人。现在每家主流视频网站都已推出会员服务。而为会员启用代言人的,却只有爱奇艺一家,6位明星三年来换着花样代言会员,爱奇艺对明星代言会员这个产品的热衷程度,堪比快消品、手机等公司。为什么只有爱奇艺为会员找代言人?要回答这个问题,先来看一下视频会员竞争的大环境。内容付费潮掀起视频会员大战2016年,是中国网络视频的第十个年头,也是下半场的开始。这一年,爱奇艺等视频网站先后宣布,付费会员数量,突破

  • python爬虫beautifulsoup4系列4-子节点​

    前言很多时候我们无法直接定位到某个元素,我们可以先定位它的父元素,通过父元素来找子元素就比较容易,简单一点来说就是通过父亲找儿子。 一、子节点1.以博客园首页的摘要为例:<divclass="c_b_p_desc">这个tag为起点2.那么div这个tag就是父节点3."摘要:前言本篇详细。。。"这个string就是上面div的子节点(string通常看成是一个tag的子节点)4."<aclass="c_b_p_desc_readmore"href="http://www.cnblogs.com/yoyoketang/p/6906558.html">阅读全文</a>"这个也是div的子节点二、.contents1.tag对象contents可以获取所有的子节点,返回的是list2.len()函数统计子节点的个数3.通过下标可以取出对应的子节点#coding:utf-8 frombs4importBeautifulSoup importrequests

  • 随笔:docker安装

    docker安装 注意: 不同版本的Linux系统或者其他系统安装的docker版本是不一样的,我是在centOS上安装的,且centOS版本不能低于centOS7 步骤: 一、查询Linux版本:uname-r二、查询可安装版本:yumlistdocker-ce.x86_64--showduplicates|sort-r三、尝试安装自己想安装的版本:yuminstalldocker-ce-18.09.9docker-ce-cli-18.09.9containerd.io四、可能报错:Package:3:docker-ce-18.09.9-3.el7.x86_64(docker-ce-stable)Requires:container-selinux>=2.9原因分析:报错是container-selinux版本低或者是没安装的原因yum安装container-selinux一般的yum源又找不到这个包需要安装epel源才能yum安装container-selinux这时直接用yum安装container-selinux可能会报错,可以进行如下步骤:1、wget-O/etc

  • BFC

    1.规范解释 块格式化上下文(BlockFormattingContext,BFC)是Web页面的可视化CSS渲染的一部分,是布局过程中生成块级盒子的区域,也是浮动元素与其他元素的交互限定区域。复制 2.通俗理解 BFC是一个独立的布局环境,可以理解为一个容器,在这个容器中按照一定规则进行物品摆放,并且不会影响其它环境中的物品。 如果一个元素符合触发BFC的条件,则BFC中的元素布局不受外部影响。 浮动元素会创建BFC,则浮动元素内部子元素主要受该浮动元素影响,所以两个浮动元素之间是互不影响的。 二、创建BFC 根元素或包含根元素的元素 浮动元素float=left|right或inherit(≠none) 绝对定位元素position=absolute或fixed display=inline-block|flex|inline-flex|table-cell或table-caption overflow=hidden|auto或scroll(≠visible) 三、BFC的特性 BFC是一个独立的容器,容器内子元素不会影响容器外的元素。反之亦如此。 盒子从顶端开始垂直

  • 9、ABPZero系列教程之拼多多卖家工具 拼团提醒类库封装

      本篇开始正式做功能,我在开发拼团提醒之前,拼多多并没有放出拼团人数不足就提醒卖家的功能。 有这个想法主要来源于朋友的抱怨,我想这应该是大部分卖家的心声吧。 经过分析,拿到了几个api,不要问我api怎么拿到的,这不是本系列的内容。 接口1:http://apiv4.yangkeduo.com/mall/{0}/info?pdduid=0(传入店铺编号,可以获取店铺资料) 接口2:http://apiv4.yangkeduo.com/v2/mall/{0}/goods?page=1&size=500&sort_type=PRIORITY&pdduid=0(传入店铺编号,可以拿到店铺商品资料,拼多多限制最多获取500个商品) 接口3:http://apiv2.yangkeduo.com/v2/goods/{0}/local_group(传入商品id,可以获取拼团信息) 有了这几个api,拼团提醒功能就不在话下,接下来讲解实现过程。    建立新项目  在解决方案下建立PddTool项目,目的是把拼多多相关业务逻辑以专门的一个类库来实

  • Wndows下使用nvm管理node版本及踩坑

    由于最近同时管理三个不同时期的项目,发现每个项目的node环境都不相同,但是又不想要重复安装node.js,所以采用nvm方式管理node版本 安装 参考安装教程 坑点 按照上述步骤安装完成后,可能会遇到,node-v命令正常,但是npm命令无效,经过各种查询,发现8.11以上版本的node版本对应的npm都没法自动安装,所以要进行手动安装 参考npm无效解决方法 如果是从node.js官网下载的node.js压缩包,跟上面教程中步骤不同的地方就是,只需要把解压缩后的node_modules中npm复制,放在nvm中node_modules中即可,然后将npm中bin文件夹下的npm,npm.cmd复制出来放到跟node_modules同级即可 更新 关于上面的坑点,经过各种测试,最后发现可能是电脑的hosts文件的问题,因为之前修改过hosts来加速访问github.com(但是近期无法打开github,很迷),导致无法自动安装npm,删除hosts中加速那几行,重新安装步骤安装一遍,完全没有问题,npm也会自动安装

  • Overleaf编译LaTex报错:Missing number, treated as zero.&lt;to be read again&gt;

    Google了一下,发现官网给出了解释:https://www.overleaf.com/learn/latex/Errors/Illegal_unit_of_measure_(pt_inserted) 经过对照,原因就是使用的包subfigure比较老,\begin{subfigure}{0.32\textwidth}这样的写法就会报错。将\usepackage{subfigure}改为\usepackage{subcaption}即可。

  • 日志客户端设计问题

    前段时间在做应用db访问日志客户端的开发,这里记录下日志客户端设计相关问题: 1.如何拦截请求? a.公司的db访问都是统一经过dal框架,所以动态给dal框架底层执行方法增加拦截代码即可。主要思路是在注册tomcat启动监听,在监听代码中,注册jvm修改类定义的tranform(参考jvm的instrument功能),最后使用asm修改dal代码,增加拦截记录日志代码。这样客户端无需做改动。 b.使用jvm-sandbox框架,jvm-sandbox底层也是使用方法a的原理。 差别: 方法a需要在应用代码里加入记录日志代码依赖。具体是在pom增加dependency,方法b不需要在应用代码里加,但是需要在应用的应用服务器上启动jvm-sandbox进程。 最终选型: 日志记录端使用方法a,原因是使用方法b对开发者透明,不容易管理。我们还有给记录的日志进行流量回放的功能,在流量回放的时候使用了方法b,因为流量回放只会在测试环境做,所以管理问题没有那么严重,而且回放使用方法b还有个好处就是动态插拔,jvm-sandbox可以只在测试环境部署。 下面从方法a来讲解客户端设计需要注意的地方:

  • HQL实现模糊查询

    hibernate实现模糊查询两种传参方式,其实各个方法的实质都是一样的,只不过传递参数的方法稍微有点区别 复制    publicList<User>getUsers(Stringid){ Listlist=newArrayList<User>(); Stringhql="fromUserasuserwhereuser.idlike'%"+id+"%'"; factory=DBHelper.getSessionFactory(); Sessionsession=factory.openSession(); Transactiontransaction=session.beginTransaction(); Queryquery=session.createQuery(hql); list=query.list(); transaction.commit(); session.close(); returnlist; } 复制      publicList<User>getUsers(Stringid){ Li

  • 数仓架构演进

    数仓架构演进 1、介绍     数仓架构演进,从一开始的离线数仓,到带实时数仓的Lambda架构,再到流批一体的Kappa架构,最终发展到多引擎混用。       离线数仓架构 2、Lambda     lambda架构 lambda架构基本介绍: lambda架构最早是由storm的创始人,NathanMarz进行提出并描述了我们目前所了解的lambda架构。 lamda架构先为主,已经适用在了绝大部分的公司里面了。绝大部分公司从刚开始发展大数据技术为主,到现在都是采用的lamda架构。 lamda架构说白了就是公司的离线和实时处理技术走两条线,离线的专门做离线数据处理(例如使用hive,impala,presto,sparkSQL等各种OLAP的技术框架),实时的就专门使用实时处理技术(例如storm,sparkStreaming,flink流处理程序等)。   Lambda架构经历多年的发展,其优点是稳定,对于实时计算部分的计算成本可控,批量处理可以用晚上的时间来整体批量计算

  • Spring Data JPA -1-CRUD入门

    1)引入jar包支持 1<dependency> 2<groupId>org.springframework.boot</groupId> 3<artifactId>spring-boot-starter-data-jpa</artifactId> 4</dependency> 5 6<!--数据库支持--> 7<dependency> 8<groupId>mysql</groupId> 9<artifactId>mysql-connector-java</artifactId> 10</dependency>复制 ViewCode 2)数据库表  3)java实体   注意,框架本身并不能识别转换驼峰和下划线,必须使用注解@Column(name="user_id")映射出正确的字段名   别忘了再类头上加上注解@Table(name="user")指定数据库名称 1@Entity 2@Table(name="

  • 前端跨域之Jsonp实现原理及.Net下Jsonp的实现

    jsonp的本质是通过script标签的src属性请求到服务端,拿到到服务端返回的数据,因为src是可以跨域的。前端通过src发送跨域请求时在请求的url带上回调函数,服务端收到请求时,接受前端传过来的回掉函数名称,将其拼接成js函数调用返回到前端即可完成跨域请求。 前端实现代码: <!DOCTYPEhtml> <htmllang="en"> <head> <metacharset="UTF-8"> <metaname="viewport"content="width=device-width,initial-scale=1.0"> <metahttp-equiv="X-UA-Compatible"content="ie=edge"> <title>Document</title> </head> <body> </body> </html> <script> functionsuccessFun(data){ conso

  • 正向代理与反向代理

    1、前言   最近工作中用到反向代理,发现网络代理的玩法还真不少,网络背后有很多需要去学习。而在此之前仅仅使用了过代理软件,曾经为了访问google,使用了代理软件,需要在浏览器中配置代理的地址。我只知道有代理这个概念,并不清楚代理还有正向和反向之分,于是赶紧学习一下,补充一下知识。首先弄清楚什么是正向代理,什么是反向代理,然后是二者在实际使用中展示的方式是什么样的,最后总结一下正向代理用来做什么,反向代理可以做什么。 2、正向代理   正向代理类似一个跳板机,代理访问外部资源。 举个例子:   我是一个用户,我访问不了某网站,但是我能访问一个代理服务器,这个代理服务器呢,他能访问那个我不能访问的网站,于是我先连上代理服务器,告诉他我需要那个无法访问网站的内容,代理服务器去取回来,然后返回给我。从网站的角度,只在代理服务器来取内容的时候有一次记录,有时候并不知道是用户的请求,也隐藏了用户的资料,这取决于代理告不告诉网站。   客户端必须设置正向代理服务器,当然前提是要知道正向代理服务器的IP地址,还有代理程序的端口。   例如之前使用过这类软件例如CCproxy,http://w

  • 电机随笔(三)

       还是先写点读后感吧。    首先中断的看表示有点不爽。    从特斯拉的故事中我们不难看出资本的重要性。    再优秀的科学家需要资本的支持来进行自己的事业,大量的实验不仅需要花费大量的时间,更要投入大量的钱财资源,没有资本何来产出。    西方的研究者往往是有闲情逸致的贵族和有闲情逸致的贵族资助的人,高效蒸汽机发明者瓦特就是如此,得贵人相助并互成贵人,思想家马克思也是如此,由故事看来特斯拉与豪斯亦是如此。    美国在当时世界拥有较全面的专利保障系统,鼓励发明家创新;有大量新发掘的空余资本等待发明家使用;还有一个相对与世隔绝的安稳地理政治环境。是以各国优秀科学家发明家纷纷涌向美国,是以美国的科学发展突飞猛进,立于世界之巅。    光为利比又为名又为利生存容易得多,爱迪生不光为名为利还为自己要强的本心而活,不愿承认后起之秀特斯拉交流系统的优秀是原因没错,不愿让出直流电的市场

相关推荐

推荐阅读