作者:whisper
链接:https://www.proprogrammar.com/article/902
声明:请尊重原作者的劳动,如需转载请注明出处
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。
请写一个函数,求任意第n位对应的数字。
示例 1:
输入:n = 3 输出:3
示例 2:
输入:n = 11 输出:0
限制:
0 <= n < 2^31
难度:中等; 标签:数学;编程语言:C++
class Solution {
public:
// c++重写
int findNthDigit(int n) {
long num[11] = {0};
num[1] = 9;
for(int i = 2; i <= 10; i++){
num[i] = num[i - 1] / (i - 1) * 10 * i;
}
for(int i = 2; i <= 10; i++){
num[i] += num[i - 1];
}
int i = 0;
while(num[++i] < n);
n -= num[i-1];
int base = 1;
for(int j = 2; j <= i; j++)base*=10;
base += n / i - 1;
int mod = n % i;
if(mod != 0){
base++;
}else{
mod = i;
}
int res = -1;
while(mod++ <= i){
res = base % 10;
base /= 10;
}
return res;
}
};
首先我们要知道,1位数1~9有9个,2位数10~99有90个,3位数100~999有900个,。。。。我们先确定是几位数,如7位数,减掉1~6位数产生的序列和,然后找到这个7位数是多少,即然都是7位数了,/7一下应该就差不多找到了(因为1位数实际有10个,还有一个0,要-1),然后%7就是这个7位数的第几位了,最后return一下
class Solution {
public:
int findNthDigit(int n) {
long digit = 1,start = 1,count = 9; //位数,起始数字,数位数量
while(n > count){
n -= count;
start *= 10;
digit++;
count = 9 * digit * start;
}
//对应的数字:由start开始,位数为digit,第n/digit位
long num = start + (n - 1)/ digit;
int res = to_string(num)[(n - 1)% digit] - '0';
return res;
}
};
方法差不多,但写法很简洁, 有了上面的分析,这里就比较容易理解了
亲爱的读者:有时间可以点赞评论一下
全部评论