一、题目大意

        有这样一个序列包含S1，S2，S3...SK,每一个Si包括整数1到 i。求在这个序列中给定的整数n为下标的数。

        例如，前80位为11212312341234512345612345671234567812345678912345678910123456789101112345678910，第8位为2.

二、题解

        动手做这道题之前要了解所求的是第n位而不是某一个Si中的第几个数，一位数占一位，两位数占两位，三位占三位...由于每一组都比前一组多一个数，如果这个数是一位数，则该组数的位数比前一组多1，如果这个数是两位数，则比前一组多2，三位数则多3.这个可以用公式a[i] = a[i-1] +（int）log10((double)i) + 1;表示。我们可以用打表的方法，在求结果之前先打表，用a[i]表示第i组所含的位数，s[i]表示前i组所含的位数。对于每一个给定的位数，先求出它处在哪一个组，然后再求位数。参考

三、java代码

import java.util.*;   public class Main {	 static long a[]=new long[31270];//记录每一组的长度	 static long s[]=new long[31270];//记录总长度	/* 打表 */	static void reset(){	    int i;	    a[1] = 1;	    s[1] = 1;	    for(i = 2; i < 31270; i++){	        /* 每一组数字都比上一组长 (int)log10((double)i) + 1 */	        a[i] = a[i-1] + (int)Math.log10((double)i) + 1;	        s[i] = s[i-1] + a[i];	    }	}	static int work(int n){ /* 计算 */	    int i = 1;	    int length = 0;	    /* 找到 n 所在的组 */	    while (s[i] < n) i++;	    /* n 在该组的下标 */	    long pos = n - s[i-1];	    /* length: n指向的数字的最后一位的下标 */	    //找到i	    for (i = 1; length < pos; i++){	        length += (int)Math.log10((double)i) + 1;	    }	    //i比所求的i多1	    /* 除以10^(length - pos)去掉所求位后面的数字然后取余 */	    /* i: n指向的数字 + 1 */	    //	    return ((i-1) / (int)Math.pow((double)10, length - pos)) % 10;	}	    public static void main(String[] args) {           Scanner sc= new Scanner(System.in);        int t;	    int n;	    reset();	    t=sc.nextInt();	    while(t--!=0)	    {	        n=sc.nextInt();	        System.out.println(work(n));	    }    }}

版权声明：本文为博主原创文章，未经博主允许不得转载。