题目: 信服君接受一项任务需要制作一个手机号码查询系统,输入连续的数字后,需要显示所有包含该连续数字的手机号。为了验证算法,信服君当前只需输出手机号的个数即可。
注:直接用数学的查找方式如果(phonenum [i] .find(test)!= string :: npos)会超时,只能AC80%,这里用空间替换时间效率AC了100%。的连续组合方式,从而节省了找到的时间。
#include<bits/stdc++.h> using namespace std; int main(){ int i,j,n,q; unordered_map<string,int>m;//用于记录连续数字出现的数字,key=连续数字,value=次数 cin>>n>>q;//n个手机号码,q个查询数字段 unordered_set<string>phone;//用set进行存储避免了号码的重复插入 string s; while(n--){ cin>>s; if(s.size()!=11)continue;//不是正确的电话号码则不必存储 phone.insert(s);//用set进行插入,避免号码的重复 } for(unordered_set<string>::iterator it=phone.begin();it!=phone.end();++it){ s=*it; unordered_set<string>c; for(i=0;i<11;++i){ string t; for(j=i;j<11;++j){ t+=s[j]; c.insert(t);//将一个手机号码所有的连续组合方式进行存储,用空间替换时间 } } for(auto p:c)m[p]++;//计数 } while(q--){ cin>>s;//输入连续数字段 cout<<m[s]<<endl;//输出他的次数 } return 0; }