C++算法：第N位数的原理、源码及测试用例

本文涉及知识点

简单的数学知识。

本博文对应源码，审核比较慢，请耐心等待：
https://download.csdn.net/download/he_zhidan/88504919

本博文在CSDN 学院有对应课程。

题目

给你一个整数 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

分析

大致步骤

计算是多少位数字。

计算是那个数。

从右先左第几位。

计算此位。

代码

核心代码

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);

}

其它

学院课程

运行验证环境

Win10 VS2022 Ck++17 或win7 VS2019 C++17

每天都补充正能量

相关下载

如果你时间宝贵，只想看精华，请到CSDN下载频道下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653