LeetCode刷题【400】第 N 位数字

输入：n = 3
输出：3

输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

同剑指Offer 44 题 数字序列中某一位的数字

解题思路

按图分析

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';
    }
}