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

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

阅读量：4557 次

发布时间：2019-06-08

本文共 1978 字，大约阅读时间需要 6 分钟。

Let the Balloon Rise HDU - 1004

题目链接：

题目：

题目描述

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

Input

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

N=0代表输入结束。

Output

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

Sample Input

5greenredblueredred3pinkorangepink0

Sample Output

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

//// Created by hanyu on 2019/4/9.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  typedef long long LL;using namespace std;const int MAX=1e5+7;int main(){ int n; while(cin>>n&&n) { map
                  
                   sh; string s; for(int i=0;i
                   
                    >s; sh[s]++; } map
                    
                     ::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<
                     
                      first<

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

// // Created by HJYL on 2019/8/19.//#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  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
                  
                   sum) { sum=a; pos=i; } } printf("%s\n",str[pos]); } return 0;}