LeetCode算法题-Nth Digit(Java实现)
这是悦乐书的第215次更新,第228篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第83题(顺位题号是400)。找到无限整数序列的第n个数字1,2,3,4,5,6,7,8,9,10,11 …例如:
输入:3
输出:3
输入:11
输出:0
说明:序列1,2,3,4,5,6,7,8,9,10,11 …的第11位是0,它是数字10的一部分。
注意:n为正整数且符合32位有符号整数(n <2^31)的范围。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
直接使用for循环,从1开始累加字符串,返回第n-1个字符所表示的整数即可。但是此方法严重超时,不建议使用。
public int findNthDigit(int n) {
String str = "";
for (int i=1; i<= n; i++) {
str += i;
}
return Integer.parseInt(str.charAt(n-1)+"");
}
03 第二种解法
题目的意思是有一个以正整数(1,2,3,4,依次向后加1)为基础组成的序列(也可以理解为字符串),传入一个整数n,找出在该序列中的第n位数字。该序列含有以下规律:
1-9,有9个一位数,当n小于等于9的时候,可以在里面找到值。
10-99,有90个两位数,当n大于9且小于等于180+9=189时,可以在里面找到值。
100-999,有900个三位数,当n大于189且小于900x3+189=2889时,可以在里面找到值。
我们可以将此问题分解为三个步骤:
先计算该数字的位数,确定范围。
找出该数字。
确定是该数字中的第几位数。
例如:303
第一步,因为189<303<2889,所以我们要找的是一个三位数,303-189=114,此时n变成114。
第二步,我们要找的数变成了三位数中的第114位,那我们就可以计算出三位数中的第114位数是100+(114-1)/3=137。这里减1是因为在字符串中,索引是从0开始的,而我们的序列字符串是从1开始,所以要减1,你也可以从一开始就减1。
第三步,计算是137中的第几位数,(114-1)%3=2,也就是137的第2位(从0开始)数7,就是我们想要的结果。
在代码中我们使用long类型,预防溢出的风险。
public int findNthDigit2(int n) {
long start = 1, count = 1, num = 9;
while (n > num*count) {
n -= num*count;
count += 1;
start *= 10;
num *= 10;
}
start += (n-1)/count;
String result = start+"";
long index = (n-1)%count;
return result.charAt((int)index)-'0';
}
04 小结
算法专题目前已连续日更超过两个月,算法题文章83+篇,