剑指offer44-数字序列中某一位的数字

原题(来源Leetcode)

数字以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. 确定下标处在几位数区间(10,11...99两位数区间,100,101...999三位数区间,...)
  2. 确定下标在该区间的第几个数上(如:101是三位数区间的第2个数)
  3. 计算下标所处的实际数字以及在第几位

代码

class Solution {
    public int findNthDigit(int n) {
        if(n < 10) return n;
        // 防止溢出
        long base = 10;
        long k = 90;
        long num_n = 2;
        while(n>=base){
            long newBase = k*num_n+base;
            if(n<=newBase){
                long count = (n-base)/num_n;
                long in_count = (n-base)%num_n;
                long num = (long)Math.pow(10,num_n-1)+count;
                return (int) (long) (String.valueOf(num).charAt((int) in_count) - '0');
            }
            base = newBase;
            k = k*10;
            num_n+=1;
        }
        return 0;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer44-%e6%95%b0%e5%ad%97%e5%ba%8f%e5%88%97%e4%b8%ad%e6%9f%90%e4%b8%80%e4%bd%8d%e7%9a%84%e6%95%b0%e5%ad%97/