HDU 1004(字典树，c++ map)

本文主要是介绍HDU 1004(字典树，c++ map)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出一个n与n个颜色，求出现次数最多的颜色。

 

暴力方法：

#include <stdio.h>
#include <string.h>
int main()
{
int n,i,max=1,count=0,flag,j;
while(1)
{
char a[1000][50];
max=1;
scanf("%d",&n);
if(n==0)
break;
getchar();
for(i=0;i<n;i++)
gets(a[i]);
if(n==1)
{
puts(a[0]);
continue;
}
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(strcmp(a[i],a[j])==0)
count++;
}
if(count>max)
{
max=count;
flag=i;
}
}
puts(a[flag]);
}
return 0;
}

c++ map的使用：

#include <cstdio>
#include <map>
#include <iostream>
#include <string>
using namespace std;
void main()
{
int N;
string ballon;
while (cin >> N, N)
{
map<string, int> m;
int n = N;
while (n--)
{
cin >> ballon;
++m[ballon];
}
map<string, int>::iterator p;
int max = 0;
string max_ballon;
for (p = m.begin(); p != m.end(); ++p)
{
if (p->second > max)
{
max = p->second;
max_ballon = p->first;
}
}
cout << max_ballon << endl;
}
}

字典树的使用：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;
struct Trie
{
int base;
Trie* next[26];
Trie() : base(-1) { memset(next, NULL, sizeof next); }
};
string color[1002];
int _count[1002];
int cnt;
void insert(Trie* root, string& line)
{
Trie* p = root;
int len = line.length(), n;
for (int i = 0; i < len; ++i)
{
n = line[i] - 'a';
if (p->next[n] == NULL)
p->next[n] = new Trie;
p = p->next[n];
}
if (p->base == -1)
{
p->base = cnt;
color[cnt++] = line;
}
++_count[p->base];
}
void freeTrie(Trie* root)
{
for (int i = 0; i < 26; ++i)
if (root->next[i])
freeTrie(root->next[i]);
delete root;
}
int main()
{
int n, i;
string line;
Trie* root;
while (cin >> n && n)
{
root = new Trie;
cnt = 0;
memset(_count, 0, sizeof _count);
for (i = 0; i < n; ++i)
{
cin >> line;
insert(root, line);
}
int _max = 0, base;
for (i = 0; i < cnt; ++i)
if (_count[i] > _max)
{
_max = _count[i];
base = i;
}
cout << color[base] << endl;
freeTrie(root);
}
}

这篇关于HDU 1004(字典树，c++ map)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---