400.Nth Digit
400.Nth Digit
难度:Easy
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231).
1
Example 1:
2
3
Input:
4
3
5
6
Output:
7
3
8
Example 2:
9
10
Input:
11
11
12
13
Output:
14
0
15
16
Explanation:
17
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
Copied!
先确定位数范围(1位数、2位数。。。),然后找到对应值。
1
class Solution {
2
public:
3
int findNthDigit(int n) {
4
if(n<10) return n;
5
int start=9;
6
int len=1;
7
int res=9;
8
while(true){
9
long int tmp= start+9*(len+1)*pow(10,len);
10
len++;
11
if(tmp> n)break;
12
start=tmp;
13
res+=9*pow(10,len-1);
14
}
15
if(start ==n) return 9;
16
n-=start;
17
int quo=n/len;
18
int rem=n%len;
19
// cout<<start<< " "<<n<<endl;
20
// cout<<quo<<" " <<rem<<endl;
21
// cout<<len<<" " <<start<<endl;
22
if(rem==0)
23
return (res+quo)%10;
24
else
25
{
26
n=res+quo+1;
27
// cout<<n<<endl;
28
return to_string(n)[rem-1]-'0' ;
29
}
30
31
}
32
};
Copied!
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户 内存消耗 :8.3 MB, 在所有 C++ 提交中击败了80.51%的用户
Copy link