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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 153 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

96 回复 | 直到 2018-03-24 09:58:35 +08:00

LokiSharp 153 天前

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

qxy 153 天前

@LokiSharp win10 + Chrome 可以。。

jasontse 153 天前 via iPad

排序不算循环？

lhx2008 153 天前 via Android

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

lizhenda 153 天前

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

lhx2008 153 天前 via Android

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

zjsxwc 153 天前 ♥ 1

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

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

nbndco 153 天前 via iPhone

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

Mervyn1205 153 天前

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

davinci 153 天前

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

yuann72 153 天前

这样行么?

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 152 天前

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

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 152 天前 ♥ 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_

随手写的= =略丑

ChristopherWu 152 天前 ♥ 2

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

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

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

HypoChen 152 天前

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 152 天前

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

snowolfy 152 天前

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

ChristopherWu 152 天前

``
`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 152 天前

PHP 果然是最好的语言

jmc891205 152 天前

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

ChristopherWu 152 天前

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

qxy 152 天前

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

rrfeng 152 天前 via Android

lintcode ？不是 leetcode 吗

nbndco 152 天前

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

g00001 152 天前

@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 152 天前 via Android

python 一次循环就 ok 了吧

wsstest 152 天前

睡眠排序一步搞定

davinci 152 天前 via iPhone

@g00001 这个解法是对的

resturlaub 152 天前

arr.max_by(&:length)

vincenttone 152 天前

表示是来看热闹的

misaka19000 152 天前 ♥ 5

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

tommyZZM 152 天前

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 152 天前

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 152 天前

又黑 PHP （

mengyaoss77 152 天前

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

qxy 152 天前

@nbndco 受教了。

qxy 152 天前

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

carlclone 152 天前

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

liuhuansir 152 天前

学习算法最好用 C 语言

solaro 152 天前

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

joeke 152 天前

go 了解一下

CFMY 152 天前

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

doraemon1293 152 天前

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

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

cuebyte 152 天前 ♥ 1

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

zifuir 152 天前 via iPhone

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

gbin 152 天前 via Android

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

limbo0 152 天前

确实是最好的语音

cjyang1128 152 天前

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

misaka19000 152 天前

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

gbin 152 天前 via Android

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

lihongjie0209 152 天前

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

roychan 152 天前

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

sagaxu 152 天前

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

wlwood 152 天前 via Android

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

mulog 152 天前

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

HanSonJ 152 天前

求你们了，别再来黑 PHP 了

ImJoeHs 152 天前

你这跟那些‘一行写完 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 152 天前

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

popbones 152 天前 via iPhone

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

20015jjw 152 天前 via Android

…可爱如楼主

873681136 152 天前 via iPhone

…

xsdhy 152 天前 via Android

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

polymerdg 152 天前

你那复杂了

<?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 152 天前

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

xAx 152 天前 ♥ 1

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

polymerdg 152 天前

$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 152 天前

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

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

vexjoe 152 天前

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

wizardoz 152 天前

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

laoyuan 152 天前

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

wupher 152 天前

看见标题我就笑了

jokerjoker 152 天前

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

blaxmirror 152 天前

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

qxy 152 天前

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

quericy 152 天前

14L 正解。。

quericy 152 天前

//$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 152 天前

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

skadi 152 天前

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

🤔

ftdejo 152 天前

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

kdwycz 152 天前

LZ 真是一粉顶十黑

ftdejo 152 天前

```
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 152 天前

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

ftdejo 152 天前

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

sixand 152 天前

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

ChristopherWu 152 天前

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

vagranth 152 天前

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

prolic 152 天前 via Android

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

notreami 152 天前

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

iceheart 152 天前 via Android

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

psklf 152 天前

lz 估计被吓坏
另外推荐 leetcode

vjnjc 152 天前

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

xpresslink 152 天前

通过测试
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 151 天前

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

ichou 151 天前 via iPhone

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

loadinger 151 天前

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