面试题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
