首页 > 专题系列 > Java解POJ > POJ 1019 Number Sequence [解题报告] Java
2013
11-08

POJ 1019 Number Sequence [解题报告] Java

Number Sequence

问题描述 :

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.

For example, the first 80 digits of the sequence are as follows:

11212312341234512345612345671234567812345678912345678910123456789101112345678910

输入:

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

输出:

There should be one output line per test case containing the digit located in the position i.

样例输入:

2
8
3

样例输出:

2
2

解题代码:

//* @author:
方法一:
public class Main { //求数 n 的位数 public static int getWeiShu(int n) { int weiShu = 0; while(n != 0) { n = n/10; weiShu++; } return weiShu; } public static int location(int i) { //i - 所求序数 //ans - 所求位的数字 //j - 递推定位串 //base - 记录每个串递增的位数 //sum - 记录串的总位数 、 用作计数 int ans; int j = 1, base, sum = 1; while(i >= sum) { i -= sum; j++; //j 记载 下一个串 到哪个数字串了 -- 12...j base = getWeiShu(j); //该串比上一个串多的字符数 - j 的位数 sum += base; //该串的字符总数 } //出口:i >= 0 if( i == 0) { ans = (j -1) % 10; return ans; } sum = 1; //从串(1...j) 中第一个数开始找 base = 1; //串中第一个数的位数是 1 while( i >= base) //求 1...j 串中第 i 个数字 { i -= base; sum++; base = getWeiShu(sum); //sum 的位数 } if( i == 0) { ans = (sum -1) % 10; return ans; } j = getWeiShu(sum) - i; while( j-- > 0) //ans is the ith number of (sum) { sum /= 10; } ans = sum % 10; return ans; } public static void main(String[] args) { java.util.Scanner input = new java.util.Scanner(System.in); int t = input.nextInt(); //test number while(t-- > 0) { int i = input.nextInt(); System.out.println( location(i) ); } } } 方法二: import java.util.Scanner; public class Main { static final int LENGHT = 5; int t; int i; int a1[] = new int[LENGHT + 1]; int a2[] = new int[LENGHT + 1]; int b1[] = new int[LENGHT]; int flg[] = new int[LENGHT + 1]; int pos; int temp; int local; int local2; int res; public Main() { a1[0] = 0; a2[0] = 0; b1[0] = 0; a1[1] = 1; flg[0] = 9; for (int i = 1; i < LENGHT + 1; i++) { a1[i] = a2[i - 1] + (i); a2[i] = a1[i] + (flg[i - 1] - 1) * (i); if (i < LENGHT) { b1[i] = b1[i - 1] + (a1[i] + a2[i]) * flg[i - 1] / 2; } flg[i] = flg[i - 1] * 10; } Scanner scan = new Scanner(System.in); t = scan.nextInt(); for (int times = 0; times < t; times++) { i = scan.nextInt(); pos = LENGHT; for (int j = 1; j < LENGHT; j++) { if (i <= b1[j]) { pos = j; break; } } temp = i - b1[pos - 1]; for (int j = 0; j < flg[pos - 1]; j++) { if (temp <= a1[pos] + pos * j) { local = j; break; } else { temp = temp - (a1[pos] + pos * j); } } local = (int) Math.pow(10, pos - 1) + local; for (int i = 1; i < LENGHT + 1; i++) { if (temp <= flg[i - 1] * i) { local2 = i; break; } else { temp = temp - flg[i - 1] * i; } } res = (int) Math.pow(10, local2 - 1); for (; temp > local2;) { temp -= local2; res++; } String str = String.valueOf(res); System.out.println(str.charAt(temp - 1)); } } public static void main(String[] args) { new Main(); } }

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。