面试题44：数字序列中某一位的数字（C++）

标签：题目   返回   while   splay   循环   isp   思路   size   etc   

题目地址：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。

题目示例

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

解题思路

确定数字序列中的某一位的数字步骤可分为三步：

• Step1：确定n所在数字的位数，我们用变量digit表示。具体思路是采用循环执行n减去一位数、两位数、三位数、......、的数位数量count，直到n小于等于count时跳出循环；

(图源：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/)

• Step2：确定n所在的数字，即所求数位的所在数字，使用num表示，而所求数位在从数字start开始的第(n-1)/digit个数中；

(图源：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/)

• Step3：确定n是num中的哪一数位，并返回结果，而所求数位在数字num中的第(n-1)%digit位。

(图源：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/)

程序源码

class Solution {
public:
    int findNthDigit(int n) {
        if(n == 0) return 0;
        long digit = 1; //数位，即数字位数
        long start = 1; //起始值，1/10/100/...
        long count = 9; //数位数量=9*start*digit
        while(n > count)//1.确定所求数位的数字位数digit
        {
            n -= count;
            digit += 1;
            start *= 10; 
            count = start * digit * 9; //计算数位数量

        }
        long num = start + (n - 1) / digit; //2.确定所求数位的数字num
        string num_string = to_string(num); 
        return num_string[((n - 1) % digit)] - ‘0‘; //3.确定所求数位，获得num中的第(n-1)%digit个数位
    }
};

参考文章

https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/

面试题44：数字序列中某一位的数字（C++）

标签：题目   返回   while   splay   循环   isp   思路   size   etc   

原文地址：https://www.cnblogs.com/wzw0625/p/12784191.html