JZ44 数字序列中某一位的数字

发表于 分类于 本文字数： 357 阅读时长 ≈ 1 分钟

JZ44 数字序列中某一位的数字

描述

数字以 0123456789101112131415… 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题推，请你输出第 n 位对应的数字。

数据范围： $0≤n≤109 $

示例1

1
2
输入：0
返回值：0

示例2

1
2
输入：2
返回值：2

示例3

1
2
输入：10
返回值：1

示例4

1
2
输入：13
返回值：1

题解

这题是简单？

首先确定最后一次增加的数字是在几位数，即$digitLen$等于几，一位数时，n处于$0\sim9$内，二位数时，n处于$9+90*2 \to 10\sim 189$内，以此类推。并且确定处于这一段内的哪一个位置。

第二步是计算这个数字具体是几，$index = \frac{n-1}{digitLen}$，再加上这一部分的起始数字，即$10^{digitLen}$

最后寻找数字内的位置，$pos = (n-1)%digitLen$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <string>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int findNthDigit(int n) {
        long long digitLen = 1;
        long long count = 9;
        long long start = 1;

        // 找到 n 所在的数字长度
        while (n > digitLen * count) {
            n -= digitLen * count;
            digitLen++;
            count *= 10;
            start *= 10;
        }

        // 找到具体的数字
        long long num = start + (n - 1) / digitLen;
        string s = to_string(num);

        return s[(n - 1) % digitLen] - '0';
    }

};