NYOJ 题目290 动物统计加强版

动物统计加强版

时间限制:3000 ms  |  内存限制:150000 KB
难度:4
描述
在美丽大兴安岭原始森林中存在数量繁多的物种,在勘察员带来的各种动物资料中有未统计数量的原始动物的名单。科学家想判断这片森林中哪种动物的数量最多,但是由于数据太过庞大,科学家终于忍受不了,想请聪明如你的ACMer来帮忙。
输入
第一行输入动物名字的数量N(1<= N <= 4000000),接下来的N行输入N个字符串表示动物的名字(字符串的长度不超过10,字符串全为小写字母,并且只有一组测试数据)。
输出
输出这些动物中最多的动物的名字与数量,并用空格隔开(数据保证最多的动物不会出现两种以上)。
样例输入
10
boar
pig
sheep
gazelle
sheep
sheep
alpaca
alpaca
marmot
mole
样例输出
sheep 3

 

 

字典树的应用

字典树:是一种用于快速检索的多叉树结构。字典树把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构;一棵m度的字典树树或者为空,或者由m棵m度的Trie树构成。
特点:
利用串的公共前缀->节约内存
结点包含任何字母
其余结点仅包含一个字母(非元素)
每个结点的子节点包含字母不同
 
字典树的查找(最主要的操作)
(1)在trie树上进行检索总是始于根结点
(2)取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索。
(3)在某个结点处,关相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) ...
键词的所有字母已被取出,则读取附在该结点上的信,即完成查找。
 
Trie的数据结构定义
struct dictree  
{  
    dictree *child[26];  
    int n;   //根据需要变化
};  
dictree *root;

 

特点:数据量大
主要任务:查找单词
解决方法:字典树
字典树结构(除指针):单词信息(英文)  

 

HDOJ-1075 What Are You Talking About
HDOJ-1251 统计难题
HDOJ-1298 T9
HDOJ-1800   Flying to the Mars
ZOJ-1109     Language of FatMouse

 

第一步:1.建立字典树,

 

第一次思想(错误):

从第一层向下统计,每次都找到每层次数最多的(这里错误!!)

如测试数据:

5

abc

ade

afr

bb

bb

 

 错误代码:

 
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;

typedef struct dictree
{
	dictree * child[26];
	int  cnt;
}dictree;

void find(dictree * root)
{	
	int i,j;
	int flag = 1;
	for(i=0;i<26;i++) if(root->child[i]) flag = 0;
	
	if(flag){
		printf(" %d\n",root->cnt);
		return;	
	} 
	
	
	dictree *p;
	dictree *q;
	q = root;
	int index;
	int max = 0;
	for(i=0;i<26;i++)//寻找该层次数最大的然后向下查找,!!!这里错误 r如: abc acd aef bb bb 则先从a向下找了,错误!!!!
	{
		p=q->child[i];
		if(p)
		{
			if(max<p->cnt)
			{
				max=p->cnt;
				index = i;
			} 
		}
		
			
	}
	p = q->child[index];
	if(p)
	{
		printf("%c",index+'a');
		find(p);
	}
}
void insert(dictree * &root,char s[])//建立字典树
{
	int j,i;
	dictree *p;
	dictree *q;
	q = root;
	for(i=0;i<strlen(s);i++)
	{
		if(q->child[s[i]-'a'])
		{
			
			q = q->child[s[i]-'a'];
			q->cnt++;
		}
		else
		{
			p = (dictree * )malloc(sizeof(dictree));//分配p 
			p->cnt = 1;  
			for(j=0;j<26;j++)	p->child[j] = NULL;
			
			q->child[s[i]-'a'] = p;
			q = p;			
		}
	}
}

int main()
{
	int i;
	dictree * root;
	root=(dictree *)malloc(sizeof(dictree));
	for(i=0;i<26;i++)	root->child[i] = NULL;
		
	int n;
	char s[11];
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",s);
		insert(root,s);
	}
	find(root);
 	return 0;
}
        


 

第二次:

统计每个单词最后一个字母的出现次数,找最多的,但是找的过程中错误

建树过程中只统计最后一个单词出现次数,不能每个字母都统计次数

如:

5

abcde

abcde

abcde

ab

ab

此时b是5词,但ab不是最多的,所以会出错。。。!!!!

 
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;


typedef struct dictree
{
	dictree * child[26];
	int  cnt;
}dictree;

char str[12];
int num;

void insert(dictree * &root,char s[])
{

	int j,i;
	dictree *p;
	dictree *q;
	q = root;
	for(i=0;i<strlen(s);i++)
	{
		if(q->child[s[i]-'a'])
		{
			
			q = q->child[s[i]-'a'];
			q->cnt++;//这里错误,应该放到外面++
		}
		else
		{
			p = (dictree * )malloc(sizeof(dictree));//分配p 
			p->cnt = 1;  
			for(j=0;j<26;j++)	p->child[j] = NULL;
			
			q->child[s[i]-'a'] = p;
			q = p;			
		}
	}
	if(q->cnt>num) {//单词结束后,看最后一个字母出现次数
		num = q->cnt;
		strcpy(str,s);	
	}

}

int main()
{
	int i;
	dictree * root;
	root=(dictree *)malloc(sizeof(dictree));
	for(i=0;i<26;i++)	root->child[i] = NULL;
		
	int n;
	char s[12];
	scanf("%d",&n);
	num=0;
	while(n--)
	{
		scanf("%s",s);
	//	puts(s);
		insert(root,s);
	}
	printf("%s %d\n",str,num);
 	return 0;
}        


 

最后AC代码:

将前面的都改进

 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;


typedef struct dictree
{
	dictree * child[26];
	int  cnt;
}dictree;

char str[11];
int num;

void insert(dictree * &root,char s[])
{

	int j,i;
	dictree *p;
	dictree *q;
	q = root;
	for(i=0;i<strlen(s);i++)
	{
		if(q->child[s[i]-'a'])
		{
			
			q = q->child[s[i]-'a'];	
		}
		else
		{
			p = (dictree * )malloc(sizeof(dictree));//分配p 
			p->cnt = 0;  
			for(j=0;j<26;j++)	p->child[j] = NULL;
			
			q->child[s[i]-'a'] = p;
			q = p;			
		}
	}
	q->cnt++;//这里放到外面,只统计最后一个字母出现次数
	if(q->cnt>num) {
		num = q->cnt;
		strcpy(str,s);	
	}

}

int main()
{
	int i;
	dictree * root;
	root=(dictree *)malloc(sizeof(dictree));
	for(i=0;i<26;i++)	root->child[i] = NULL;
	
	int n;
	char s[11];
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",s);
		insert(root,s);
	}
	printf("%s %d\n",str,num);
 	return 0;
}