V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
qxy
V2EX  ›  程序员

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

  •  
  •   qxy · 2018-03-22 13:31:11 +08:00 · 9189 次点击
    这是一个创建于 2198 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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
        1
    LokiSharp  
       2018-03-22 13:49:50 +08:00
    Win7 + Chrome, 代码输入界面没法 Backspace
    qxy
        2
    qxy  
    OP
       2018-03-22 13:55:22 +08:00
    @LokiSharp win10 + Chrome 可以。。
    jasontse
        3
    jasontse  
       2018-03-22 13:58:26 +08:00 via iPad
    排序不算循环?
    lhx2008
        4
    lhx2008  
       2018-03-22 13:59:23 +08:00 via Android
    瞎搞。。还调排序,nlogn 了解一下
    lizhenda
        5
    lizhenda  
       2018-03-22 14:02:08 +08:00
    你调用系统函数算啥···
    lhx2008
        6
    lhx2008  
       2018-03-22 14:02:21 +08:00 via Android
    php 要调排序也是用 uasort 啊,哈哈
    zjsxwc
        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;
    }
    }
    ```
    nbndco
        8
    nbndco  
       2018-03-22 14:04:34 +08:00 via iPhone
    感觉这个算法题解的有一些偏差……
    Mervyn1205
        9
    Mervyn1205  
       2018-03-22 14:07:59 +08:00
    数组是如下内容的时候,答案是错的
    {
    "like",
    "love",
    "hate",
    "yes"
    }
    davinci
        10
    davinci  
       2018-03-22 14:12:03 +08:00
    太慢了,而且没有考虑多个长度相同的字符串的情况。这题 o(n) 时间复杂度,o(n)空间复杂度,一次循环即可。
    yuann72
        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"
    ])
    g00001
        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 写的,不生成数组不排序,直接找到最长单词。
    LokiSharp
        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_

    随手写的= =略丑
    ChristopherWu
        14
    ChristopherWu  
       2018-03-22 14:29:30 +08:00   ❤️ 2
    根本不需要排序。。
    遍历给出的 map 一遍,用 map[词的长度] 来存数组, 同时一个变量记录最长单词长度。

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

    On 复杂度,估计是最低了。
    HypoChen
        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)))
    davinci
        16
    davinci  
       2018-03-22 14:31:28 +08:00
    @g00001 这题要求输出所有长度最长的字符串。你的解法只会输出第一个出现的长度最长的字符串
    snowolfy
        17
    snowolfy  
       2018-03-22 14:45:31 +08:00
    @HypoChen
    没必要 sort 的,@LokiSharp 的办法只需要字符串过一遍
    ChristopherWu
        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++,语法都七零八碎,查来查去。
    lxy42
        19
    lxy42  
       2018-03-22 14:48:40 +08:00
    PHP 果然是最好的语言
    jmc891205
        20
    jmc891205  
       2018-03-22 14:48:48 +08:00
    楼主是来黑 php 的吧 多大仇?
    ChristopherWu
        21
    ChristopherWu  
       2018-03-22 14:50:54 +08:00
    qxy
        22
    qxy  
    OP
       2018-03-22 14:57:23 +08:00
    @lizhenda
    @nbndco 这种题目,不能调用系统函数的吗。。 还真是不知道
    rrfeng
        23
    rrfeng  
       2018-03-22 15:02:48 +08:00 via Android
    lintcode ?不是 leetcode 吗
    nbndco
        24
    nbndco  
       2018-03-22 15:04:27 +08:00
    @qxy
    就算可以调用系统函数,你的答案本身还是错的(不看复杂度)。
    算法题本质考察的是你对算法的理解,你调用系统函数可以,你确定你的解法是最优的么?
    就这个问题而言,你确定排序里面没有遍历么?
    按照你的思路还可以写一个没有遍历的解法,只要把算法写一个函数调用一下就变成一行解决一个算法题了。
    g00001
        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");
    whoami9894
        26
    whoami9894  
       2018-03-22 15:16:28 +08:00 via Android
    python 一次循环就 ok 了吧
    wsstest
        27
    wsstest  
       2018-03-22 15:16:32 +08:00
    睡眠排序一步搞定
    davinci
        28
    davinci  
       2018-03-22 15:16:56 +08:00 via iPhone
    @g00001 这个解法是对的
    resturlaub
        29
    resturlaub  
       2018-03-22 15:24:43 +08:00
    arr.max_by(&:length)
    vincenttone
        30
    vincenttone  
       2018-03-22 15:31:58 +08:00
    表示是来看热闹的
    misaka19000
        31
    misaka19000  
       2018-03-22 15:38:54 +08:00   ❤️ 5
    怎么 V 站最近开贴黑 PHP 的人越来越多了
    tommyZZM
        32
    tommyZZM  
       2018-03-22 15:42:58 +08:00
    araraloren
        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
    htfy96
        34
    htfy96  
       2018-03-22 15:56:31 +08:00
    又黑 PHP (
    mengyaoss77
        35
    mengyaoss77  
       2018-03-22 16:04:33 +08:00
    搞个链表,
    遍历一遍原数组, 遇到相同大小的就加到链表后面, 遇到更大的就重建链表。
    最后输出链表,成了! 一次遍历!
    qxy
        36
    qxy  
    OP
       2018-03-22 16:57:10 +08:00
    @nbndco 受教了。
    qxy
        37
    qxy  
    OP
       2018-03-22 16:57:51 +08:00
    @jmc891205
    @misaka19000
    @htfy96 真没黑 php。。。我自己就是做 php 的,黑他干嘛。。 我就是萌新,大佬勿喷
    carlclone
        38
    carlclone  
       2018-03-22 17:10:18 +08:00
    别来丢人了真的.....
    liuhuansir
        39
    liuhuansir  
       2018-03-22 17:12:41 +08:00
    学习算法最好用 C 语言
    solaro
        40
    solaro  
       2018-03-22 17:13:18 +08:00
    go 的切片和 array 到底他妈的什么区别??看的我一脸懵逼
    joeke
        41
    joeke  
       2018-03-22 17:37:13 +08:00
    go 了解一下
    CFMY
        42
    CFMY  
       2018-03-22 18:03:31 +08:00
    算法追求的是时间和空间的效率,不是代码好看简练哦
    doraemon1293
        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
    cuebyte
        44
    cuebyte  
       2018-03-22 19:05:52 +08:00
    樓主你還是不要當程序員了⋯⋯排序的時間複雜度是 NlogN,你當是免費的?
    cuebyte
        45
    cuebyte  
       2018-03-22 19:07:15 +08:00   ❤️ 1
    樓主你這是真的一粉頂十黑
    zifuir
        46
    zifuir  
       2018-03-22 19:54:17 +08:00 via iPhone
    php 表示这锅他不背,太黑啦
    gbin
        47
    gbin  
       2018-03-22 20:04:30 +08:00 via Android
    🌚🌚这叫算法,PHP 都写好了兄弟咱俩有得一拼,有兴趣加我微信一起学?
    limbo0
        48
    limbo0  
       2018-03-22 20:09:33 +08:00
    确实是最好的语音
    cjyang1128
        49
    cjyang1128  
       2018-03-22 20:23:07 +08:00
    每过几天就能看到黑 PHP 新的黑法,真有意思
    misaka19000
        50
    misaka19000  
       2018-03-22 20:26:36 +08:00
    好吧 感觉楼主是个萌新各位也别太严格啦
    不过楼主还是多学门语言吧,只会 PHP 确实是会出现这样的问题
    gbin
        51
    gbin  
       2018-03-22 21:00:09 +08:00 via Android
    右转 /go/algorithm,每天一个算法题,有兴趣加我微信一起学习 cGdiMTYzNDc5NTI2Mg== ( base64 )
    lihongjie0209
        52
    lihongjie0209  
       2018-03-22 21:23:11 +08:00
    每过几天就能看到黑 PHP 新的黑法,真有意思
    roychan
        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]
    ...
    sagaxu
        54
    sagaxu  
       2018-03-22 22:27:40 +08:00
    val s = listOf("dddd", "a", "eeeee", "ccc", "bb")
    s.maxBy { it.length }
    wlwood
        55
    wlwood  
       2018-03-22 23:04:11 +08:00 via Android
    算法怎么能分语言呢?只要是图灵完备的语言,都可以图灵等价。这个语言假如说能做出复杂度为 o(n),那么其他语言也肯定能做到 o(n)。
    Lz 难道又是想来让论坛沸腾起来的么?
    mulog
        56
    mulog  
       2018-03-22 23:28:42 +08:00
    不看楼主发帖记录我还真以为是来黑的。。
    不知道说啥好。。。
    HanSonJ
        57
    HanSonJ  
       2018-03-22 23:48:29 +08:00
    求你们了,别再来黑 PHP 了
    ImJoeHs
        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, [])
    icenine
        59
    icenine  
       2018-03-23 00:21:28 +08:00
    系统函数排序实现是扔鞋的吗?
    popbones
        60
    popbones  
       2018-03-23 06:06:29 +08:00 via iPhone
    这就是为什么大家都说“ PHP 是最好的语言”
    20015jjw
        61
    20015jjw  
       2018-03-23 06:42:25 +08:00 via Android
    …可爱如楼主
    873681136
        62
    873681136  
       2018-03-23 07:39:36 +08:00 via iPhone
    xsdhy
        63
    xsdhy  
       2018-03-23 08:05:45 +08:00 via Android
    每过几天就能看到黑 PHP 新的黑法,真有意思
    polymerdg
        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];
    yuqaf
        65
    yuqaf  
       2018-03-23 08:58:16 +08:00
    @doraemon1293 他那个时间统计不靠谱。。一样的代码跑两次时间都不一样
    xAx
        66
    xAx  
       2018-03-23 08:59:09 +08:00   ❤️ 1
    PHP 是最好的语言.....为什么会有人以为这句话是褒义?
    polymerdg
        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];


    修正一下
    Clarencep
        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 里面返回的也都是数组好不好。你们一个个就返回一个字符串,使用啥算法也都铁定挂了。
    vexjoe
        69
    vexjoe  
       2018-03-23 09:17:00 +08:00
    标题中就有错别字,这种动态语言可能不适合你。
    wizardoz
        70
    wizardoz  
       2018-03-23 09:25:43 +08:00
    php 果然是最好的语言,受教了!
    laoyuan
        71
    laoyuan  
       2018-03-23 09:34:02 +08:00
    今年以来 V2 黑 PHP 最狠的一次
    wupher
        72
    wupher  
       2018-03-23 09:37:11 +08:00
    看见标题我就笑了
    jokerjoker
        73
    jokerjoker  
       2018-03-23 09:42:18 +08:00
    C#了解一下:
    var longest = array.Where(x=>x.Length==array.Max(y => y.Length));
    blaxmirror
        74
    blaxmirror  
       2018-03-23 10:15:20 +08:00
    算法的问题就不说了。
    LZ 你只会 PHP,然后一番操作之后发现 PHP 是最好的语言。
    逻辑在哪里?
    qxy
        75
    qxy  
    OP
       2018-03-23 10:28:01 +08:00
    @blaxmirror 因为,略看一些其他语言对于数组的操作。感觉,php 是最方便的
    quericy
        76
    quericy  
       2018-03-23 10:28:18 +08:00
    14L 正解。。
    quericy
        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]);
    wwqgtxx
        78
    wwqgtxx  
       2018-03-23 10:38:22 +08:00
    萌新在 V 站讨论算法,感觉是个作死的行为
    skadi
        79
    skadi  
       2018-03-23 10:42:59 +08:00
    刚打算入门学习算法,遇到一题发现 PHP 果然是最好的 "语音"

    🤔
    ftdejo
        80
    ftdejo  
       2018-03-23 10:46:48 +08:00
    建议去刷 leetcode··以及楼主黑的漂亮!
    kdwycz
        81
    kdwycz  
       2018-03-23 10:54:45 +08:00
    LZ 真是一粉顶十黑
    ftdejo
        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 上刷的。。
    snw
        83
    snw  
       2018-03-23 10:57:45 +08:00
    不就是一个[]和一个 int 的事吗。
    遇到长的♂就把之前[]里的全踢了放新的,int 记录下新长♂度;
    遇到一样的♂就追加到[]里;
    遇到短的♂直接无视。
    ftdejo
        84
    ftdejo  
       2018-03-23 11:01:01 +08:00
    @ChristopherWu 这都要开个 hash 做··直接遍历一遍不就行了吗··
    sixand
        85
    sixand  
       2018-03-23 11:14:21 +08:00
    为什么要这样?
    ???(黑人问号脸)
    max([len(item) for item in ['123','54245234523432','fgewrgew','123432143','gfeg']])
    ChristopherWu
        86
    ChristopherWu  
       2018-03-23 11:30:57 +08:00
    @ ftdejo 秀逗了。。用数组就可以了,可以不用 hash。
    vagranth
        87
    vagranth  
       2018-03-23 12:30:32 +08:00
    当然是遍历一次,难道还要遍历两次?
    prolic
        88
    prolic  
       2018-03-23 12:37:56 +08:00 via Android
    从来不考虑时间复杂度,处理耗时长就推给 php 性能问题,php 还真是“最好的语言”
    notreami
        89
    notreami  
       2018-03-23 12:52:47 +08:00
    @gbin 最后那个 base64 去掉。这么明显的两个等号,一眼就知道 base64 了。还需要提醒嘛?
    iceheart
        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) }
    }
    psklf
        91
    psklf  
       2018-03-23 13:15:01 +08:00
    lz 估计被吓坏
    另外推荐 leetcode
    vjnjc
        92
    vjnjc  
       2018-03-23 13:36:32 +08:00
    7 楼差不多对了,还要注意最大单词可能不止一个
    xpresslink
        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'
    vZexc0m
        94
    vZexc0m  
       2018-03-23 15:20:27 +08:00
    @solaro 数组不可变,切片可变,我是这样认为的
    ichou
        95
    ichou  
       2018-03-23 21:17:47 +08:00 via iPhone
    @resturlaub 终于看到大 ruby 了 哈哈哈
    loadinger
        96
    loadinger  
       2018-03-24 09:58:35 +08:00
    数据结构白学了吗。。。。php 就是这样被搞臭的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4722 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 01:08 · PVG 09:08 · LAX 18:08 · JFK 21:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.