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 啊,哈哈
|
7
zjsxwc 2018-03-22 14:03:43 +08:00 1
不用排序啊,直接贪心就行
``` $a = [ ]; $maxLen = -1; $result = null; foreach ($a as $ele) { if ($maxLen < strlen($ele)) { $maxLen = strlen($ele); $result = $ele; } } ``` |
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 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 2018-03-22 14:29:30 +08:00 2
根本不需要排序。。
遍历给出的 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 5
怎么 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 1
樓主你這是真的一粉頂十黑
|
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 1
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','fgewrgew','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 就是这样被搞臭的。
|