刚打算入门学习算法，遇到一题发现 PHP 果然是最好的语音

[qxy]

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 对于数组的处理比其他语言要厉害。难道，果真如此，其他语言，对于这题有啥不同的解法，请赐教！

[LokiSharp]

Win7 + Chrome, 代码输入界面没法 Backspace

[qxy]

@LokiSharp win10 + Chrome 可以。。

[jasontse]

排序不算循环？

[lhx2008]

瞎搞。。还调排序，nlogn 了解一下

[lizhenda]

你调用系统函数算啥···

[lhx2008]

php 要调排序也是用 uasort 啊，哈哈

[zjsxwc]

不用排序啊，直接贪心就行

```
$a = [
];
$maxLen = -1;
$result = null;
foreach ($a as $ele) {
if ($maxLen < strlen($ele)) {
$maxLen = strlen($ele);
$result = $ele;
}
}
```

[nbndco]

感觉这个算法题解的有一些偏差……

[Mervyn1205]

数组是如下内容的时候，答案是错的
{
"like",
"love",
"hate",
"yes"
}

[davinci]

太慢了，而且没有考虑多个长度相同的字符串的情况。这题 o(n) 时间复杂度，o(n)空间复杂度，一次循环即可。

[yuann72]

这样行么?


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"
])

[g00001]

一个循环是可以的，
数组排序也不是必须的，排序也是有代价的。
这个题应当是降低了难度，如果从文本中查找，实际上数组也可以省略掉，生成数组也是有消耗的。

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 写的，不生成数组不排序，直接找到最长单词。

[LokiSharp]

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_

随手写的= =略丑

[ChristopherWu]

根本不需要排序。。
遍历给出的 map 一遍，用 map[词的长度] 来存数组， 同时一个变量记录最长单词长度。

直接返回 map[最长单词长度]即可

On 复杂度，估计是最低了。

[HypoChen]

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)))

[davinci]

@g00001 这题要求输出所有长度最长的字符串。你的解法只会输出第一个出现的长度最长的字符串

[snowolfy]

@HypoChen
没必要 sort 的，@LokiSharp 的办法只需要字符串过一遍

[ChristopherWu]

``
`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++，语法都七零八碎，查来查去。

[lxy42]

PHP 果然是最好的语言

[jmc891205]

楼主是来黑 php 的吧 多大仇？

[ChristopherWu]

http://www.lintcode.com/submission/13711573/

[qxy]

@lizhenda
@nbndco 这种题目，不能调用系统函数的吗。。 还真是不知道

[rrfeng]

lintcode ？不是 leetcode 吗

[nbndco]

@qxy
就算可以调用系统函数，你的答案本身还是错的（不看复杂度）。
算法题本质考察的是你对算法的理解，你调用系统函数可以，你确定你的解法是最优的么？
就这个问题而言，你确定排序里面没有遍历么？
按照你的思路还可以写一个没有遍历的解法，只要把算法写一个函数调用一下就变成一行解决一个算法题了。

[g00001]

@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");

[whoami9894]

python 一次循环就 ok 了吧

[wsstest]

睡眠排序一步搞定

[davinci]

@g00001 这个解法是对的

[resturlaub]

arr.max_by(&:length)

[vincenttone]

表示是来看热闹的

[misaka19000]

怎么 V 站最近开贴黑 PHP 的人越来越多了

[tommyZZM]

ksort 里面的循环...

https://github.com/php/php-src/blob/master/ext/standard/array.c#L726
https://github.com/php/php-src/blob/master/Zend/zend_hash.c#L2322

有一些开销是隐式的...

[araraloren]

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

[htfy96]

又黑 PHP （

[mengyaoss77]

搞个链表，
遍历一遍原数组， 遇到相同大小的就加到链表后面， 遇到更大的就重建链表。
最后输出链表，成了！ 一次遍历！

[qxy]

@nbndco 受教了。

[qxy]

@jmc891205
@misaka19000
@htfy96 真没黑 php。。。我自己就是做 php 的，黑他干嘛。。 我就是萌新，大佬勿喷

[carlclone]

别来丢人了真的.....

[liuhuansir]

学习算法最好用 C 语言

[solaro]

go 的切片和 array 到底他妈的什么区别？？看的我一脸懵逼

[joeke]

go 了解一下

[CFMY]

算法追求的是时间和空间的效率，不是代码好看简练哦

[doraemon1293]

随手一写竟然 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

[cuebyte]

樓主你還是不要當程序員了⋯⋯排序的時間複雜度是 NlogN，你當是免費的？

[cuebyte]

樓主你這是真的一粉頂十黑

[zifuir]

php 表示这锅他不背，太黑啦

[gbin]

🌚🌚这叫算法，PHP 都写好了兄弟咱俩有得一拼，有兴趣加我微信一起学?

[limbo0]

确实是最好的语音

[cjyang1128]

每过几天就能看到黑 PHP 新的黑法，真有意思

[misaka19000]

好吧 感觉楼主是个萌新各位也别太严格啦
不过楼主还是多学门语言吧，只会 PHP 确实是会出现这样的问题

[gbin]

右转 /go/algorithm，每天一个算法题，有兴趣加我微信一起学习 cGdiMTYzNDc5NTI2Mg== （ base64 ）

[lihongjie0209]

每过几天就能看到黑 PHP 新的黑法，真有意思

[roychan]

max_len = max([len(x) for x in dictionary])
return [x for x in dictionary if len(x) == max_len]
...

[sagaxu]

val s = listOf("dddd", "a", "eeeee", "ccc", "bb")
s.maxBy { it.length }

[wlwood]

算法怎么能分语言呢？只要是图灵完备的语言，都可以图灵等价。这个语言假如说能做出复杂度为 o(n)，那么其他语言也肯定能做到 o(n)。
Lz 难道又是想来让论坛沸腾起来的么？

[mulog]

不看楼主发帖记录我还真以为是来黑的。。
不知道说啥好。。。

[HanSonJ]

求你们了，别再来黑 PHP 了

[ImJoeHs]

你这跟那些‘一行写完 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, [])

[icenine]

系统函数排序实现是扔鞋的吗？

[popbones]

这就是为什么大家都说“ PHP 是最好的语言”

[20015jjw]

…可爱如楼主

[873681136]

…

[xsdhy]

每过几天就能看到黑 PHP 新的黑法，真有意思

[polymerdg]

你那复杂了

<?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];

[yuqaf]

@doraemon1293 他那个时间统计不靠谱。。一样的代码跑两次时间都不一样

[xAx]

PHP 是最好的语言.....为什么会有人以为这句话是褒义?

[polymerdg]

$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];


修正一下

[Clarencep]

楼上各位，包括 LZ，请注意审题：
“ Given a dictionary, find all of the longest words in the dictionary.”
“ the longest words ”
“ words ”
"s"

Example 里面返回的也都是数组好不好。你们一个个就返回一个字符串，使用啥算法也都铁定挂了。

[vexjoe]

标题中就有错别字，这种动态语言可能不适合你。

[wizardoz]

php 果然是最好的语言，受教了！

[laoyuan]

今年以来 V2 黑 PHP 最狠的一次

[wupher]

看见标题我就笑了

[jokerjoker]

C#了解一下:
var longest = array.Where(x=>x.Length==array.Max(y => y.Length));

[blaxmirror]

算法的问题就不说了。
LZ 你只会 PHP，然后一番操作之后发现 PHP 是最好的语言。
逻辑在哪里？

[qxy]

@blaxmirror 因为，略看一些其他语言对于数组的操作。感觉，php 是最方便的

[quericy]

14L 正解。。

[quericy]

//$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]);

[wwqgtxx]

萌新在 V 站讨论算法，感觉是个作死的行为

[skadi]

刚打算入门学习算法，遇到一题发现 PHP 果然是最好的 "语音"

🤔

[ftdejo]

建议去刷 leetcode··以及楼主黑的漂亮！

[kdwycz]

LZ 真是一粉顶十黑

[ftdejo]

```
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 上刷的。。

[snw]

不就是一个[]和一个 int 的事吗。
遇到长的♂就把之前[]里的全踢了放新的，int 记录下新长♂度；
遇到一样的♂就追加到[]里；
遇到短的♂直接无视。

[ftdejo]

@ChristopherWu 这都要开个 hash 做··直接遍历一遍不就行了吗··

[sixand]

为什么要这样?
???(黑人问号脸)
max([len(item) for item in ['123','54245234523432','fgewrgew','123432143','gfeg']])

[ChristopherWu]

@ ftdejo 秀逗了。。用数组就可以了，可以不用 hash。

[vagranth]

当然是遍历一次，难道还要遍历两次？

[prolic]

从来不考虑时间复杂度，处理耗时长就推给 php 性能问题，php 还真是“最好的语言”

[notreami]

@gbin 最后那个 base64 去掉。这么明显的两个等号，一眼就知道 base64 了。还需要提醒嘛？

[iceheart]

var len = 0
var list = []
for ( x in array ){
if x.length > len { list = [] }
if x.length == len { list.pushback(x) }
}

[psklf]

lz 估计被吓坏
另外推荐 leetcode

[vjnjc]

7 楼差不多对了，还要注意最大单词可能不止一个

[xpresslink]

通过测试
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'

[vZexc0m]

@solaro 数组不可变，切片可变，我是这样认为的

[ichou]

@resturlaub 终于看到大 ruby 了 哈哈哈

[loadinger]

数据结构白学了吗。。。。php 就是这样被搞臭的。