简答题
偏难
#7214
电话号码 给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如: Emergency 911 Alice 97 625 999 B…
电话号码
给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。
时间限制:1000
内存限制:65536
输入
第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。
样例输入
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
样例输出
NO YES
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int t;
int n;
int FLAG; // FLAG=1代表互不构成后缀,FLAG=0代表摸一个单词构成后缀
struct Node {
struct Node *next[10]; // 定义一个指针数组next,里面的元素都是Node类型的指针
int is_Cover; // 定义这个节点的访问次数
int is_End; // 定义这个节点是否是一个电话号的最后一个字符
};
void Init(Node *a) // 初始化节点i
{
memset(a->next, 0, sizeof(a->next)); // next[0]~next[9]都是指针NULL
a->is_Cover = 0;
a->is_End = 0;
}
// 内存友好型函数:释放内存
void DELETE(Node *root) {
for (int i = 0; i < 10; i++) {
if (root->next[i]) {
DELETE(root->next[i]);
} // 递归法释放内存
}
free(root); // 递归到底层,root->next[0~9]都是NULL,直接释放root即可
}
void insert(Node *root, char *temp) {
Node *p = root;
int id; // 0~9
while (*temp) // 字符串指针未到底
{
id = *temp - '0';
if (p->next[id] == NULL) {
p->next[id] = (Node *)malloc(sizeof(Node)); // 先申请内存空间
Init(p->next[id]); // 再对这个节点进行初始化
}
p = p->next[id]; // 指针往下移动
if (p->is_End) {
FLAG = 0;
} // 这个点是其他电话号的最后一个数字,包含着其他单词的前缀
p->is_Cover++;
temp++; // 字符指针向下移动
}
if (p->is_Cover > 1) {
FLAG = 0;
} // 执行到这里说明temp字符串是其他长字符串的前缀,temp字符串较短
p->is_End = 1; // 设置字符串末尾标志
}
int main() {
char ss[15];
cin >> t;
while (t--) {
Node *root = (Node *)malloc(sizeof(Node));
Init(root);
FLAG = 1; // 没有特殊情况不构成后缀
cin >> n;
while (n--) {
scanf("%s", ss);
if (FLAG) {
insert(root, ss);
} // 前面都没有前缀的发生,可以继续插入
}
if (FLAG == 0) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
}
DELETE(root); // 释放内存
}
return 0;
}</pre>
这道题暂未补解析。