[编程题]数据分类处理

╰半夏微凉° 2022-07-14 14:18 161阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

信息社会，有海量的数据需要分析处理，比如公安局分析身份证号码、QQ用户、手机号码、银行帐号等信息及活动记录。  
采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。

**输入描述：**

> 一组输入整数序列I和一组规则整数序列R，I和R序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为0~0xFFFFFFFF，序列个数不限

**输出描述：**

从R依次中取出R，对I进行处理，找到满足条件的I<j>： 
 I<j>整数对应的数字需要连续包含R对应的数字。比如R为23，I<j>为231，那么I<j>包含了R，条件满足 。 
 按R从小到大的顺序:
 (1)先输出R； 
 (2)再输出满足条件的I<j>的个数； 
 (3)然后输出满足条件的I<j>在I序列中的位置索引(从0开始)； 
 (4)最后再输出I<j>。 
 附加条件： 
 (1)R需要从小到大排序。相同的R只需要输出索引小的以及满足条件的I<j>，索引大的需要过滤掉 
 (2)如果没有满足条件的I<j>，对应的R不用输出 
 (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为0，但没有满足条件的I<j>，不输出0，而下一个R是3
 6--- 存在6个包含3的I<j> 
 0--- 123所在的原序号为0 
 123--- 123包含3，满足条件

**输入例子：**

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数都需要输出包含R数的个数和对应的索引和I，说明对于每一个R都需要保存它查找的结果，为了避免构造过多的数组，可以就采用一个数组来记录所有R数的结果，不过不同R数的结果需要用标记区分开。可以采用一个数组记录索引位置，另一个数组记录对应的I，一个R的所有索引和I都找到后在索引数组和I数组后都增加一个标记表明一个R数结果的结束，然后再用一个数组来记录一个R数一共找到多少个索引和I对，然后根据这些存储的结果计算出输出的总共有多少个整数。另外的一个思路是先把R排序和去重，然后再去考虑。

**解题方式1：**

#include <iostream>
 #include <string>
 #include <vector>
 #include <iterator>
 #include <algorithm>
 using namespace std;
 
 bool biggerth(string s1, string s2)
 {
 int a = atoi(s1.c_str());
 int b = atoi(s2.c_str());
 return a < b;
 }
 int main()
 {
 int i, r;
 while (cin >> i)
 {
 vector<string> ivect;
 string s;
 while (i--)
 {
 cin >> s;
 ivect.push_back(s);
 }
 cin >> r;
 vector<string> rvect;
 while (r--)
 {
 cin >> s;
 rvect.push_back(s);
 }
 sort(rvect.begin(), rvect.end(), biggerth);
 string pre = rvect[0];
 vector<string> res1;
 vector<int> res2;
 vector<string> ires;
 vector<int> nres;
 for (vector<string>::iterator it = rvect.begin(); it != rvect.end(); ++it)
 {
 int beg1 = res1.size();
 if (it != rvect.begin() && *it == pre)
 {
 continue;
 }
 for (vector<string>::iterator iter = ivect.begin(); iter != ivect.end(); ++iter)
 {
 int itemp = (*iter).find(*it);
 if (itemp != string::npos)
 {
 res1.push_back(*iter);
 res2.push_back(iter - ivect.begin());
 }
 }
 if (res1.size() != beg1)
 {
 ires.push_back(*it);
 nres.push_back(res1.size() - beg1);
 res1.push_back(" ");
 res2.push_back(-1);
 }
 pre = *it;
 }
 cout << ires.size() + res1.size() + res2.size() - nres.size() << " ";
 vector<int>::iterator res2it = res2.begin();
 vector<string>::iterator res1it = res1.begin();
 vector<int>::iterator nit = nres.begin();
 for(vector<string>::iterator it = ires.begin(); it != ires.end(); ++it)
 {
 cout << *it << " " << *nit;
 while (*res2it != -1)
 {
 cout << " " << *res2it << " " << *res1it;
 res2it++;
 res1it++;
 }
 res2it++;
 res1it++;
 nit++;
 if (res2it != res2.end())
 cout << " ";
 }
 cout << endl;
 }
 return 0;
 }

**解题方式2：**

先排序和去重，再做处理。

#include<iostream>
 #include<vector>
 #include<algorithm>
 #include<string>
 using namespace std;
 bool match(int m,int n)
 {
 string str1=to_string(m);
 string str2=to_string(n);
 int pos=str2.find(str1);
 if(pos!=-1)
 return true;
 else
 return false;
 }
 int main()
 {
 int m,n;
 while(cin>>m)
 {
 vector<int> I;
 vector<int> R;
 for(int i=0;i<m;i++)
 {
 int temp;
 cin>>temp;
 I.push_back(temp); 
 }
 cin>>n;
 for(int i=0;i<n;i++)
 {
 int temp;
 cin>>temp;
 R.push_back(temp); 
 }
 sort(R.begin(),R.end());//排序
 R.erase(unique(R.begin(), R.end()), R.end());//去重
 
 vector<int> index;
 vector<int> value;
 vector<int> cnt;
 vector<int> index1;
 for(int i=0;i<R.size();i++)
 {
 int cnt1=0;//每个R[i]在I中存在的个数
 for(int pos=0;pos<I.size();pos++)//遍历I
 { 
 if(match(R[i],I[pos]))//如果R[i]在I中
 {
 cnt1++;//计数++
 index.push_back(pos);//把相应位置压入index
 value.push_back(I[pos]);//把在I中相应位置的值压入value
 }
 }
 if(cnt1!=0)//判断每个R[i]在I中的个数是否为0
 {
 cnt.push_back(cnt1);//把R[i]在I中对应找到的个数压入cnt
 index1.push_back(i);//把R中每个位置压入index1
 } 
 } 
 int j=0;
 cout<<2*index.size()+index1.size()+cnt.size()<<' ';//2*index.size()是一个位置+位置的值
 for(int i=0;i<cnt.size();i++)
 {
 cout<<R[index1[i]]<<' '<<cnt[i]<<' '; //把R中相应的值和在I中找到的个数输出 
 while(cnt[i]-->0)//循环输出R中R[i]在I中的位置和值
 {
 cout<<index[j]<<' '<<value[j];
 if(i==cnt.size()-1&&cnt[i]==0)
 {
 cout<<endl;
 } 
 else
 {
 cout<<' ';
 } 
 j++;
 }
 }
 }
 return 0;
 }