(hdu step 5.2.3)Phone List(在一堆号码中,判断是否有号码是其它
发布时间：2020-12-13 20:04:55 所属栏目：PHP教程 来源：网络整理
导读：题目: Phone List Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 235 Accepted Submission(s): 92 Problem Description Given a list of phone numbers,determine if it is consistent in the se
|
题目:
题目分析： 这道题，属于Trie的入门级别的题目。但是在这里先介绍1下不用Trie怎样解决这道题。在1堆号码中, 要判断1个号码是不是是其他号码的前缀。我们可以先对这对号码按字典序进行1下排序。然后顺次判断相邻两个号码中是不是有号码是其它号码的前缀便可。整体的时间复杂度要比暴力做法的O(n^2)要好很多。 这里还需要介绍1下的是strncmp这个函数。 strncmp(): 这个函数用来比较s1和s2字符串，这个函数将返回1个值， 它的符号与第1对不同的字符的比较结果相干。如果两个字符串相等的话，strncmp将返回0。如果s1是s2的1个子串的话，s1小于s2。另外还有，函数 int strncmp (const char *s1,const char *s2,size_t size) 此函数与strcmp极其类似。不同的地方是，strncmp函数是指定比较size个字符。也就是说，如果字符串s1与s2的前size个字符相同，函数返回值为0。 代码以下： /*
* c.cpp
*
* Created on: 2015年3月7日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10001;
char num_str[maxn][11];//用于存储号码字符串
/**
* 让号码字符串按字典序升序排列
*/
int cmp(const void* a,const void* b){
return strcmp((char*)a,(char*)b);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int i;
for(i = 0 ; i < n ; ++i){//顺次读入n个号码
scanf("%s",num_str[i]);
}
qsort(num_str,n,sizeof(num_str[0]),cmp);//将n个号码按字典序排列
bool flag = false;//用于标记是不是有号码是其他号码的前缀
for(i = 0 ; i < n⑴ ; ++i){//遍历所有的号码字符串
//如果有号码的前n个字符与其他号码的前n个字符是1样的.
if(strncmp(num_str[i],num_str[i+1],strlen(num_str[i] )) == 0){
flag = true;//.则表明该号码是另外1个号码的前缀
break;//跳出循环
}
}
if(flag == true){//如果由号码是其它号码的前缀
printf("NO
");//打印NO
}else{//如果没有号码是其它号码的前缀
printf("YES
");//打印YES
}
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |