📣 VIP通行证夏日特惠 限时立减$68
查看: 4714| 回复: 23
跳转到指定楼层
上一主题 下一主题
收起左侧

Longest words

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 love1point 于 2015-6-9 09:56 编辑

有人说下面这道google曾经考过,谁有比较好的解法不?

题目链接:http://www.lintcode.com/en/problem/longest-words/

补充:其实这题最关键的地方就是如何记入下最长单词的长度,避免出现遗漏相同长度的单词。昨晚问了大家这道题,好几个同学都给了我非常快且好的算法,再次感谢一亩三分地这个平台,能让我们的疑问得到解答。所以,只要我们互相提供信息,我们都能得到我们需要的。赞扬这种不仅从地里获得东西,还给予的网友!

[b]Easy
Longest Words[/b]


40%Accepted

Given a dictionary, find all of the longest words in the dictionary.


Have you met this question in a real interview?
Yes


Example

Given

{  "dog",  "google",  "facebook",  "internationalization",  "blabla"}

the longest words are(is) ["internationalization"].

Given

{  "like",  "love",  "hate",  "yes"}

the longest words are ["like", "love", "hate"].



class Solution {
    /**
     * @param dictionary: an array of strings
     * @return: an arraylist of strings
     */
    ArrayList<String> longestWords(String[] dictionary) {
        // write your code here
    }
};






点评

经过了stellari的点播,我的解法贴在了下面  发表于 2015-6-9 01:58

上一篇:LeetCode Solution
下一篇:求问大家找工作有没有值得推荐的辅导班
全局:
maintain一个这样的hashmap感觉是overkill啊 只问了最长的词的list,map里存的短词的entry都是浪费内存啊。太fancy的解法我想不出来,我感觉两次扫描,第一次扫描得出最长词的长度,第二次扫描添加最长词,这样不消耗额外内存。要非得一遍扫,可以ArrayList保存当前最长词序列 一旦发现更长的词就clear 然后添加更长词。

点评

能想到好的算法太重要啦  发表于 2015-6-9 09:50

评分

参与人数 1大米 +10 收起 理由
love1point + 10 回答的很好!

查看全部评分

回复

使用道具 举报

推荐
 楼主| love1point 2015-6-9 16:20:19 | 只看该作者
全局:
stellari 发表于 2015-6-9 15:46
如果这个题加一个follow up,变成:“找出所有具有某个特定前缀的单词中最长的那些”。例如:

字典为:{ ...

我第一反应,加两个判断,在上面那个双重循环的方法。第一个判断单词长度至少大于等于3,嵌在第一个if里加上第二个判断,用 dictionary[i].substring(0,3).equals("pre"). 用hashmap的方法就是在循环里加这两个判断。
  1. class Solution {
  2.     /**
  3.      * @param dictionary: an array of strings
  4.      * @return: an arraylist of strings
  5.      */
  6.     ArrayList<String> longestWords(String[] dictionary) {
  7.         // write your code here
  8.         ArrayList<String> result = new ArrayList<String>();
  9.         int max = 0;
  10.         for(int i = 0; i < dictionary.length; i++)
  11.         {  if(dictionary[i].length()>=3)
  12.          {  
  13.               if(dictionary[i].substring(0,3).equals("pre")){  max = Math.max(dictionary[i].length(), max);
  14.          }
  15.             
  16.         }
  17.         
  18.         for(String a : dictionary)
  19.         {
  20.             if(a.length() == max)
  21.             {
  22.                 result.add(a);
  23.             }
  24.         }
  25.         return result;
  26.     }
  27. };
复制代码



其他一样。不知觉得如何?
回复

使用道具 举报

推荐
 楼主| love1point 2015-6-9 01:55:03 | 只看该作者
全局:
献上我AC过的代码。

感觉google真的很爱考HashMap的题目。
  1. class Solution {
  2.     /**
  3.      * @param dictionary: an array of strings
  4.      * @return: an arraylist of strings
  5.      */
  6.     ArrayList<String> longestWords(String[] dictionary) {
  7.         // write your code here
  8.         ArrayList<String> result = new ArrayList<String>();
  9.         HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
  10.         
  11.         int max = 0;
  12.         for(int i = 0; i < dictionary.length; i++)
  13.         {
  14.             if(map.containsKey(dictionary[i].length()))
  15.             {
  16.                 map.get(dictionary[i].length()).add(dictionary[i]);   
  17.             }
  18.             else
  19.             {
  20.                 ArrayList<String> arr = new ArrayList<String>();
  21.                 arr.add(dictionary[i]);
  22.                 map.put(dictionary[i].length(), arr);
  23.             }
  24.             max = Math.max(dictionary[i].length(), max);
  25.         }
  26.         return map.get(max);
  27.     }
  28. };
复制代码
回复

使用道具 举报

🔗
cloudending 2015-6-8 21:51:15 | 只看该作者
全局:
遍历一遍,用一个map存下来,key是单词的长度,value是vector<string>
  1. class Solution
  2. {
  3. public:
  4.     vector<string> longestWords(vector<string>& dict)
  5.     {
  6.         map<size_t,vector<string> > m;
  7.         size_t maxLength = 0;
  8.         for(auto it = dict.begin(); it != dict.end(); ++it)
  9.         {
  10.             maxLength = std::max(it->length(), maxLength);
  11.             m[it->length()].push_back(*it);
  12.         }

  13.         return m[maxLength];
  14.     }
  15. };
复制代码

评分

参与人数 1大米 +10 收起 理由
love1point + 10 谢谢你的介绍!

查看全部评分

回复

使用道具 举报

🔗
 楼主| love1point 2015-6-8 22:13:11 | 只看该作者
全局:
cloudending 发表于 2015-6-8 21:51
遍历一遍,用一个map存下来,key是单词的长度,value是vector

你能把算法思想写一下不?谢谢。C++我不怎么熟。你用java也行。

这题如果有长度一样的单词这种情况我好像卡住了
回复

使用道具 举报

🔗
 楼主| love1point 2015-6-8 22:49:26 | 只看该作者
全局:
本帖最后由 love1point 于 2015-6-8 22:50 编辑
cloudending 发表于 2015-6-8 21:51
遍历一遍,用一个map存下来,key是单词的长度,value是vector

我的解法还是只能输出一个,无法输出相同长度的单词。
比如 map 后(3,“abc”), (3, "def")
还是只能输出一个

[i][i]
  1. class Solution {
  2.     /**
  3.      * @param dictionary: an array of strings
  4.      * @return: an arraylist of strings
  5.      */
  6.     ArrayList<String> longestWords(String[] dictionary) {
  7.         // write your code here
  8.         HashMap<Integer, String> map = new HashMap<Integer, String>();
  9.         ArrayList<String> result = new ArrayList<String>();
  10.         
  11.         int max = 0;
  12.         
  13.         for(int i = 0; i < dictionary.length; i++)
  14.         {
  15.             max= Math.max(dictionary.length(), max);
  16.             map.put(dictionary.length(), dictionary);
  17.         }
  18.         
  19.         for(Integer a : map.keySet())
  20.         {
  21.             if(a == max)
  22.             {
  23.                 result.add(map.get(a));
  24.             }
  25.         }
  26.         return result;
  27.     }
  28. };
复制代码
[/i][/i]
回复

使用道具 举报

🔗
stellari 2015-6-9 00:21:13 | 只看该作者
全局:
love1point 发表于 2015-6-8 22:49
我的解法还是只能输出一个,无法输出相同长度的单词。
比如 map 后(3,“abc”), (3, "def")
还是只 ...

你需要维护一个
HashMap<Integer, ArrayList<String>>
来建立
“单词长度->所有符合该长度的单词的列表”
这样的映射。

比如词典中是{"a", "ad","to", "red","but", "car"};
那么你建立的Map就是
{{1: {"a"}}, {2: {"ad", "to"}}, {3: {"red", "but", "car}}}.

有了这样的一个Map你就可以直接从中取得结果了。

评分

参与人数 1大米 +20 收起 理由
love1point + 20 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
 楼主| love1point 2015-6-9 01:53:28 | 只看该作者
全局:
stellari 发表于 2015-6-9 00:21
你需要维护一个
HashMap
来建立

非常感谢。

经过你的点播,V 变成 ArrayList<String> 很好的解决了我的问题,再也不会漏了长度一样的字符串。
回复

使用道具 举报

🔗
cloudending 2015-6-9 09:10:08 | 只看该作者
全局:
love1point 发表于 2015-6-8 22:13
你能把算法思想写一下不?谢谢。C++我不怎么熟。你用java也行。

这题如果有长度一样的单词这种情况我 ...

嗯,楼上的一样,这里的vector是vector<string>,就相当于java的ArrayList<String>
回复

使用道具 举报

🔗
 楼主| love1point 2015-6-9 09:11:30 | 只看该作者
全局:
cloudending 发表于 2015-6-9 09:10
嗯,楼上的一样,这里的vector是vector,就相当于java的ArrayList

好的,非常感谢
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表