http://www.lintcode.com/en/problem/longest-words/
朋友推荐的网站,但是,只支持 C++,JAVA,PYTHON2/3,因为是刚入门,所以,找了一题应该最简单的。
然而,楼主用的 php,其他不会,所以,自己在本地写了一手。
此题给了提示:
遍历两次的办法很容易想到,如果只遍历一次你有没有什么好办法?
但是,经我一想哪里需要两次循环。用我大 php 一次循环加个排序不就好了吗。 原数据:
Array ( [0] => dddd [1] => a [2] => eeeee [3] => ccc [4] => bb ) 最大数:eeeee
渣代码:
<?php $a = [ 'dddd', 'a', 'eeeee', 'ccc', 'bb', ]; $arr = []; foreach ($a as $k => $v) { $arr[strlen($v)] = $v; } echo '<pre>'; print_r($a); krsort($arr); print_r('最大数:' . current($arr));
一直听闻,php 对于数组的处理比其他语言要厉害。难道,果真如此,其他语言,对于这题有啥不同的解法,请赐教!
![]() | 1 LokiSharp 2018-03-22 13:49:50 +08:00 Win7 + Chrome, 代码输入界面没法 Backspace |
3 jasontse 2018-03-22 13:58:26 +08:00 via iPad 排序不算循环? |
![]() | 4 lhx2008 2018-03-22 13:59:23 +08:00 via Android 瞎搞。。还调排序,nlogn 了解一下 |
![]() | 5 lizhenda 2018-03-22 14:02:08 +08:00 你调用系统函数算啥 |
![]() | 6 lhx2008 2018-03-22 14:02:21 +08:00 via Android php 要调排序也是用 uasort 啊,哈哈 |
![]() | 8 nbndco 2018-03-22 14:04:34 +08:00 via iPhone 感觉这个算法题解的有一些偏差…… |
9 Mervyn1205 2018-03-22 14:07:59 +08:00 数组是如下内容的时候,答案是错的 { "like", "love", "hate", "yes" } |
10 davinci 2018-03-22 14:12:03 +08:00 太慢了,而且没有考虑多个长度相同的字符串的情况。这题 o(n) 时间复杂度,o(n)空间复杂度,一次循环即可。 |
11 yuann72 2018-03-22 14:17:22 +08:00 这样行么? function longest_words (arr){ let maxLength = 0, output; arr.forEach((item) => { if (maxLength < item.length){ maxLength = item.length; output = []; output.push(item); }else if (maxLength === item.length){ output.push(item); } }); return output; } longest_words([ "dog", "google", "facebook", "internationalization", "blabla" ]) longest_words([ "like", "love", "hate", "yes" ]) |
12 g00001 2018-03-22 14:19:31 +08:00 一个循环是可以的, 数组排序也不是必须的,排序也是有代价的。 这个题应当是降低了难度,如果从文本中查找,实际上数组也可以省略掉,生成数组也是有消耗的。 lOngWord= function(s){ var r; for w in string.lines(s,"\s") if( #w > #r) r = w; return r; } var word = longWord("dddd a eeeee ccc bb"); 用 aardio 写的,不生成数组不排序,直接找到最长单词。 |
![]() | 13 LokiSharp 2018-03-22 14:21:53 +08:00 ![]() def longestWords(self, dictionary): # write your code here max_len = 0 list_ = [] for str_ in dictionary: str_len = len(str_) if str_len == max_len: list_.append(str_) elif str_len > max_len: max_len = str_len list_.clear() list_.append(str_) return list_ 随手写的= =略丑 |
![]() | 14 ChristopherWu 2018-03-22 14:29:30 +08:00 ![]() 根本不需要排序。。 遍历给出的 map 一遍,用 map[词的长度] 来存数组, 同时一个变量记录最长单词长度。 直接返回 map[最长单词长度]即可 On 复杂度,估计是最低了。 |
![]() | 15 HypoChen 2018-03-22 14:30:20 +08:00 python: words = [ "like", "love", "hate", "yes" ] print(list(filter(lambda x: len(x) == len(sorted(words, key=lambda x: len(x), reverse=True)[0]), words))) |
![]() | 18 ChristopherWu 2018-03-22 14:46:50 +08:00 `` `class Solution { public: /* * @param dictionary: an array of strings * @return: an arraylist of strings */ vector<string> longestWords(vector<string> &dictionary) { unordered_map<int, vector<string> > hash; int longest_len = 0; for(auto &it : dictionary) { int len = it.length(); if(len > longest_len) longest_len = len; if(hash.find(len) == hash.end()) { vector<string> v; v.push_back(it); hash[len] = v; }else { hash[len].push_back(it); } } return hash[longest_len]; } }; ``` 过了。。好久没有 写 C++,语法都七零八碎,查来查去。 |
19 lxy42 2018-03-22 14:48:40 +08:00 PHP 果然是最好的语言 ![]() |
![]() | 20 jmc891205 2018-03-22 14:48:48 +08:00 楼主是来黑 php 的吧 多大仇? |
![]() | 21 ChristopherWu 2018-03-22 14:50:54 +08:00 |
![]() | 23 rrfeng 2018-03-22 15:02:48 +08:00 via Android lintcode ?不是 leetcode 吗 |
![]() | 24 nbndco 2018-03-22 15:04:27 +08:00 @qxy 就算可以调用系统函数,你的答案本身还是错的(不看复杂度)。 算法题本质考察的是你对算法的理解,你调用系统函数可以,你确定你的解法是最优的么? 就这个问题而言,你确定排序里面没有遍历么? 按照你的思路还可以写一个没有遍历的解法,只要把算法写一个函数调用一下就变成一行解决一个算法题了。 |
25 g00001 2018-03-22 15:11:04 +08:00 @davinci 不排序,返回多个: lOngWords= function(s){ var m; for w in string.lines(s,"\s") { if( #w > #m[[1]] ) m = {w} ; elseif( #w == #m[[1]] ) table.push(m,w ); } return m; } var words = longWords("dddd a eeeee ffff ccc bb ccccc"); |
![]() | 26 whoami9894 2018-03-22 15:16:28 +08:00 via Android python 一次循环就 ok 了吧 |
![]() | 27 wsstest 2018-03-22 15:16:32 +08:00 睡眠排序一步搞定 ![]() |
29 resturlaub 2018-03-22 15:24:43 +08:00 arr.max_by(&:length) |
30 vincenttone 2018-03-22 15:31:58 +08:00 表示是来看热闹的 |
![]() | 31 misaka19000 2018-03-22 15:38:54 +08:00 ![]() 怎么 V 站最近开贴黑 PHP 的人越来越多了 |
![]() | 32 tommyZZM 2018-03-22 15:42:58 +08:00 |
![]() | 33 araraloren 2018-03-22 15:52:26 +08:00 PHP stolen many ideas from Perl my @a = < dddd a eeeee 55555 ccc bb >; my $max = -1; say @a.classify({ $max = .chars if .chars > $max; .chars }){$max}; try it online: https://tio.run/#perl6 |
![]() | 34 htfy96 2018-03-22 15:56:31 +08:00 又黑 PHP ( |
![]() | 35 mengyaoss77 2018-03-22 16:04:33 +08:00 搞个链表, 遍历一遍原数组, 遇到相同大小的就加到链表后面, 遇到更大的就重建链表。 最后输出链表,成了! 一次遍历! |
37 qxy OP |
38 carlclone 2018-03-22 17:10:18 +08:00 别来丢人了真的..... |
![]() | 39 liuhuansir 2018-03-22 17:12:41 +08:00 学习算法最好用 C 语言 |
![]() | 40 solaro 2018-03-22 17:13:18 +08:00 go 的切片和 array 到底他妈的什么区别??看的我一脸懵逼 |
![]() | 41 joeke 2018-03-22 17:37:13 +08:00 go 了解一下 |
![]() | 42 CFMY 2018-03-22 18:03:31 +08:00 算法追求的是时间和空间的效率,不是代码好看简练哦 |
![]() | 43 doraemon1293 2018-03-22 18:33:15 +08:00 随手一写竟然 timecost 排第一。。。。 class Solution: """ @param: dictionary: an array of strings @return: an arraylist of strings """ def longestWords(self, dictionary): # write your code here ans=[] lOngest=0 for word in dictionary: if len(word)>longest: ans=[word] lOngest=len(word) elif len(word)==longest: ans.append(word) return ans |
![]() | 44 cuebyte 2018-03-22 19:05:52 +08:00 主你是不要程序了排序的度是 NlogN,你是免的? |
![]() | 45 cuebyte 2018-03-22 19:07:15 +08:00 ![]() 主你是真的一粉十黑 |
46 zifuir 2018-03-22 19:54:17 +08:00 via iPhone php 表示这锅他不背,太黑啦 |
![]() | 47 gbin 2018-03-22 20:04:30 +08:00 via Android 这叫算法,PHP 都写好了兄弟咱俩有得一拼,有兴趣加我微信一起学? |
![]() | 48 limbo0 2018-03-22 20:09:33 +08:00 确实是最好的语音 |
![]() | 49 cjyang1128 2018-03-22 20:23:07 +08:00 每过几天就能看到黑 PHP 新的黑法,真有意思 |
![]() | 50 misaka19000 2018-03-22 20:26:36 +08:00 好吧 感觉楼主是个萌新各位也别太严格啦 不过楼主还是多学门语言吧,只会 PHP 确实是会出现这样的问题 |
![]() | 51 gbin 2018-03-22 21:00:09 +08:00 via Android 右转 /go/algorithm,每天一个算法题,有兴趣加我微信一起学习 cGdiMTYzNDc5NTI2Mg== ( base64 ) |
52 lihongjie0209 2018-03-22 21:23:11 +08:00 每过几天就能看到黑 PHP 新的黑法,真有意思 |
53 roychan 2018-03-22 21:55:37 +08:00 max_len = max([len(x) for x in dictionary]) return [x for x in dictionary if len(x) == max_len] ... |
![]() | 54 sagaxu 2018-03-22 22:27:40 +08:00 val s = listOf("dddd", "a", "eeeee", "ccc", "bb") s.maxBy { it.length } |
55 wlwood 2018-03-22 23:04:11 +08:00 via Android 算法怎么能分语言呢?只要是图灵完备的语言,都可以图灵等价。这个语言假如说能做出复杂度为 o(n),那么其他语言也肯定能做到 o(n)。 Lz 难道又是想来让论坛沸腾起来的么? |
![]() | 56 mulog 2018-03-22 23:28:42 +08:00 不看楼主发帖记录我还真以为是来黑的。。 不知道说啥好。。。 |
![]() | 57 HanSonJ 2018-03-22 23:48:29 +08:00 求你们了,别再来黑 PHP 了 ![]() |
58 ImJoeHs 2018-03-22 23:59:42 +08:00 你这跟那些‘一行写完 xxx ’有啥区别。 ["like", "love", "hate", "yes"].reduce((p, c) => p.length === 0 || p[0].length < c.length ? [c] : p[0].length === c.length ? [...p, c] : p, []) |
![]() | 59 icenine 2018-03-23 00:21:28 +08:00 系统函数排序实现是扔鞋的吗? |
![]() | 60 popbones 2018-03-23 06:06:29 +08:00 via iPhone 这就是为什么大家都说“ PHP 是最好的语言” |
![]() | 61 20015jjw 2018-03-23 06:42:25 +08:00 via Android …可爱如楼主 |
62 873681136 2018-03-23 07:39:36 +08:00 via iPhone … |
![]() | 63 xsdhy 2018-03-23 08:05:45 +08:00 via Android 每过几天就能看到黑 PHP 新的黑法,真有意思 |
64 polymerdg 2018-03-23 08:52:59 +08:00 你那复杂了 <?php $a = ['dddd','a','eeeee','ccc','bb']; $len = 0; $num = 0; foreach ($a as $k => $v) { if (strlen($v) > $len) $num = $k; } echo $a[$num]; |
65 yuqaf 2018-03-23 08:58:16 +08:00 @doraemon1293 他那个时间统计不靠谱。。一样的代码跑两次时间都不一样 |
![]() | 66 xAx 2018-03-23 08:59:09 +08:00 ![]() PHP 是最好的语言.....为什么会有人以为这句话是褒义? |
67 polymerdg 2018-03-23 08:59:34 +08:00 $a = ['dddd','a','eeeee','ccc','bb']; $len = 0; $num = 0; foreach ($a as $k => $v) { if (strlen($v) > $len) { $len = strlen($v); $num = $k; } } echo $a[$num]; 修正一下 |
![]() | 68 Clarencep 2018-03-23 09:00:09 +08:00 楼上各位,包括 LZ,请注意审题: “ Given a dictionary, find all of the longest words in the dictionary.” “ the longest words ” “ words ” "s" Example 里面返回的也都是数组好不好。你们一个个就返回一个字符串,使用啥算法也都铁定挂了。 |
69 vexjoe 2018-03-23 09:17:00 +08:00 标题中就有错别字,这种动态语言可能不适合你。 |
![]() | 70 wizardoz 2018-03-23 09:25:43 +08:00 php 果然是最好的语言,受教了! |
![]() | 71 laoyuan 2018-03-23 09:34:02 +08:00 今年以来 V2 黑 PHP 最狠的一次 |
![]() | 72 wupher 2018-03-23 09:37:11 +08:00 看见标题我就笑了 |
![]() | 73 jokerjoker 2018-03-23 09:42:18 +08:00 C#了解一下: var lOngest= array.Where(x=>x.Length==array.Max(y => y.Length)); |
![]() | 74 blaxmirror 2018-03-23 10:15:20 +08:00 算法的问题就不说了。 LZ 你只会 PHP,然后一番操作之后发现 PHP 是最好的语言。 逻辑在哪里? |
75 qxy OP @blaxmirror 因为,略看一些其他语言对于数组的操作。感觉,php 是最方便的 |
76 quericy 2018-03-23 10:28:18 +08:00 14L 正解。。 |
77 quericy 2018-03-23 10:31:18 +08:00 //$a = ['dddd','a','eeeee','ccc','bb']; $a = ['like', 'love', 'hate', 'yes']; $maxLen = 0; $res = []; foreach ($a as $k => $v) { $len = strlen($v); if ($len >= $maxLen) { $maxLen = $len; $res[$len][] = $v; } } print_r($res[$maxLen]); |
![]() | 78 wwqgtxx 2018-03-23 10:38:22 +08:00 萌新在 V 站讨论算法,感觉是个作死的行为 |
![]() | 79 skadi 2018-03-23 10:42:59 +08:00 刚打算入门学习算法,遇到一题发现 PHP 果然是最好的 "语音" |
![]() | 80 ftdejo 2018-03-23 10:46:48 +08:00 建议去刷 leetcode以及楼主黑的漂亮! |
![]() | 81 kdwycz 2018-03-23 10:54:45 +08:00 LZ 真是一粉顶十黑 |
![]() | 82 ftdejo 2018-03-23 10:56:57 +08:00 ``` vector<string> longestWords(vector<string> &dictionary) { // write your code here vector<string> ret{""}; for(auto & str: dictionary) { if(str.size() > ret.back().size()) { ret = vector<string>{str}; }else if(str.size() == ret.back().size()) { ret.emplace_back(str); } } return ret; } ``` 贴下自己代码,为什么两次运行时间不一样。。以前都在 leetcode 上刷的。。 |
![]() | 83 snw 2018-03-23 10:57:45 +08:00 不就是一个[]和一个 int 的事吗。 遇到长的♂就把之前[]里的全踢了放新的,int 记录下新长♂度; 遇到一样的♂就追加到[]里; 遇到短的♂直接无视。 |
![]() | 84 ftdejo 2018-03-23 11:01:01 +08:00 @ChristopherWu 这都要开个 hash 做直接遍历一遍不就行了吗 |
![]() | 85 sixand 2018-03-23 11:14:21 +08:00 为什么要这样? ???(黑人问号脸) max([len(item) for item in ['123','54245234523432','gewrgew','123432143','gfeg']]) |
![]() | 86 ChristopherWu 2018-03-23 11:30:57 +08:00 @ ftdejo 秀逗了。。用数组就可以了,可以不用 hash。 |
87 vagranth 2018-03-23 12:30:32 +08:00 当然是遍历一次,难道还要遍历两次? |
![]() | 88 prolic 2018-03-23 12:37:56 +08:00 via Android 从来不考虑时间复杂度,处理耗时长就推给 php 性能问题,php 还真是“最好的语言” |
90 iceheart 2018-03-23 13:04:09 +08:00 via Android var len = 0 var list = [] for ( x in array ){ if x.length > len { list = [] } if x.length == len { list.pushback(x) } } |
![]() | 91 psklf 2018-03-23 13:15:01 +08:00 lz 估计被吓坏 另外推荐 leetcode |
![]() | 92 vjnjc 2018-03-23 13:36:32 +08:00 7 楼差不多对了,还要注意最大单词可能不止一个 |
93 xpresslink 2018-03-23 13:43:29 +08:00 通过测试 http://www.lintcode.com/submission/13728720/ class Solution: """ @param: dictionary: an array of strings @return: an arraylist of strings """ def longestWords(self, dictionary): # write your code here from itertools import groupby return list(next(groupby(sorted(dictionary,key=len,reverse=True), key=len))[1]) 如果只是找出第一个最长的单词我大 py 有 Hack 的写法 >>> words = ["dog", "google", "facebook", "internationalization", "blabla"] >>> max(words, key=len) 'internationalization' |
![]() | 95 ichou 2018-03-23 21:17:47 +08:00 via iPhone @resturlaub 终于看到大 ruby 了 哈哈哈 |
![]() | 96 loadinger 2018-03-24 09:58:35 +08:00 数据结构白学了吗。。。。php 就是这样被搞臭的。 |