剑指offer40_数字序列中某一位的数字

数字序列中某一位的数字

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中，第 5 位（从 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。

请写一个函数求任意位对应的数字。

数据范围

0≤ 输入数字 ≤2147483647

样例

输入：13输出：1

算法思路

该算法用于解决数字序列的第n位问题（序列格式：123456789101112131415...），核心分为两步：

1. 定位数字所在的区间：
   • 确定第n位对应的数字是几位数（i位）。
   • 通过逐步减去i位数的总位数（i * s），缩小n的范围。
   • base表示当前i位数的最小值（如i=3时base=100）。
2. 提取具体数字的某一位：
   • 计算目标数字number：base + (n + i - 1) / i - 1。
   • 确定number中的第r位（通过取模和除法操作）。

class Solution {
public:int digitAtIndex(int n) {/*对于n来说：i:是个几位数;s:该位数有多少个;base：该位数的起始数字;*/long long i = 1, s = 9, base = 1;while(n > i * s){n -= n * s;i ++;s *= 10;base *= 10;}//是几位数的第几个数，那个数就是numberint number = base + (n + i - 1) / i - 1;//是那个数的几分位，n%i=0 表示是最后一位个位;int r = n % i ? n % i : i;for(int j = 0; j < i - r; j ++) number /= 10;return number % 10;}
};