LeetCode刷题【剑指 Offer 44】数字序列中某一位的数字

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

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

 

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

 

限制：

• 0 <= n < 2^31

注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/

模拟分析

按图分析

1. 0-9的时候都可以直接返回自己
2. 10-99一共有90个数字，每个数字两个字符
3. 100-999一共有900个数字，每个数字三个字符
4. 1000-9999一共有9000个数字，每个数字四个字符
5. 后续雷同

按照这个规律分析，我们只需从头开始，依次从头开始

1. 减去10个字符
2. 减去90 * 2 个字符
3. 减去900 * 3个字符
4. 减去9000 * 4个字符
5. 如果不够减了则从这一档的1 x 10^pow 开始，

• 首先除一下当前档位的字符长度，就知道当前档位的第某个数字，在加上这个档位的开始值1 x 10^pow ，就能得到当前是在哪个数字
• 再于一下当前档位的数字的长度，就知道了是刚刚求得的结果中的数字，从左往右从下标0开始的第某个数字

问题

1. 运算中间的值

 cur + 9 * powOf10 * ( pow+1 ) 

会超过int型上限，所以最简单的处理办法中间的运算过程用了long型数据

2. 取最后结果的某一位数字也可以用数学方法，不过偷懒了下直接转字符串了

代码

class Solution {
    public int findNthDigit(int n) {
        if (n < 10){
            return n;
        }
        long cur = 10;
        long powOf10 = 10;
        long pow = 1;
        while (cur + 9 * powOf10 * ( pow+1 )< n){
            cur += 9 * powOf10 * (pow+1);
            powOf10 *= 10;
            pow++;
        }
        long order = powOf10 + (n-cur) / (pow+1);
        long idx = (n - cur) % (pow+1);
        String orderStr = Long.toString(order);
        return orderStr.charAt((int)idx)-'0';
    }
}