移动推出的校内网短号和亲情网短号非常方便，但在某款新手机里却出现了尴尬的bug。例如，当通讯录中包含如下号码时：
1.小王：600
2.小李：467654
3.小张：600010
输入600时，手机会直接自动打给了小王，因此永远没法打给小张。现在有很多部手机都有这种问题，<span>nowcoder</span>想要找到一个办法来判断每个号码簿里的号码是不是有这种冲突。
[编程题]冲突的电话号码
- 热度指数：810 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入有多组数据。
每组数据第一行是一个整数n，(1≤n≤10000)。
紧接着有n行电话号码，号码只有数字组成，长度不超过11位。
输出描述:
对应每组输入，有一行输出：如果电话簿中存在冲突的号码，就输出“Yes”；否则输出“No”。
示例1
输入
3 911 97625999 91125426 5 113 12340 123440 12345 98346
输出
Yes No
使用Tire树来解决，注释已经写的很详细了。原理是先建立所有号码对应的字典树，然后对每个号码进行遍历，如果该号码没有结束，但是当前数字对应的位有结束标记。
说明已经存在一个号码与当前号码有共同的前缀。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Node
{
char ch; // 字典节存储一个数字
bool isEnd = false; // 是否为号码的终点
Node * link[10] = {NULL}; // 指向下一节点的指针数组
};
// 创建字典树
Node * CreateTire(vector<string> & list)
{
Node * root = new Node; // 字典树根节点，不动
Node * prev, * cur; // prev前一节点，cur当前节点
for (string str : list) // 对每个string建立字典树中的路径
{
prev = root, cur = root; // 初始化
for (int i = 0; i < str.size(); ++i)
{ // 对string中每个char通过遍历方式查找存储的节点
if (prev->link[str[i] - '0'] == NULL)
{ // 对于当前数字，如果前一节点对应的指针为空
cur = new Node; // 那么就新建一个节点来存储这个数字
cur->ch = str[i]; // 然后将前一节点和当前节点连接起来
prev->link[str[i] - '0'] = cur;
prev = cur;
} // 否则说明已经有该路径，那么只要沿着路径进行遍历即可
else prev = prev->link[str[i] - '0'], cur = prev;
}
cur->isEnd = true; // 遍历结束时，将最后一位数字对应的标记置为“号码结束”
}
return root; // 返回字典根
}
// 判断字典树中是否存在共同前缀号码
// 原理是对每个号码进行遍历，如果该号码没有结束，但是当前数字对应的位有结束标记
// 说明已经存在一个号码与当前号码有共同的前缀
bool judgeCompete(Node * root, vector<string> & list)
{
Node * cur;
for (string str : list) // 对每个号码进行判断
{
cur = root; // 初始化
for (int i = 0; i < str.size();++i)
{ // 对每个数字进行判断
cur = cur->link[str[i] - '0']; // 不断向下遍历
// 存在前缀条件，返回“存在”
if (cur->isEnd && (i != str.size() - 1)) return true;
}
}
return false; // 所有号码遍历完毕，没有发现共同前缀，返回“不存在”
}
int main()
{
int n;
while (cin >> n && n)
{
vector<string> list(n);
for (int i = 0; i < n; ++i) cin >> list[i];
Node * root = CreateTire(list);
cout << (judgeCompete(root, list) ? "Yes" : "No") << endl;
}
return 0;
}
编辑于 2015-12-18 14:05:52
回复(0)
import java.util.*;
class TrieNode{
int num; //有多少单词通过这个节点，即由根至该节点组成的字符串模式出现的次数
TrieNode[] son; //所有的儿子节点
boolean isEnd; //是不是最后一个节点
boolean isleaf;
char val;//节点的值
int SIZE=10;
TrieNode(){
num=1;
son=new TrieNode[SIZE];
isEnd=false;
}
}
public class Main{
private static TrieNode root; //字典树的根
//建立字典树,在字典树中插入一个单词
public static void insert(String str){
if(str==null || str.length()==0)
return;
TrieNode node=root;
char[] letters=str.toCharArray();//将目标单词转换为字符数组
for(int i=0,len=str.length();i<len;i++){
int pos=letters[i]-'0';
//如果当前节点的儿子节点没有该字符，则构建一个TrieNode并复制该字符
if(node.son[pos]==null){
node.son[pos]=new TrieNode();
node.son[pos].val=letters[i];
}else{ //如果已经存在，则将由根至该儿子节点组成的字符串模式出现的次数+1
node.son[pos].num++;
}
node=node.son[pos];
}
node.isEnd=true;
}
public static int prefixNum(String str){
if(str==null || str.length()==0){
return 0;
}
TrieNode node=root;
char[] letters=str.toCharArray();
for(int i=0,len=str.length();i<len;i++){
int pos=letters[i]-'0';
if(node.son[pos]!=null)
node=node.son[pos];
else
return 0;
}
return node.num;
}
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
root = new TrieNode();
int n=scanner.nextInt();
int flag=0;
ArrayList<String> strList=new ArrayList<String>();
for(int i=0;i<n;i++){
String number=scanner.next();
insert(number);
strList.add(number);
}
for(int i=0;i<strList.size();i++){
if(prefixNum(strList.get(i))>1) flag=1;
}
if(flag==1)
System.out.println("Yes");
else
System.out.println("No");
}
}
}
发表于 2018-09-19 18:56:11
回复(0)
import java.util.Scanner;
/**
* 字典树 数据结构 参考 低调一点
* 注释说明
* @author Administrator
*
*/
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
String[] arr = new String[n];
for (int i = 0; i < arr.length; i ++ ) {
arr[i] = sc.next();
}
//上边一堆都是输入***************************************
//建立字典树
Node root = createTrie(arr);
boolean isFinded = false;
//遍历查找，是否有符合条件的字符串
for (String s:arr) {
if(check(root, s)) {
isFinded = true;
break;
}
}
if(isFinded) System.out.println("Yes");
else System.out.println("No");
}
sc.close();
}
//在创建好的字典数中查找 符合条件的字符串是否存在
public static boolean check(Node root, String s) {
Node p=root;
//遍历查找字符串到末尾，
for (int i = 0; i < s.length(); i ++ ) {
//用point代表这个字符所对应的子节点的坐标
int point = s.charAt(i) - '0';
//向下查找
p = p.next[point];
}
//判断，字符串的末尾的子节点是否为空，如果不空，就是存在，否则是不存在
for(int i=0;i<10;i++){
if(p.next[i]!=null) return true;
}
return false;
}
//构造字典树 TrieTree ，输入字符串数组，输出Trie树的头结点
public static Node createTrie(String[] arr) {
Node root = new Node('-');
Node p;
//遍历所有的字符串
for (int i = 0; i < arr.length; i ++ ) {
p = root;
String s = arr[i];
//遍历字符串的每一个字符
for (int j = 0; j < s.length(); j ++ ) {
//用point代表这个字符所对应的子节点的坐标
int point = s.charAt(j) - '0';//字符型转换为int类型，对应减去字符型的'0'
//判断这个点是否已经创建过，没有就创建，存在就num加一
if(p.next[point] == null) {
p.next[point] = new Node(s.charAt(j));
}
else {
p.next[point].num ++ ;
}
//流动指针指向刚刚创建好的子节点
p = p.next[point];
}
}
//返回创建好的Trie树的根节点
return root;
}
//节点的构造类
//保存经过该节点的字符串的数量
int num = 1;
//子节点的集合，定义为Node类型
Node[] next = new Node[10];
// 含参构造器
public Node(char value) {
this.value = value;
}
}
}
/**
* 字典树 数据结构 参考 低调一点
* 注释说明
* @author Administrator
*
*/
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
String[] arr = new String[n];
for (int i = 0; i < arr.length; i ++ ) {
arr[i] = sc.next();
}
//上边一堆都是输入***************************************
//建立字典树
Node root = createTrie(arr);
boolean isFinded = false;
//遍历查找，是否有符合条件的字符串
for (String s:arr) {
if(check(root, s)) {
isFinded = true;
break;
}
}
if(isFinded) System.out.println("Yes");
else System.out.println("No");
}
sc.close();
}
//在创建好的字典数中查找 符合条件的字符串是否存在
public static boolean check(Node root, String s) {
Node p=root;
//遍历查找字符串到末尾，
for (int i = 0; i < s.length(); i ++ ) {
//用point代表这个字符所对应的子节点的坐标
int point = s.charAt(i) - '0';
//向下查找
p = p.next[point];
}
//判断，字符串的末尾的子节点是否为空，如果不空，就是存在，否则是不存在
for(int i=0;i<10;i++){
if(p.next[i]!=null) return true;
}
return false;
}
//构造字典树 TrieTree ，输入字符串数组，输出Trie树的头结点
public static Node createTrie(String[] arr) {
Node root = new Node('-');
Node p;
//遍历所有的字符串
for (int i = 0; i < arr.length; i ++ ) {
p = root;
String s = arr[i];
//遍历字符串的每一个字符
for (int j = 0; j < s.length(); j ++ ) {
//用point代表这个字符所对应的子节点的坐标
int point = s.charAt(j) - '0';//字符型转换为int类型，对应减去字符型的'0'
//判断这个点是否已经创建过，没有就创建，存在就num加一
if(p.next[point] == null) {
p.next[point] = new Node(s.charAt(j));
}
else {
p.next[point].num ++ ;
}
//流动指针指向刚刚创建好的子节点
p = p.next[point];
}
}
//返回创建好的Trie树的根节点
return root;
}
//节点的构造类
static class Node {
//字符串中的单个字符
char value;//保存经过该节点的字符串的数量
int num = 1;
//子节点的集合，定义为Node类型
Node[] next = new Node[10];
// 含参构造器
public Node(char value) {
this.value = value;
}
}
}
编辑于 2018-04-01 19:11:37
回复(0)
Trie树，注意标志节点是否为某个单词的终点。
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
using namespace std;
struct Trie
{
bool isEnd;
shared_ptr<Trie> next[10];
Trie()
{
fill(next, next + 10, nullptr);
isEnd = false;
}
};
int main(int argc, char** argv)
{
//freopen("in.txt", "r", stdin);
int n;
while (cin >> n && n > 0)
{
shared_ptr<Trie> root(new Trie);
string phone;
bool isConflict = false;
for (int i = 0; i < n; ++i)
{
cin >> phone;
if (isConflict) continue;
bool createNode = false;
auto p = root;
for (auto& i : phone)
{
if (!p->next[i - '0'])
{
p->next[i - '0'] = make_shared<Trie>();
createNode = true;
}
if (p->isEnd)
{
isConflict = true;
break;
}
p = p->next[i - '0'];
}
p->isEnd = true;
if (!createNode) isConflict = true;
}
if (isConflict) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
发表于 2017-07-11 21:48:00
回复(0)
写个归并，自定义比较大小逻辑，边排序边检查，遇到相等直接返回
// write your code here
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
while(in.hasNext()){
int n=in.nextInt();
String[] s=new String[n];
String[] t=new String[n];
for(int i=0;i<n;i++){
s[i]=in.next();
t[i]=s[i];
}
if(merge(s,t,0,n-1)) System.out.println("No");
else System.out.println("Yes");
}
in.close();
}
static boolean merge(String[] s,String[] t,int sta,int end){
if(sta==end) return true;
int mid=sta+end>>1;
boolean b=merge(t,s,sta,mid) && merge(t,s,mid+1,end);
if(!b) return b;
int i=sta,j=mid+1,k=sta;
while(i<=mid && j<=end){
int res=compare(t[i],t[j]);
if(res<0) s[k++]=t[j++];
else if(res>0) s[k++]=t[i++];
else return false;
}
while(i<=mid){
s[k++]=t[i++];
}
while(j<=end){
s[k++]=t[j++];
}
return true;
}
static int compare(String s1,String s2){
int len=s1.length();
if(s1.length()>s2.length()) len=s2.length();
for(int i=0;i<len;i++){
if(s1.charAt(i)==s2.charAt(i)) continue;
else return s1.charAt(i)-s2.charAt(i);
}
return 0;
}
}
发表于 2018-09-10 21:50:32
回复(0)
package com.yzh.xuexi;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner =new Scanner(System.in);
while(scanner.hasNext()){
int n=Integer.valueOf(scanner.nextLine());
String[] arr=new String[n];
for (int i = 0; i < arr.length; i++) {
arr[i]=scanner.nextLine();
}
System.out.println(conflictPhoneNumber(arr));
}
scanner.close();
}
private static String conflictPhoneNumber(String[] arr) {
Arrays.sort(arr);//利用Arrays内置sort()函数对字符串按默认规则从小到大排序（也可以自己实现快排、希尔排序、归并排序和堆排序等n㏒n复杂度排序方法降低整个算法的复杂度）
//字符串从小到大排序后，只有相邻的两个字符串可能存在第二个字符串以第一个字符串开头的关系
for(int i=1;i<arr.length ;i++){
if (arr[i].indexOf(arr[i-1])==0) {
return "YES";
}
}
return "NO";
}
}
编辑于 2018-08-15 22:40:21
回复(0)
尴尬，有些边界得考虑好，比如当n为1或者2的时候
// write your code here cpp
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
int main()
{
string s;
int length;
while (cin >> length)
{
if (length == 1)
{
cin>>s;
cout << "No" << endl;
continue;
}
set<string> data;
for (int i = 0; i < length; i++)
{
cin >> s;
data.insert(s);
}
bool sta = true;
set<string>::iterator it = data.begin();
string pre = *it, cur;
for (it++; it != data.end(); it++)
{
cur = *it;
if (cur.length() > pre.length())
{
string t;
for (int i = 0; i < pre.length(); i++)
t += cur[i];
if (t == pre)
{
sta = false;
break;
}
else
pre = cur;
}
else
pre = cur;
}
if (sta == false)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
发表于 2017-04-25 13:09:38
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
String[] arr = new String[n];
for (int i = 0; i < arr.length; i ++ ) {
arr[i] = sc.next();
}
Trie root = createTrie(arr);
boolean isFinded = false;
for (String s:arr) {
if(check(root, s)) {
isFinded = true;
break;
}
}
if(isFinded) System.out.println("Yes");
else System.out.println("No");
}
}
public static boolean check(Trie root, String s) {
for (int i = 0; i < s.length(); i ++ ) {
int position = s.charAt(i) - '0';
if(root.next[position] == null) break;
if(root.next[position].num == 1) return false;
root = root.next[position];
}
return true;
}
public static Trie createTrie(String[] arr) {
Trie root = new Trie('-');
Trie cur;
for (int i = 0; i < arr.length; i ++ ) {
cur = root;
String s = arr[i];
for (int j = 0; j < s.length(); j ++ ) {
int position = s.charAt(j) - '0';
if(cur.next[position] == null) cur.next[position] = new Trie(s.charAt(j));
else cur.next[position].num ++ ;
cur = cur.next[position];
}
}
return root;
}
static class Trie {
char value;
int num = 1;
Trie[] next = new Trie[10];
public Trie(char value) {
this.value = value;
}
}
}
发表于 2016-10-12 23:15:42
回复(0)
//土办法，最垃圾解法，也不知道系统为什么能接受，233333~~~
#include "iostream"
using namespace std;
int panduan(char *a,char *b){//功能：判断两串是否相互包含（仅需比对开头）
while((*a) && (*b)){
if(*(a)!=*(b)){
return 1;//一旦有不一样的，返回1，表示不包含
}
a++;
b++;
}
return 0;//直到有一个结束指向空，还没找到不一样的，返0表示包含
}
void func(int n){
int a;
char s[n][12];//每组号码当字符串处理，用二维数组存多组号码
for(int i=0;i<n;i++){
cin>>s[i];//输入号码。“s[i]”是字符串数组【名】
}
for(int x=0;x<n;x++){
for(int y=x+1;y<n;y++){
a=panduan(s[x],s[y]);//逐一两两比对
if(a==0){
cout<<"Yes"<<endl;
return;//一旦有包含的，输出yes，返回，结束
}
}
}
cout<<"No"<<endl;
return;
}
int main(void){
int n;
while(cin>>n){func(n);}//一定要用while(cin>>n)，否则不过 return 0;
}
编辑于 2015-09-20 21:06:21
回复(0)
问题信息
难度：
10条回答
4收藏
5971浏览
通过挑战的用户
查看代码-
2021-09-17 10:07:19
-
2020-05-01 01:45:43 -
2020-02-11 16:15:58 -
2019-10-25 11:42:29
-
2019-06-08 16:34:17
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
