原题(来源Leetcode)
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。
请写一个函数,求任意第n位对应的数字。
示例 1:
输入: n = 3
输出: 3
示例 2:
输入: n = 11
输出: 0
限制:
0 <= n < 2^31
注意:本题与主站 400 题相同:https://leetcode-cn.com/problems/nth-digit/
解法
思想
- 确定下标处在几位数区间(10,11...99两位数区间,100,101...999三位数区间,...)
- 确定下标在该区间的第几个数上(如:101是三位数区间的第2个数)
- 计算下标所处的实际数字以及在第几位
代码
class Solution {
public int findNthDigit(int n) {
if(n < 10) return n;
// 防止溢出
long base = 10;
long k = 90;
long num_n = 2;
while(n>=base){
long newBase = k*num_n+base;
if(n<=newBase){
long count = (n-base)/num_n;
long in_count = (n-base)%num_n;
long num = (long)Math.pow(10,num_n-1)+count;
return (int) (long) (String.valueOf(num).charAt((int) in_count) - '0');
}
base = newBase;
k = k*10;
num_n+=1;
}
return 0;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer44-%e6%95%b0%e5%ad%97%e5%ba%8f%e5%88%97%e4%b8%ad%e6%9f%90%e4%b8%80%e4%bd%8d%e7%9a%84%e6%95%b0%e5%ad%97/