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

[Leetcode] 58. 最后一个单词的长度

  •  
  •   Acceml · 2018-09-02 09:27:29 +08:00 · 4013 次点击
    这是一个创建于 2258 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。

    如果不存在最后一个单词,请返回 0。

    说明:一个单词是指由字母组成,但不包含任何空格的字符串。

    示例:

    输入: "Hello World"
    输出: 5
    

    题解

    这个题比较水,主要是注意一下前后有空格这种情况。 如下代码用 preLong 记录截止到当前字符最后一个单词的长度.

    class Solution {
        public int lengthOfLastWord(String s) {
            if (s.length() == 0 || s == null) return 0;
            
            int slong = 0;
            int preLong = 0;  // 记录最后一个 word 的长度
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == ' ' ) {
                    slong = 0;
                } else {
                    slong++;  
                    preLong = slong;
                }
            }
            
            return preLong;
        }
    }
    

    每日英语

    • identify (v.) 确认
    • identify ... with ... 确认...
    • identity (n.) 身份;统一性
    • classify (v.) 分类
    • recognize (v.) 识别,认出
    • cognition (n.) 认知

    热门阅读


    最近在刷题,主要更新后端相关知识 Leetcode 名企之路

    31 条回复    2018-09-03 09:27:52 +08:00
    nooper
        1
    nooper  
       2018-09-02 09:55:02 +08:00
    len("sfd dsfd".split()[-1])
    liuyl
        2
    liuyl  
       2018-09-02 09:56:50 +08:00   ❤️ 1
    即使遍历,为什么不从后往前遍历?
    xd314697475
        3
    xd314697475  
       2018-09-02 10:03:11 +08:00
    从后往前,速度不是提高了吗?
    20015jjw
        4
    20015jjw  
       2018-09-02 10:13:27 +08:00 via Android   ❤️ 1
    lz 误人子弟还推广自己的号不好吧

    @Livid 这种算推广么
    jedihy
        5
    jedihy  
       2018-09-02 10:16:33 +08:00 via iPhone
    这不是坑爹吗?这样的代码自封名企之路?
    Acceml
        6
    Acceml  
    OP
       2018-09-02 10:20:42 +08:00
    @xd314697475 嗯,是的,从后面向前快一点,时间复杂度没变化。

    @20015jjw 不够快也不算误人子弟吧

    @jedihy 除了楼上说的从后向前,您有什么比较好的思路呢?

    @20015jjw 这个号一方面是我自己总结,一方面是和大家交流。您有什么比较好的解法吗?
    liuguang
        7
    liuguang  
       2018-09-02 10:20:44 +08:00
    哈哈,当然从后往前快了
    Acceml
        8
    Acceml  
    OP
       2018-09-02 10:21:39 +08:00
    @nooper 你这个显然不符合要求的,兄弟。有空格的情况你没处理,而且既然是面试肯定不能用 trim() split()这种方法的啊。
    pipapa
        9
    pipapa  
       2018-09-02 10:40:51 +08:00
    至少要是最优解吧,每天都来推广以下。
    Acceml
        10
    Acceml  
    OP
       2018-09-02 10:43:49 +08:00
    @pipapa 表达只是思考的工具,不一定是思考的结果。我是这么看的,所以评论区有怼我的,我也觉得是正常,大家交流嘛,而且我是弱菜。
    nooper
        11
    nooper  
       2018-09-02 10:59:25 +08:00
    @Acceml 没认真审题
    jedihy
        12
    jedihy  
       2018-09-02 11:10:10 +08:00 via iPhone
    @Acceml 这个题就这么一个考点,你 miss 掉了。
    ihainan
        13
    ihainan  
       2018-09-02 11:27:24 +08:00
    哈哈我不怼楼主,我还挺喜欢楼主这个栏目的,我也在刷 LeetCode,楼主贴的几道题相对比较简单,顺手去 A 一下调剂一下心情。

    几点小建议哈:

    1. 每次贴出自己的 Solution 之前,不妨看看 Discuss 区别人的答案,楼主想跟别人交流目的是好,但万一某道题交流的人少呢,其他更优的 Solution 自己总得看一下吧?

    2. 一次一道题我还是觉得少了…您之前说的,200 道题,国内几乎所有互联网都够应付了,这点换几年前或许还行,但 LeetCode 现在已经将近 900 题了,您最近的几道题基本都是 Easy 或者是 Normal 难度偏低的,我觉得还是不大够。

    3. 一次一个专题或许会更好些?
    fyyz
        14
    fyyz  
       2018-09-02 11:36:24 +08:00
    @Acceml 还特么时间复杂度没变化。

    假设字符串长度为 M,最后一个单词的长度为 N,从前往后遍历,时间复杂度为 O(M),而从后往前遍历,时间复杂度为 O(N)。

    显而易见,字符串长度可以是几个字符,也可以是数 MB 大小,比如说一本原著的 TXT 全文。
    而单词的长度,最多也就 20 个单词了吧?当然也可能有更长的,但是大致都在 20 单词以内。

    因此,从前往后遍历,时间复杂度严重依赖字符串长度,是线性的时间复杂度。
    而从后往前遍历,时间复杂度取决于单词长度,虽然也是线性时间复杂度,但是由于单词长度很短,所以时间复杂度大致可以看成常数时间复杂度。
    ihainan
        15
    ihainan  
       2018-09-02 11:37:14 +08:00
    还有时间复杂度并非没变化呀,O(N)
    ihainan
        16
    ihainan  
       2018-09-02 11:38:07 +08:00
    和 O(W) 是否有差距完全取决于 N (总长度)和 W (最后一个单词长度)的规模。
    fyyz
        17
    fyyz  
       2018-09-02 11:39:41 +08:00
    这水平还是好好回家修炼吧,leetcode 的入门题都做这幅鸟样,还名企呢,丢人。
    ffkjjj
        18
    ffkjjj  
       2018-09-02 12:37:18 +08:00 via iPhone   ❤️ 2
    if (s.length() == 0 || s == null)
    ……
    MSilen
        19
    MSilen  
       2018-09-02 12:43:41 +08:00 via Android   ❤️ 1
    if (s.length() == 0 || s == null)

    楼主别刷题了,先补一下基础先
    tsui
        20
    tsui  
       2018-09-02 13:36:30 +08:00
    @MSilen 哈哈哈哈线上丢 NPE,估计答题者没在正经公司写过代码
    TtiGeR
        21
    TtiGeR  
       2018-09-02 13:56:53 +08:00 via iPhone
    都在吐槽算法 那我就吐槽个单词吧

    像 identify 这种词 光光记为“确认”是很容易混淆用法的

    这个词和 confirm, verify, validate, recognize 在不同情况下的用法要注意异同之处~ 还是建议用英英词典的释义。
    ranleng
        22
    ranleng  
       2018-09-02 14:18:37 +08:00
    ( identify 更像是识别出来出什么东西.
    Acceml
        23
    Acceml  
    OP
       2018-09-02 14:54:52 +08:00
    @fyyz 感谢~~

    @MSilen
    @ffkjjj 确实写得有问题。感谢。

    @fyyz 慢慢会成长的呀,就记录一下题解,丢人也还好。


    @TtiGeR 嗯。记单词确实要放在句子中,不过由于篇幅有限,我这个号也不打算做成英语的号,只是希望不要忘记英语,能通顺的读技术文档。
    Acceml
        24
    Acceml  
    OP
       2018-09-02 15:05:20 +08:00
    感谢大家回复。
    这道题就是因为太简单,所以昨天我就没 A,直接找的网上的 code,没想到那么多问题,为自己不认真检讨下。
    顺便,很喜欢 v 站的氛围,大家都很认真。
    LGA1150
        25
    LGA1150  
       2018-09-02 15:28:49 +08:00
    class Solution {
    public int lengthOfLastWord(String s) {
    int len = 0, tail = s.length() - 1;
    while (tail >= 0 && s.charAt(tail) == ' ') tail--;
    while (tail >= 0 && s.charAt(tail) != ' ') {
    len++;
    tail--;
    }
    return len;
    }
    };

    运行时间 3ms
    回复吞缩进,将就看吧
    LGA1150
        26
    LGA1150  
       2018-09-02 15:29:23 +08:00
    @ffkjjj
    @MSilen
    po 主贴的 Java 代码
    gzlock
        27
    gzlock  
       2018-09-02 16:29:20 +08:00
    @LGA1150 #26 if (s.length() == 0 || s == null) 与 名企之路 这个人设已经崩了,这个号算是臭了。。。
    CheaperCoder
        28
    CheaperCoder  
       2018-09-02 17:09:39 +08:00
    作为一个“名企之路”的号,分享这种代码,不觉得是自己的问题吗?也难怪大家怼你了。
    NickCarter
        29
    NickCarter  
       2018-09-02 17:35:16 +08:00
    ```js

    const lengthOfLastWord = function (s) {
    if(/^ *$/.test(s)) {
    return 0
    }
    return s.match(/ *([A-z]+) *$/)[1].length
    }

    ```
    ayyll
        30
    ayyll  
       2018-09-03 09:04:08 +08:00 via Android
    好多怼楼主
    1.说两句 解题报告这种东西,说白了,写一遍容易让自己思路更清晰,但超级费时间 写一遍的时间够 A 好几道题了 emm
    2.水题适可而止吧。。。如果真打算在算法上有建树的话 高级数据结构,数论,图论,计算几何,以及零零碎碎的 dp 什么的 按专题一路扫过去
    3.如果只是应付一般性的面试的话,当我没说
    Acceml
        31
    Acceml  
    OP
       2018-09-03 09:27:52 +08:00
    @ayyll 点开看了下,你搞 ACM,这块知识确实很厉害。不过我开这个号就是为了强迫总结自己的知识。但是总结的东西不可能每天都发,不发的时候我就 A 一道题。这是之前的内容: https://www.v2ex.com/t/485438#reply7
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1026 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 22:06 · PVG 06:06 · LAX 14:06 · JFK 17:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.