Let the Balloon Rise HDU - 1004 (字典树和map两种写法）

野性酷女 2023-08-17 15:41 117阅读 0赞

## Let the Balloon Rise HDU - 1004  ##

题目链接：

[https://vjudge.net/problem/HDU-1004][https_vjudge.net_problem_HDU-1004]

题目：

题目描述

有多种颜色的气球，统计它们的个数，并找出数量最多的那种颜色。

Input

有多组样例输入。每组样例第一行输入一个整数N (0 < N <= 1000) -- 代表一共有N个气球。接下来N行每行输入一个不多于15个字母的字符串代表颜色。  
  
  
  
N=0代表输入结束。

Output

每组样例数据输出数量最多的那种颜色的气球。（保证输出唯一）

Sample Input

5
    green
    red
    blue
    red
    red
    3
    pink
    orange
    pink
    0

Sample Output

red
    pink
    思路：比较简单的是map写法，记录字符串对应的个数，而且还是自动排序的：

//
    // Created by hanyu on 2019/4/9.
    //
    #include <iostream>
    #include <memory.h>
    #include <string>
    #include <istream>
    #include <sstream>
    #include <vector>
    #include <stack>
    #include <algorithm>
    #include <map>
    #include <queue>
    #include <math.h>
    #include <cstdio>
    typedef long long LL;
    using namespace std;
    const int MAX=1e5+7;
    int main()
    {
    
        int n;
        while(cin>>n&&n)
        {
            map<string,int>sh;
            string s;
            for(int i=0;i<n;i++)
            {   cin>>s;
                sh[s]++;
            }
            map<string,int>::iterator it;
            int sum=0;
            for(it=sh.begin();it!=sh.end();it++)
            {
                if(it->second>sum)
                    sum=it->second;
            }
            for(it=sh.begin();it!=sh.end();it++)
            {
                if(it->second==sum)
                {
                    cout<<it->first<<endl;
                    break;
                }
            }
    
        }
    
        return 0;
    }

**另一种写法是我今天写的字典树的写法，也比较方便**

// 
    // Created by HJYL on 2019/8/19.
    //
    #include <iostream>
    #include <vector>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <set>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    struct trie{
        trie* next[26];
        int sum;
        trie(){
            for(int i=0;i<26;i++)
                next[i]=NULL;
            sum=0;
        }
    }root;
    void insert(char* s)
    {
        trie* p=&root;
        for(int i=0;s[i];i++)
        {
            if(p->next[s[i]-'a']==NULL)
            {
                p->next[s[i]-'a']=new trie;
               // p->sum=1;
               //p=p->next[s[i]-'a'];
            }
            p=p->next[s[i]-'a'];
            p->sum++;
        }
    }
    int find(char* s)
    {
        trie* p=&root;
        for(int i=0;s[i];i++)
        {
            if(p->next[s[i]-'a']==NULL)
                return 0;
            else
                p=p->next[s[i]-'a'];
        }
        return p->sum;
    }
    int main()
    {
        //freopen("C:\\Users\\asus567767\\CLionProjects\\untitled\\text","r",stdin);
    
        int n,m;
        char str[maxn][20];
        while(~scanf("%d",&n)&&n)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%s",str[i]);
                insert(str[i]);
            }
            int a,pos=0,sum=0;
            for(int i=0;i<n;i++)
            {
                a=find(str[i]);
                if(a>sum)
                {
                    sum=a;
                    pos=i;
                }
            }
            printf("%s\n",str[pos]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11380738.html

[https_vjudge.net_problem_HDU-1004]: https://vjudge.net/problem/HDU-1004