C++算法第n位数
本文涉及知识点
LeetCode:400第N位数的原理、源码及测试用例
给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
提示：
1 <= n <= 231 – 1
分析
|
位数 |
最小数 |
数量 |
n位数的数量等于：最小数*9。总位数等于：数量*位数。 |
||
|
一位数(1到9) |
1 |
9 |
|||
|
两位数(10到99) |
10 |
90 |
|||
|
三位数(100到999) |
100 |
900 |
|||
|
四位数(1000到9999) |
1000 |
9000 |
|||
|
…. |
|||||
|
… |
9000000000000000000000… |
|
|||
大致步骤
计算是多少位数字。
计算是那个数。
从右先左第几位。
计算此位。
代码
核心代码
class Solution {
public:
int findNthDigit(int n) {
long long llN = n;
long long llMin = 1;
int iBitNum = 1;
//计算是几位数
for (; llN > llMin * 9 * iBitNum; iBitNum++)
{
llN -= llMin * 9 * iBitNum;
llMin *= 10;
}
//计算是那个数
int iOrder = (llN - 1) / iBitNum;//第几个数(从零开始）
m_iValue = llMin + iOrder;
//计算从右向左数，第几位
int iBitOrder = (iBitNum-1) - (llN - 1) % iBitNum;
int iValue = m_iValue;
//计算此位
while (iBitOrder-- > 0)
{
iValue /= 10;
}
return iValue %10;
}
int m_iValue;
};
测试代码
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
Solution sln;
int res = 0;
res = sln.findNthDigit(1);
Assert(res, 1);
Assert(sln.m_iValue, 1);
res = sln.findNthDigit(9);
Assert(res, 9);
Assert(sln.m_iValue, 9);
res = sln.findNthDigit(10);
Assert(res, 1);
Assert(sln.m_iValue, 10);
res = sln.findNthDigit(11);
Assert(res, 0);
Assert(sln.m_iValue, 10);
res = sln.findNthDigit(190);
Assert(res, 1);
Assert(sln.m_iValue, 100);
res = sln.findNthDigit(191);
Assert(res, 0);
Assert(sln.m_iValue, 100);
res = sln.findNthDigit(INT_MAX);
Assert(sln.m_iValue, 250954973);
Assert(res, 2);
}
