133. 最长单词 一次遍历+vector容器

给一个词典,找出其中所有最长的单词。 样例

在词典 { "dog", "google", "facebook", "internationalization", "blabla" } 中, 最长的单词集合为 ["internationalization"] 在词典 { "like", "love", "hate", "yes" } 中,最长的单词集合为 ["like", "love", "hate"]

如果只是要最长的一个单词,那么只需要一次遍历即可,这里是要求求出最长单词的集合,稍作改变即可。

一次遍历+vector容器

首先把第一个单词放入容器res,并把第一个单词的大小记作max_size,然后遍历,如果新来的单词的大小比max_size大,那么清空res,并把新单词放入,并且用当前单词的大小来更新max_size。如果新来的单词的大小和max_size想等,那么把当前单词放入即可,这样一遍遍历就可以达到目的,代码写起来也是非常简单:

 vector<string> longestWords(vector<string> &dictionary) 
     {
         vector<string> res;
         int max_size=dictionary[0].size();
         for(auto d:dictionary)
         {
             if(d.size()>max_size)  
             {
                 max_size=d.size();
                 res.clear();
                 res.push_back(d);
             }
             else if(d.size()==max_size)
             {
                 res.push_back(d);
             }
         }
         return res;
     }

我一开始写了一个麻烦的,主要是没想到用vector::clear(),但基本思路是一样的,就是写起来麻烦点,贴在下面,注释齐全:

 vector<string> longestWords(vector<string> &dictionary) 
    {
       vector<int> max_index;   //记录最大长度的索引
       vector<string> res;
       int max_size=0;    //记录当前最大值
       
       //这次遍历挑了大的出来,越大,排的越靠后,因为只有比当前的最大大,才能插入
       for(int i=0;i<dictionary.size();i++)   
       {
           if(dictionary[i].size()>=max_size)
           {
               max_index.push_back(i);
               cout<<*(max_index.end()-1)<<" ";
               max_size=dictionary[i].size();
           }  
           
       }
       
       //如果只有一个的话,肯定这个是最长的,而且应该是第一个
       if(max_index.size()==1)       
       {
           res.push_back(dictionary[max_index[0]]);
           return res;
       }
       else  
      
       //因为是需要一个集合,所以从后往前把长度相同的都插入到res中
       max_size=0;   //记得清零,最后一个一定放进去
       {
           for(auto end=max_index.end()-1;end>=max_index.begin();end--)
           {
               if(dictionary[*end].size()>=max_size)
               {
                   max_size=dictionary[*end].size();
                   res.push_back(dictionary[*end]);
               
               }
               else break;
    
           }
       }
       return res;
        // write your code here
    }
···

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏kalifaの日々

C++构造无向图&求最短路径源码

用vector<edge> es[MAX]表示点,每个点队列里放着点的相邻边和到边的距离。 以下源码经过测试可运行 #include <iostream> #i...

3105
来自专栏计算机视觉与深度学习基础

Leetcode 164 Maximum Gap 桶排序好题

Given an unsorted array, find the maximum difference between the successive ele...

2095
来自专栏数据结构与算法

洛谷P3382 【模板】三分法(三分)

1120
来自专栏数据结构与算法

P1182 数列分段Section II

题目描述 对于给定的一个长度为N的正整数数列A[i],现要将其分成M(M≤N)段,并要求每段连续,且每段和的最大值最小。 关于最大值最小: 例如一数列4 2 4...

2688
来自专栏kalifaの日々

POJ2431-最优队列(最小堆)解法

这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>...

3457
来自专栏五分钟学算法

每天一算:Minimum Size Subarray Sum

leetcode上第209号问题:Minimum Size Subarray Sum

651
来自专栏游戏开发那些事

三十分钟掌握STL

这是本小人书。原名是《using stl》,不知道是谁写的。不过我倒觉得很有趣,所以化了两个晚上把它翻译出来。我没有对翻译出来的内容校验过。如果你没法在三十分钟...

1104
来自专栏calmound

uva Excuses, Excuses!

题意:给几个单词,在给几个句子,输出包含最多单词的那个句子,大小写不分,末尾空行 分析:这道题能A,还是挺开心的,但不说多难,而是又学会了个函数,又知道了个细节...

3675
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1941
来自专栏计算机视觉与深度学习基础

Leetcode 29 Divide Two Integers 位操作的巧妙运用

Divide two integers without using multiplication, division and mod operator. I...

2366

扫码关注云+社区