题目

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

0 ≤ 输入数字 ≤ 2147483647

示例

• 输入：13
• 输出：1

代码

• 解法【视频讲解】

class Solution {
public:
    int digitAtIndex(int n) {
         long long i = 1, s = 9, base = 1; // i表示是几位数，s表示位数共有多少个，base表示位数的起始值。
         while(n > i * s) {   // 9, 90, 900, 9000, 90000, i * s表示位数总共占多少位。
             n -= i * s;         // 1000 - 9 - 90 * 2 - 900 * 3 ,当i= 3 时不符合条件，说明是在三位数里面。
             i ++;                
             s *= 10;
             base *= 10;
         }
         int number = base + (n + i - 1) / i - 1; //求位数的第几个数， 1000 - 9 - 180 = n , n / 3 + base - 1（考虑0故减1）, 向上取整 n + i - 1。
         int r = n % i ? n % i : i;              // 除不尽就是第几位，除尽力了就是最后一位。
         for (int j = 0; j < i - r; j ++) number /= 10;  //求数的第 i - r 位， 除以 10 消去后面 i - r 位。

         return number % 10;    // % 10 拿到个位
    }
};

代码分析：这题如果让我自己做，我恐怕很难想出来 (详见代码注释)。

1、先解释一下题意，这个给定的字符串是由自然数拼接成的:
$$0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + ......$$
然后给定n，问字符串在下标n处对应的是什么数。

2、先把 0 去掉，从 1 开始看，也就是一位数有 9 个$(1-9)$，二位数有 90 个$(10-99)$，三位数有 900 个$(100-999)$，以此类推。

3、所以接下来的就要先找到这个数在第几位数中，再找到在这个数的第几位中。

题目：数字序列中某一位的数字