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

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

  •  
  •   qxy · 153 天前 · 6956 次点击
    这是一个创建于 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
        1
    LokiSharp   153 天前
    Win7 + Chrome, 代码输入界面没法 Backspace
        2
    qxy   153 天前
    @LokiSharp win10 + Chrome 可以。。
        3
    jasontse   153 天前 via iPad
    排序不算循环?
        4
    lhx2008   153 天前 via Android
    瞎搞。。还调排序,nlogn 了解一下
        5
    lizhenda   153 天前
    你调用系统函数算啥···
        6
    lhx2008   153 天前 via Android
    php 要调排序也是用 uasort 啊,哈哈
        7
    zjsxwc   153 天前   ♥ 1
    不用排序啊,直接贪心就行

    ```
    $a = [
    ];
    $maxLen = -1;
    $result = null;
    foreach ($a as $ele) {
    if ($maxLen < strlen($ele)) {
    $maxLen = strlen($ele);
    $result = $ele;
    }
    }
    ```
        8
    nbndco   153 天前 via iPhone
    感觉这个算法题解的有一些偏差……
        9
    Mervyn1205   153 天前
    数组是如下内容的时候,答案是错的
    {
    "like",
    "love",
    "hate",
    "yes"
    }
        10
    davinci   153 天前
    太慢了,而且没有考虑多个长度相同的字符串的情况。这题 o(n) 时间复杂度,o(n)空间复杂度,一次循环即可。
        11
    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"
    ])
        12
    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 写的,不生成数组不排序,直接找到最长单词。
        13
    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_

    随手写的= =略丑
        14
    ChristopherWu   152 天前   ♥ 2
    根本不需要排序。。
    遍历给出的 map 一遍,用 map[词的长度] 来存数组, 同时一个变量记录最长单词长度。

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

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


    修正一下
        68
    Clarencep   152 天前
    楼上各位,包括 LZ,请注意审题:
    “ Given a dictionary, find all of the longest words in the dictionary.”
    “ the longest words ”
    “ words ”
    "s"

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

    🤔
        80
    ftdejo   152 天前
    建议去刷 leetcode··以及楼主黑的漂亮!
        81
    kdwycz   152 天前
    LZ 真是一粉顶十黑
        82
    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 上刷的。。
        83
    snw   152 天前
    不就是一个[]和一个 int 的事吗。
    遇到长的♂就把之前[]里的全踢了放新的,int 记录下新长♂度;
    遇到一样的♂就追加到[]里;
    遇到短的♂直接无视。
        84
    ftdejo   152 天前
    @ChristopherWu 这都要开个 hash 做··直接遍历一遍不就行了吗··
        85
    sixand   152 天前
    为什么要这样?
    ???(黑人问号脸)
    max([len(item) for item in ['123','54245234523432','fgewrgew','123432143','gfeg']])
        86
    ChristopherWu   152 天前
    @ ftdejo 秀逗了。。用数组就可以了,可以不用 hash。
        87
    vagranth   152 天前
    当然是遍历一次,难道还要遍历两次?
        88
    prolic   152 天前 via Android
    从来不考虑时间复杂度,处理耗时长就推给 php 性能问题,php 还真是“最好的语言”
        89
    notreami   152 天前
    @gbin 最后那个 base64 去掉。这么明显的两个等号,一眼就知道 base64 了。还需要提醒嘛?
        90
    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) }
    }
        91
    psklf   152 天前
    lz 估计被吓坏
    另外推荐 leetcode
        92
    vjnjc   152 天前
    7 楼差不多对了,还要注意最大单词可能不止一个
        93
    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'
        94
    vZexc0m   151 天前
    @solaro 数组不可变,切片可变,我是这样认为的
        95
    ichou   151 天前 via iPhone
    @resturlaub 终于看到大 ruby 了 哈哈哈
        96
    loadinger   151 天前
    数据结构白学了吗。。。。php 就是这样被搞臭的。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3389 人在线   最高记录 3762   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 24ms · UTC 06:19 · PVG 14:19 · LAX 23:19 · JFK 02:19
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1