首页 > 代码库 > Number Sequence POJ 1019

Number Sequence POJ 1019

2024-07-06 04:24:33   234人阅读

给定一个字符串满足规律 11212312345……，求其第k位的数字。
 
算法思路：
分组来看，第一组1 第二组12 第三组123 第K组[1:k]
1-9组每组1位， 10-99组每组2位 依次类推。
网上大部分解法，用一个数组表示到第k组时，一共需要多少位数，但这个方法需要额外的空间，而且空间大小并不是非常容易确定。
 
伪代码的思路：sum 表示
while true
     last-sum = sum;
     group-size = last-group-size + member-size; // 本次循环比上次循环多一个数字，需要确定数字的长度。
     sum += group-size;
     if(sum > i)
          pos = i - last_sum;
          res = find(pos); // 在123456……这类字符串中找到第pos位
          break;
     last-group-size = group-size;
     group-num++;
     if(group-num/pow(10, member-size) - (group-num-1)/pow(10, member-size)) member-size++; //从第9组跳到第10组 第99组跳到100组 …… 
 
find 伪代码：
1-9为1位，10-99为2位……分开处理,k 为当前位数
while true
     last-sum = sum;
     sum += 9 * pow(10, k-1) *k
     if(sum > pos)
          rank = (pos - last_sum) / k; //第k个部分的第rank个数
          mod = (pos - last_sum) %k; //第k各部分的第rank个数从前往后的第mod位
          res = (pow(10, k-1) + k)/(pow(10, k-1-mod))%10;
     k++;
     last-sum = sum;
 
 1 #include <iostream>
 2 using namespace std;
 3 
 4 long long int pow(long long int base, long long int exp)
 5 {
 6     long long int result = 1;
 7     for(long long int i = 0; i < exp; i++) {
 8         result *= base;
 9     }
10     return result;
11 }
12 
13 int find(long long pos)
14 {
15     long long sum = 0, last_sum = 0;
16     int k = 1;
17     int result = 0;
18     
19     while(true) {
20         last_sum = sum;
21         sum += 9 * pow(10, k-1) * k;
22         if(sum > pos) {
23             long long diff = pos - last_sum;
24             long long rank = diff / k;
25             long long mod = diff % k;
26             if(k == 1) result = diff + 1;
27             else result = ((pow(10, k-1) + rank)/pow(10, k-1-mod)) % 10;
28             break; 
29         }
30         k++;
31     }
32     
33     return result;
34 }
35 
36 int main()
37 {
38     int t;
39     long long i, group_num, member_size, sum, last_sum, last_group_sum, group_sum, pos, res;
40     cin >> t;
41     for(int j = 0; j < t; j++) {
42         group_num = 1;
43         last_group_sum = 0;
44         member_size = 1;
45         sum = 0;
46         cin >> i;
47         i = i - 1;
48         while(true){
49             last_sum = sum;
50             group_sum = last_group_sum + member_size;
51             sum += group_sum;
52             if(sum > i) {
53                 res = find(i - last_sum);
54                 cout<<res<<endl;
55                 break;
56             }
57             last_group_sum = group_sum;
58             group_num++;
59             if(group_num/pow(10, member_size) - (group_num-1)/pow(10, member_size) == 1) member_size++;
60         }
61     }
62     return 0;
63 }

 


联系
我们