题目:
数字以0123456789101112...格式序列化到一个字符序列中。在这个序列中,第5位(从0开始)是5,第13位是1。
解答:
比如找1001位数字
1、1位数有10个,0-9,数字为10x1=10个,显然1001>10,跳过这10个数值,在后找第991为位数字(1001-10)
2、2位数有90个:10-99,数字为90x2=180个,显然991>180,继续在后面找881为数字(991-180)
3、3位数有900个:100-999,数字为900x3=2700个,且881<2700,说明第811为数字在位数为3的数值中。
由于811=270x3+1,所以第811位是从100开始的第270个数值的第二个数字,就是7
解答:
1 public class Solution { 2 3 public static void main(String[] args) { 4 int index = 1001; 5 System.out.println(digitAtIndex(index)); 6 } 7 8 public static int digitAtIndex(int index) { 9 if(index < 0) { 10 return -1; 11 } 12 13 int digits = 1; 14 15 while(true) { 16 int digitNumbers = countOfNumberFor(digits); 17 // 数位的数量 18 int countOfNumbers = digits*digitNumbers; 19 20 if(index < countOfNumbers) { 21 return digitAtIndex(index, digits); 22 } else { 23 index = index - countOfNumbers; 24 digits++; 25 } 26 } 27 } 28 29 30 private static int countOfNumberFor(digits) { 31 if(digits == 1) { 32 return 10; 33 } 34 35 int count = (int)Math.pow(10, digits-1); 36 return 9*count; 37 } 38 39 private static int digitAtIndex(int index, int digits) { 40 // 811 = 270x3 + 1 41 42 int number = beginNumberFor(digits) + index/digits; 43 44 // 3 - 811 % 3 = 3 - 1 = 2 45 // 表示从所以第811位是从100开始的第270个数值即370的第二个数字,就是7 46 47 int indexFromRight = digits - index%digits; 48 49 // 370 / 10 = 37 50 for(int i = 1; i < indexFromRight; i++) { 51 number = number / 10; 52 } 53 54 // 37 % 10 = 7 55 56 return number%10; 57 } 58 59 // digits位数的第一个数字 60 private static int beginNumberFor(int digits) { 61 if(digits == 1) { 62 return 0; 63 } 64 65 return (int)Math.pow(10, digits-1); 66 } 67 }