剑指offer 面试题44 (java版) 数字序列中某一位的数字

ゝ一纸荒年。 2023-07-08 15:29 13阅读 0赞

### [welcome to my blog][] ###

## 剑指offer面试题44(java版):数字序列中某一位的数字 ##

### 题目描述 ###

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，
    第13位是1，第19位是4，等等。
    
    请写一个函数，求任意第n位对应的数字。
    
    
    示例 1：
    
    输入：n = 3
    输出：3
    示例 2：
    
    输入：n = 11
    输出：0

#### 第一次做; 核心: 1)find the length of the number where the nth digit is from; 2)find the actual number where the nth digit is from; 3)find the nth digit and return; 和我想的一样, 但是代码要比我第一版简洁太多; 但还不如最优解写得简洁; 4) count得用long类型, 10亿位数有90亿个, 超出了int的最大值21.47亿; 5) -=操作符与自动转型 6) base case后面的n都大于等于1; 记住一个案例,n=192, res=0; 跳出while循环后的n==3; 所以需要(n-1)/3 ####

class Solution { 
        public int findNthDigit(int n) { 
            if(n==0)
                return 0;
            //数字的长度为len; 从长度为1的数字开始, 也就是从个位数开始
            int len = 1;
            //长度为len的数字有count个
            long count = 9;
            //长度为len的第一个数字
            int start = 1;
            //确定第n位对应的数字的长度
            while(n > len*count){ 
                // n = n - len*count; //这么写会报错, 需要把count转成int
                n -= len*count; //这么写就不报错了
                //update
                len++;
                start = start*10;
                count = count*10;
            }
            //确定第n位对应的数字是哪个长度为len的数字
            start = start + (n%len==0? n/len-1 : n/len);
            //取出该数字的第(n-1)%len位
            String s = Integer.toString(start);
            return Character.getNumericValue(s.charAt(n%len==0? len-1 : n%len-1));
        }
    }

#### 第一次做; 核心: 1)找出n属于的数的长度是多少 2)如果n属于长度为len+1的某个数, 找出n属于第几个长度为len+1的数 3)找出n是那个数的第几位 ####

/* 个位数:0~9 10 10*1 十位数: 10~99 90 90*2 百位数: 100~999 900 900*3 千位数: 1000~9999 9000 9000*4 */
    class Solution { 
        public int findNthDigit(int n) { 
            //最高位是十亿
            int digit = 10;
            //arr[i]表示长度为i的数字的个数
            long[] arr = new long[digit+1];
            //长度为0的数字的个数是0
            arr[0] = 0;
            arr[1] = 10;
            //从长度为2的数字开始;(也就是从十位数开始)
            int len = 2;
            for(long i=10; i<=1000000000; i*=10){ 
                arr[len] = 9*i*len + arr[len-1];
                len++;
            }
            len=0;
            for(; len < arr.length-1; len++){ 
                if(n>=arr[len] && n<arr[len+1])
                    break;
            }
            //here, arr[len] =< n <= arr[len+1], 说明n的长度是len+1
            //接下来要找出在所有的长度为len+1的数字中, n属于第几个
            //属于第order个还是第(order+1)个?
            //order表示包含order个完整的长度为len+1的数
            int order = (n+1 - (int)arr[len] ) / (len+1);
            int mod = (n+1 - (int)arr[len] ) % (len+1);
            //如果mod==0说明n属于第order个长度为len+1的数字;
            if(mod==0){ 
                //如果是个位数,
                if(len+1==1)
                    return ((int)Math.pow(10, len)+order-2) % 10;
                //注意, 长度为len+1的数字中, Math.pow(10,len)排在第一个
                return ((int)Math.pow(10, len)+order-1) % 10;
            }
            //如果mod!=0说明n属于第(order+1)个长度为len+1的数字
            int target = (int)Math.pow(10, len) + order;
            return target / (int)Math.pow(10, len-(mod-1)) % 10;
        }
    }

#### [LeetCode最优解][LeetCode] ####

public int findNthDigit(int n) { 
    		int len = 1;
    		long count = 9;
    		int start = 1;
    
    		while (n > len * count) { 
    			n -= len * count;
    			len += 1;
    			count *= 10;
    			start *= 10;
    		}
    
    		start += (n - 1) / len;
    		String s = Integer.toString(start);
    		return Character.getNumericValue(s.charAt((n - 1) % len));
    	}

#### 关于n-1 ####

![format_png][]

[welcome to my blog]: https://littlehaes.com
[LeetCode]: https://leetcode.com/problems/nth-digit/discuss/88363/Java-solution
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS83MGJiYmYxYzNmZTRkYzVkN2Y1MWU0MDMyOTI2ODhiMC94bWxub3RlL0U5M0EzMEI4QkFEMjQ0RTY4RUJGRDA4MUMzN0NEQUM2LzYzMjA0?x-oss-process=image/format,png