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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

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

2018-03-22 13:49:50 +08:00

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

qxy

2018-03-22 13:55:22 +08:00

@LokiSharp win10 + Chrome 可以。。

jasontse

2018-03-22 13:58:26 +08:00 via iPad

排序不算循环？

lhx2008

2018-03-22 13:59:23 +08:00 via Android

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

lizhenda

2018-03-22 14:02:08 +08:00

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

lhx2008

2018-03-22 14:02:21 +08:00 via Android

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

zjsxwc

2018-03-22 14:03:43 +08:00

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

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

nbndco

2018-03-22 14:04:34 +08:00 via iPhone

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

Mervyn1205

2018-03-22 14:07:59 +08:00

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

davinci

2018-03-22 14:12:03 +08:00

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

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

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

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_

随手写的= =略丑

ChristopherWu

2018-03-22 14:29:30 +08:00

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

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

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

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

davinci

2018-03-22 14:31:28 +08:00

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

snowolfy

2018-03-22 14:45:31 +08:00

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

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

lxy42

2018-03-22 14:48:40 +08:00

PHP 果然是最好的语言

jmc891205

2018-03-22 14:48:48 +08:00

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

ChristopherWu

2018-03-22 14:50:54 +08:00

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

qxy

2018-03-22 14:57:23 +08:00

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

rrfeng

2018-03-22 15:02:48 +08:00 via Android

lintcode ？不是 leetcode 吗

nbndco

2018-03-22 15:04:27 +08:00

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

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

whoami9894

2018-03-22 15:16:28 +08:00 via Android

python 一次循环就 ok 了吧

wsstest

2018-03-22 15:16:32 +08:00

睡眠排序一步搞定

davinci

2018-03-22 15:16:56 +08:00 via iPhone

@g00001 这个解法是对的

resturlaub

2018-03-22 15:24:43 +08:00

arr.max_by(&:length)

vincenttone

2018-03-22 15:31:58 +08:00

表示是来看热闹的

misaka19000

2018-03-22 15:38:54 +08:00

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

tommyZZM

2018-03-22 15:42:58 +08:00

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

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

htfy96

2018-03-22 15:56:31 +08:00

又黑 PHP （

mengyaoss77

2018-03-22 16:04:33 +08:00

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

qxy

2018-03-22 16:57:10 +08:00

@nbndco 受教了。

qxy

2018-03-22 16:57:51 +08:00

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

carlclone

2018-03-22 17:10:18 +08:00

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

liuhuansir

2018-03-22 17:12:41 +08:00

学习算法最好用 C 语言

solaro

2018-03-22 17:13:18 +08:00

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

joeke

2018-03-22 17:37:13 +08:00

go 了解一下

CFMY

2018-03-22 18:03:31 +08:00

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

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

cuebyte

2018-03-22 19:05:52 +08:00

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

cuebyte

2018-03-22 19:07:15 +08:00

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

zifuir

2018-03-22 19:54:17 +08:00 via iPhone

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

gbin

2018-03-22 20:04:30 +08:00 via Android

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

limbo0

2018-03-22 20:09:33 +08:00

确实是最好的语音

cjyang1128

2018-03-22 20:23:07 +08:00

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

misaka19000

2018-03-22 20:26:36 +08:00

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

gbin

2018-03-22 21:00:09 +08:00 via Android

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

lihongjie0209

2018-03-22 21:23:11 +08:00

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

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]
...

sagaxu

2018-03-22 22:27:40 +08:00

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

wlwood

2018-03-22 23:04:11 +08:00 via Android

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

mulog

2018-03-22 23:28:42 +08:00

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

HanSonJ

2018-03-22 23:48:29 +08:00

求你们了，别再来黑 PHP 了

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, [])

icenine

2018-03-23 00:21:28 +08:00

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

popbones

2018-03-23 06:06:29 +08:00 via iPhone

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

20015jjw

2018-03-23 06:42:25 +08:00 via Android

…可爱如楼主

873681136

2018-03-23 07:39:36 +08:00 via iPhone

…

xsdhy

2018-03-23 08:05:45 +08:00 via Android

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

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

yuqaf

2018-03-23 08:58:16 +08:00

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

xAx

2018-03-23 08:59:09 +08:00

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

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

修正一下

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 里面返回的也都是数组好不好。你们一个个就返回一个字符串，使用啥算法也都铁定挂了。

vexjoe

2018-03-23 09:17:00 +08:00

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

wizardoz

2018-03-23 09:25:43 +08:00

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

laoyuan

2018-03-23 09:34:02 +08:00

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

wupher

2018-03-23 09:37:11 +08:00

看见标题我就笑了

jokerjoker

2018-03-23 09:42:18 +08:00

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

blaxmirror

2018-03-23 10:15:20 +08:00

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

qxy

2018-03-23 10:28:01 +08:00

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

quericy

2018-03-23 10:28:18 +08:00

14L 正解。。

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

wwqgtxx

2018-03-23 10:38:22 +08:00

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

skadi

2018-03-23 10:42:59 +08:00

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

🤔

ftdejo

2018-03-23 10:46:48 +08:00

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

kdwycz

2018-03-23 10:54:45 +08:00

LZ 真是一粉顶十黑

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

snw

2018-03-23 10:57:45 +08:00

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

ftdejo

2018-03-23 11:01:01 +08:00

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

sixand

2018-03-23 11:14:21 +08:00

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

ChristopherWu

2018-03-23 11:30:57 +08:00

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

vagranth

2018-03-23 12:30:32 +08:00

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

prolic

2018-03-23 12:37:56 +08:00 via Android

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

notreami

2018-03-23 12:52:47 +08:00

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

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

psklf

2018-03-23 13:15:01 +08:00

lz 估计被吓坏
另外推荐 leetcode

vjnjc

2018-03-23 13:36:32 +08:00

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

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'

vZexc0m

2018-03-23 15:20:27 +08:00

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

ichou

2018-03-23 21:17:47 +08:00 via iPhone

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

loadinger

2018-03-24 09:58:35 +08:00

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