https://leetcode.com/problems/nth-digit/description/
题目
Find the n^th 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 < 2^31).
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
0
Explanation:
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.
题目翻译
题目解析
参考答案
/*
iMinNum iMaxNum iMinDigit iMaxDigit iBase
1 2 3 ...... 9 9 - 1 + 1 = 9 1 9 1
10 11 12 ...... 99 99 - 10 + 1 = 90 10 9 + 90x2 = 189 2
100 ............ 999 999 - 100 + 1 = 900 190 9 + 90x2 + 900x3 = 2889 3
1000 ............ 9999 9999 - 1000 + 1= 9000
.....
例：int n = 12.
那么可以找到12是在第二个区间内的。
iMinNum = 10; iMaxNum = 99; iBase = 2;
iMinDigit = 10; iMaxDigit = 189;
iDigitOffset = n - iMinDigit = 12 - 10 = 2; 在这个区间内偏移2位。
iNumOffset = iDigitOffset / iBase = 2 / 2 = 1; 在这个区间内的第几个数。
iNum = iMinNum + iNumOffset = 10 + 1 = 11; 这个数就是11。
iDigitInNum = iDigitOffset % iBase = 0; 就是在11这个数的第0位。
*/
#include <iostream>
using namespace std;
class Solution {
public:
int findNthDigit(int n) {
long long iBase = 1;
long long iMinNum = 1;
long long iMaxNum = 9;
long long iMinDigit = 1;
long long iMaxDigit = 9;
while (!bInRange(n, iMinDigit, iMaxDigit))
{
iBase++;
iMinNum = iMaxNum + 1;
iMaxNum = iMinNum * 10 - 1;
iMinDigit = iMaxDigit + 1;
iMaxDigit = iMaxDigit + (iMaxNum - iMinNum + 1) * iBase;
}
long long iDigitOffset = n - iMinDigit;
long long iNumOffset = iDigitOffset / iBase;
long long iNum = iMinNum + iNumOffset;
long long iDigitInNum = iDigitOffset % iBase;
return iGetNumDigit(iNum, iDigitInNum, iBase);
}
bool bInRange(long long n, long long iMinDigit, long long iMaxDigit)
{
if (n >= iMinDigit && n <= iMaxDigit)
{
return true;
}
else
{
return false;
}
}
long long iGetNumDigit(long long iNum, long long iDigit, long long iBase)
{
long long t = iBase - 1 - iDigit;
while (t > 0)
{
iNum /= 10;
t--;
}
return iNum % 10;
}
};
int main()
{
//1000000000
Solution o;
cout << o.findNthDigit(10) << endl;
cout << o.findNthDigit(11) << endl;
cout << o.findNthDigit(12) << endl;
cout << o.findNthDigit(13) << endl;
cout << o.findNthDigit(20) << endl;
cout << o.findNthDigit(500) << endl;
return 0;
}
https://github.com/haoel/leetcode/blob/master/algorithms/cpp/nthDigit/NthDigit.cpp
