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 30 天前
Win7 + Chrome, 代码输入界面没法 Backspace
|
3
jasontse 30 天前 via iPad
排序不算循环?
|
![]() |
4
lhx2008 30 天前 via Android
瞎搞。。还调排序,nlogn 了解一下
|
![]() |
5
lizhenda 30 天前
你调用系统函数算啥···
|
![]() |
6
lhx2008 30 天前 via Android
php 要调排序也是用 uasort 啊,哈哈
|
![]() |
7
zjsxwc 30 天前 ♥ 1
不用排序啊,直接贪心就行
``` $a = [ ]; $maxLen = -1; $result = null; foreach ($a as $ele) { if ($maxLen < strlen($ele)) { $maxLen = strlen($ele); $result = $ele; } } ``` |
8
nbndco 30 天前 via iPhone
感觉这个算法题解的有一些偏差……
|
9
Mervyn1205 30 天前
数组是如下内容的时候,答案是错的
{ "like", "love", "hate", "yes" } |
10
davinci 30 天前
太慢了,而且没有考虑多个长度相同的字符串的情况。这题 o(n) 时间复杂度,o(n)空间复杂度,一次循环即可。
|
11
yuann72 30 天前
这样行么?
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 30 天前
一个循环是可以的,
数组排序也不是必须的,排序也是有代价的。 这个题应当是降低了难度,如果从文本中查找,实际上数组也可以省略掉,生成数组也是有消耗的。 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 30 天前 ♥ 2
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 30 天前 ♥ 2
根本不需要排序。。
遍历给出的 map 一遍,用 map[词的长度] 来存数组, 同时一个变量记录最长单词长度。 直接返回 map[最长单词长度]即可 On 复杂度,估计是最低了。 |
![]() |
15
HypoChen 30 天前
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 30 天前
``
`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 30 天前
PHP 果然是最好的语言
![]() |
![]() |
20
jmc891205 30 天前
楼主是来黑 php 的吧 多大仇?
|
![]() |
23
rrfeng 30 天前 via Android
lintcode ?不是 leetcode 吗
|
24
nbndco 30 天前
@qxy
就算可以调用系统函数,你的答案本身还是错的(不看复杂度)。 算法题本质考察的是你对算法的理解,你调用系统函数可以,你确定你的解法是最优的么? 就这个问题而言,你确定排序里面没有遍历么? 按照你的思路还可以写一个没有遍历的解法,只要把算法写一个函数调用一下就变成一行解决一个算法题了。 |
25
g00001 30 天前
@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 30 天前 via Android
python 一次循环就 ok 了吧
|
![]() |
27
wsstest 30 天前
睡眠排序一步搞定
![]() |
29
resturlaub 30 天前
arr.max_by(&:length)
|
30
vincenttone 30 天前
表示是来看热闹的
|
![]() |
31
misaka19000 30 天前 ♥ 5
怎么 V 站最近开贴黑 PHP 的人越来越多了
|
![]() |
32
tommyZZM 30 天前
|
![]() |
33
araraloren 30 天前
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 30 天前
又黑 PHP (
|
![]() |
35
mengyaoss77 30 天前
搞个链表,
遍历一遍原数组, 遇到相同大小的就加到链表后面, 遇到更大的就重建链表。 最后输出链表,成了! 一次遍历! |
37
qxy 30 天前
|
38
carlclone 30 天前
别来丢人了真的.....
|
![]() |
39
liuhuansir 30 天前
学习算法最好用 C 语言
|
![]() |
40
solaro 30 天前
go 的切片和 array 到底他妈的什么区别??看的我一脸懵逼
|
![]() |
41
joeke 30 天前
go 了解一下
|
![]() |
42
CFMY 30 天前
算法追求的是时间和空间的效率,不是代码好看简练哦
|
43
doraemon1293 30 天前
随手一写竟然 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 30 天前
樓主你還是不要當程序員了⋯⋯排序的時間複雜度是 NlogN,你當是免費的?
|
45
cuebyte 30 天前 ♥ 1
樓主你這是真的一粉頂十黑
|
46
zifuir 30 天前 via iPhone
php 表示这锅他不背,太黑啦
|
![]() |
47
gbin 30 天前 via Android
🌚🌚这叫算法,PHP 都写好了兄弟咱俩有得一拼,有兴趣加我微信一起学?
|
![]() |
48
limbo0 30 天前
确实是最好的语音
|
![]() |
49
cjyang1128 30 天前
每过几天就能看到黑 PHP 新的黑法,真有意思
|
![]() |
50
misaka19000 30 天前
好吧 感觉楼主是个萌新各位也别太严格啦
不过楼主还是多学门语言吧,只会 PHP 确实是会出现这样的问题 |
![]() |
51
gbin 30 天前 via Android
右转 /go/algorithm,每天一个算法题,有兴趣加我微信一起学习 cGdiMTYzNDc5NTI2Mg== ( base64 )
|
52
lihongjie0209 30 天前
每过几天就能看到黑 PHP 新的黑法,真有意思
|
![]() |
53
roychan 30 天前
max_len = max([len(x) for x in dictionary])
return [x for x in dictionary if len(x) == max_len] ... |
![]() |
54
sagaxu 30 天前
val s = listOf("dddd", "a", "eeeee", "ccc", "bb")
s.maxBy { it.length } |
55
wlwood 30 天前 via Android
算法怎么能分语言呢?只要是图灵完备的语言,都可以图灵等价。这个语言假如说能做出复杂度为 o(n),那么其他语言也肯定能做到 o(n)。
Lz 难道又是想来让论坛沸腾起来的么? |
![]() |
56
mulog 29 天前
不看楼主发帖记录我还真以为是来黑的。。
不知道说啥好。。。 |
![]() |
57
HanSonJ 29 天前
求你们了,别再来黑 PHP 了
![]() |
58
ImJoeHs 29 天前
你这跟那些‘一行写完 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 29 天前
系统函数排序实现是扔鞋的吗?
|
![]() |
60
popbones 29 天前 via iPhone
这就是为什么大家都说“ PHP 是最好的语言”
|
![]() |
61
20015jjw 29 天前 via Android
…可爱如楼主
|
62
873681136 29 天前 via iPhone
…
|
63
xsdhy 29 天前 via Android
每过几天就能看到黑 PHP 新的黑法,真有意思
|
![]() |
64
polymerdg 29 天前
你那复杂了
<?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 29 天前
@doraemon1293 他那个时间统计不靠谱。。一样的代码跑两次时间都不一样
|
![]() |
66
xAx 29 天前 ♥ 1
PHP 是最好的语言.....为什么会有人以为这句话是褒义?
|
![]() |
67
polymerdg 29 天前
$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 29 天前
楼上各位,包括 LZ,请注意审题:
“ Given a dictionary, find all of the longest words in the dictionary.” “ the longest words ” “ words ” "s" Example 里面返回的也都是数组好不好。你们一个个就返回一个字符串,使用啥算法也都铁定挂了。 |
69
vexjoe 29 天前
标题中就有错别字,这种动态语言可能不适合你。
|
![]() |
70
wizardoz 29 天前
php 果然是最好的语言,受教了!
|
![]() |
71
laoyuan 29 天前
今年以来 V2 黑 PHP 最狠的一次
|
![]() |
72
wupher 29 天前
看见标题我就笑了
|
![]() |
73
jokerjoker 29 天前
C#了解一下:
var longest = array.Where(x=>x.Length==array.Max(y => y.Length)); |
![]() |
74
blaxmirror 29 天前
算法的问题就不说了。
LZ 你只会 PHP,然后一番操作之后发现 PHP 是最好的语言。 逻辑在哪里? |
75
qxy 29 天前
@blaxmirror 因为,略看一些其他语言对于数组的操作。感觉,php 是最方便的
|
76
quericy 29 天前
14L 正解。。
|
77
quericy 29 天前
//$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 29 天前
萌新在 V 站讨论算法,感觉是个作死的行为
|
![]() |
79
skadi 29 天前
刚打算入门学习算法,遇到一题发现 PHP 果然是最好的 "语音"
🤔 |
![]() |
80
ftdejo 29 天前
建议去刷 leetcode··以及楼主黑的漂亮!
|
![]() |
81
kdwycz 29 天前
LZ 真是一粉顶十黑
|
![]() |
82
ftdejo 29 天前
```
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 29 天前
不就是一个[]和一个 int 的事吗。
遇到长的♂就把之前[]里的全踢了放新的,int 记录下新长♂度; 遇到一样的♂就追加到[]里; 遇到短的♂直接无视。 |
![]() |
84
ftdejo 29 天前
@ChristopherWu 这都要开个 hash 做··直接遍历一遍不就行了吗··
|
![]() |
85
sixand 29 天前
为什么要这样?
???(黑人问号脸) max([len(item) for item in ['123','54245234523432','fgewrgew','123432143','gfeg']]) |
![]() |
86
ChristopherWu 29 天前
@ ftdejo 秀逗了。。用数组就可以了,可以不用 hash。
|
87
vagranth 29 天前
当然是遍历一次,难道还要遍历两次?
|
![]() |
88
prolic 29 天前 via Android
从来不考虑时间复杂度,处理耗时长就推给 php 性能问题,php 还真是“最好的语言”
|
90
iceheart 29 天前 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 29 天前
lz 估计被吓坏
另外推荐 leetcode |
![]() |
92
vjnjc 29 天前
7 楼差不多对了,还要注意最大单词可能不止一个
|
93
xpresslink 29 天前
通过测试
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 29 天前 via iPhone
@resturlaub 终于看到大 ruby 了 哈哈哈
|
![]() |
96
loadinger 28 天前
数据结构白学了吗。。。。php 就是这样被搞臭的。
|