剑指offer第二版-44.数字序列中某一位的数字

本系列导航：剑指offer（第二版）java实现导航帖

面试题44：数字序列中某一位的数字

题目要求：
数字以01234567891011121314...的格式排列。在这个序列中，第5位（从0开始计）是5，第13位是1，第19位是4。求任意第n为对应的数字。

解题思路：
与43题类似,都是数学规律题。如果用遍历的方式，思路代码都很简单，但速度较慢。更好的方式是借助于数字序列的规律，感觉更像是数学题。步骤大致可以分为如下三部分：

以第15位数字2为例（2隶属与12，两位数，位于12从左侧以0号开始下标为1的位置）
步骤1：首先确定该数字是属于几位数的;
      如果是一位数，n<9;如果是两位数，n<9+90*2=189;
      说明是两位数。
步骤2：确定该数字属于哪个数。10+(15-10)/2= 12。
步骤3：确定是该数中哪一位。15-10-(12-10)*2 = 1, 所以位于“12”的下标为1的位置，即数字2。

以第1001位数字7为例
步骤1：首先确定该数字是属于几位数的;
      如果是一位数，n<9;如果是两位数，n<9+90*2=189;如果是三位数，n<189+900*3=2889;
      说明是三位数。
步骤2：确定该数字属于哪个数。100+(1001-190)/3= 370。
步骤3：确定是该数中哪一位。1001-190-(370-100)*3 = 1,所以位于“370”的下标为1的位置，即数字1。

package chapter5;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/3
 * Time  : 8:50
 * Description:数字序列中某一位的数字
 **/
public class P225_DigitsInSequence {
    public static int digitAtIndex(int index){
        if(index<0)
            return -1;
        if(index<10)
            return index;
        int curIndex = 10,length = 2;
        int boundNum = 10;
        while (curIndex+lengthSum(length)<index){
            curIndex+=lengthSum(length);
            boundNum*=10;
            length++;
        }
        int addNum = (index-curIndex)/length;
        int curNum = boundNum + addNum;
        return Integer.toString(curNum).charAt(index-curIndex-addNum*length)-'0';
    }
    public static int lengthSum(int length){
        int count = 9;
        for(int i=1;i<length;i++)
            count*=10;
        return count*length;
    }
    public static void main(String[] args){
        for(int i=9;i<16;i++)
            System.out.println(digitAtIndex(i));
        System.out.println(digitAtIndex(1001));

    }
}

运行结果

9
1
0
1
1
1
2
7