华为机试HJ25 数据分类处理
首先看一下题
描述
信息社会，有海量的数据需要分析处理，比如公安局分析身份证号码、 QQ 用户、手机号码、银行帐号等信息及活动记录。
采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。
数据范围：1≤I,R≤100 ，输入的整数大小满足 0≤val≤2^31−1
输入描述：
一组输入整数序列I和一组规则整数序列R，I和R序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为0~(2^31)-1，序列个数不限
输出描述：
从R依次中取出R<i>，对I进行处理，找到满足条件的I：
I整数对应的数字需要连续包含R<i>对应的数字。比如R<i>为23，I为231，那么I包含了R<i>，条件满足 。
按R<i>从小到大的顺序:
(1)先输出R<i>；
(2)再输出满足条件的I的个数；
(3)然后输出满足条件的I在I序列中的位置索引(从0开始)；
(4)最后再输出I。
附加条件：
(1)R<i>需要从小到大排序。相同的R<i>只需要输出索引小的以及满足条件的I，索引大的需要过滤掉
(2)如果没有满足条件的I，对应的R<i>不用输出
(3)最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)
序列I：15,123,456,786,453,46,7,5,3,665,453456,745,456,786,453,123（第一个15表明后续有15个整数）
序列R：5,6,3,6,3,0（第一个5表明后续有5个整数）
输出：30, 3,6,0,123,3,453,7,3,9,453456,13,453,14,123,6,7,1,456,2,786,4,46,8,665,9,453456,11,456,12,786
说明：
30----后续有30个整数
3----从小到大排序，第一个R<i>为0，但没有满足条件的I，不输出0，而下一个R<i>是3
6--- 存在6个包含3的I
0--- 123所在的原序号为0
123--- 123包含3，满足条件
示例1
输入：
15 123 456 786 453 46 7 5 3 665 453456 745 456 786 453 123 5 6 3 6 3 0输出：
30 3 6 0 123 3 453 7 3 9 453456 13 453 14 123 6 7 1 456 2 786 4 46 8 665 9 453456 11 456 12 786说明：
将序列R：5,6,3,6,3,0（第一个5表明后续有5个整数）排序去重后，可得0,3,6。 序列I没有包含0的元素。 序列I中包含3的元素有：I[0]的值为123、I[3]的值为453、I[7]的值为3、I[9]的值为453456、I[13]的值为453、I[14]的值为123。 序列I中包含6的元素有：I[1]的值为456、I[2]的值为786、I[4]的值为46、I[8]的值为665、I[9]的值为453456、I[11]的值为456、I[12]的值为786。 最后按题目要求的格式进行输出即可。
一、问题分析
1.采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。
2.输入描述:R和I是两个整数序列,他们包含1到100个整数,每个整数的大小在[0,2^31 - 1]之间
3.R和I序列中的第一个数字代表他们包含的数字数量(这个数字不包含它本身)
4.所以输入中的第一行是R,第二行是I
5.输出描述:从R中依次取出R<i>,对I进行处理(注意这里的i是说从0到R的个数的索引值,和I没有关系)
6.找到满足条件的I
7.I整数对应的数字需要连续包含R<i>对应的数字.(I序列中存在连续包含R<i>的整数,这就是我们要寻找的数字)
8.按R<i>从小到大的顺序:(默认不是从小到大的顺序)
(1)先输出R<i>
(2)再输出满足条件的I的个数
(3)然后输出满足条件的I在I序列中的位置索引(从0开始)
(4)最后再输出I(应该是输出满足条件的I)
9.附加条件:(1)R<i>需要从小到大排序.
10.相同的R<i>只需要输出索引小的以及满足条件的I,索引大的需要过滤掉
(我是这么理解的,如果I中有重复的满足条件的整数,只计算先出现的(索引小的),之后出现的,忽略)
11.(2)如果没有满足条件的I,对应的R<i>不用输出
12.最后需要在输出序列的第一个整数位置记录后续整数序列的个数(不包含“个数”本身)
二、解题思路
1.首先我们需要定义两个整数数组,一个I[101]和一个R[101]
2.我们需要定义两个整数,一个numofI,一个numofR
3.我们读取数据,首先读取I的数据,先读取numofI,然后将每个数据读如I中
4.然后我们读取R的数据,先读取一个整数到numofR,然后将每个数据读如R中
5.之后对我们的R进行排序和去重,我们可以先用qsort对R进行排序,然后再去重
6.之后我们需要更新numofR的值
7.然后我们从R中依次取出R<i>,并检查I中是否连续包含R<i>的数字.
8.检查之前我们需要定义一个整数qualifyI[numofR],初始化值为0,用来记录对于每个R,我们有多少个满足的I(满足条件的I的个数),
9.我们还需要定义一个indexofI[numofR][100],用来存储我们每个R,的满足条件的I的索引值
10.然后我们可以开始检查I中是否存在连续包含R<i>的数字,我们遍历I
11.因为I包含R<i>中的数字,所以我们可以认为I应该大于等于R<i>,否则不包含
12.如果I<j>大于等于R<i>,我们检查I<j>是否包含R<i>,当I<j>大于等于R<i>时,
我们建立两个临时数tempI和tempR,分别等于I<j>和R<i>的值,
我们利用对10求余的方法求他们最后一位数字是否相同
如果不相同,我们的tempI的值变成他原来的值除以10之后的值,然后我们进入下一次循环继续判断
tempI和tempR最后一位是否相同,如果相同,我们继续判断剩下的位数,如果全部相同,tempR%10 == tempI % 10 && (tempR/10 == 0)的时候, 我们先检查对于已经存在的indexofI[i]中是否存在一个索引,代表的数字和我们找到的数字相同,如果存在一个索引值x使得I[indexofI[i][x]] == I<j>我们找到了重复的数字,忽略不计(continue),否则的话我们将这个I<j>的index,放入indexofI[i][qualifyI[i]] = j中,并且更新我们的qualifyI[i]++; (这一步好像错了,并不需要去除重复的)
13.对于我们所有的qualifyI中的值我们统计到一个整数total中去,并且每有一个qualifyI不为0我们的total就+2,并加上qualifyI的两倍数字
14.先输出total,然后输出qualifyI[i]不为0的R<i>的值,然后输出qualifyI[i],indexofI[i][从0到qualifyI[i]],I<indexof[i][从0到qualifyI[i]]>
三、具体步骤
#include <stdio.h>
#include <stdlib.h>
// 比较函数，用于 qsort
int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
// 判断数字 i 是否连续包含数字 j
int contains(int i, int j) { // 比如I是123,R是0
if (i < j) return 0; // 如果123 < 0, 证明没有包含关系
int tempI = i;
int tempJ = j;
if (tempJ == 0) {
while (tempI / 10 != 0) {
if (tempI % 10 == 0) return 1;
else tempI /= 10;
}
return 0;
} else {
while (tempJ > 0 && tempI > 0) {
if (tempI % 10 == tempJ % 10) {
// printf("%d contains %d's last digit\n", tempI, tempJ);
while(tempI % 10 == tempJ % 10){
tempI /= 10;
tempJ /= 10;
if(tempJ == 0) {
return 1;
}
if(tempI % 10 != tempJ % 10){
tempJ = j;
break;
}
}
} else {
tempI /= 10;
}
}
}
return tempJ == 0;
}
int main() {
int I[101];
int R[101];
int numOfI, numOfR;
scanf("%d", &numOfI);
for (int i = 0; i < numOfI; i++) {
scanf("%d", &I[i]);
}
//test
// for (int i = 0; i < numOfI; i++) {
// printf("%d\n", I[i]);
// }
scanf("%d", &numOfR);
for (int i = 0; i < numOfR; i++) {
scanf("%d", &R[i]);
}
//test
// for (int i = 0; i < numOfR; i++) {
// printf("%d\n", R[i]);
// }
// 使用 qsort 对 R 进行排序
qsort(R, numOfR, sizeof(int), compare);
//test
// for (int i = 0; i < numOfR; i++) {
// printf("%d\n", R[i]);
// }
// 去重并更新 numOfR
int newR[numOfR + 1];
int newNumOfR = 0;
for (int i = 0; i < numOfR; i++) {
if (R[i] == R[i + 1]) {
// 如果后面的数字和这个数字相同,我们需要跳过相同的数字
newR[newNumOfR++] = R[i];
while (R[i] == R[i + 1]) { //直到遇到下一个新的数字我们停止
i++;
}
} else {
newR[newNumOfR++] = R[i];
}
}
numOfR = newNumOfR;
//test
// for (int i = 0; i < numOfR; i++) {
// printf("%d\n", newR[i]);
// }
// 一个是满足条件的I的个数,一个是满足条件的I的索引
int qualifyI[numOfR];
int indexOfI[numOfR][100];
for (int i = 0; i < numOfR; i++) {
qualifyI[i] = 0;
}
int total = 0;
for (int i = 0; i < numOfR; i++) {
for (int j = 0; j < numOfI; j++) {
if (contains(I[j], newR[i])) {
// printf("find %d contains %d\n", I[j], newR[i]);
// int foundDuplicate = 0;
// for (int k = 0; k < qualifyI[i]; k++) {
// if (I[indexOfI[i][k]] == I[j]) {
// foundDuplicate = 1;
// break;
// }
// }
// if (!foundDuplicate) {
indexOfI[i][qualifyI[i]++] = j;
// }
}
}
if (qualifyI[i] != 0) {
total += 2 * qualifyI[i] + 2;
}
}
printf("%d ", total);
for (int i = 0; i < numOfR; i++) {
if (qualifyI[i] > 0) {
printf("%d ", newR[i]);
printf("%d ", qualifyI[i]);
for (int j = 0; j < qualifyI[i]; j++) {
printf("%d ", indexOfI[i][j]);
printf("%d ", I[indexOfI[i][j]]);
}
}
}
printf("\n");
return 0;
}20241031 18:53