算法養成記：最後字符長度

• 2020 年 3 月 26 日
• 筆記

呆萌程序員

算法養成記

LeetCode58

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Example:

Input: "Hello World"

Output: 5

中文意思就是：

給定一個僅包含大小寫字母和空格 ' ' 的字符串 s，返回其最後一個單詞的長度。如果字符串從左向右滾動顯示，那麼最後一個單詞就是最後出現的單詞。

如果不存在最後一個單詞，請返回 0 。

說明：一個單詞是指僅由字母組成、不包含任何空格字符的 最大子字符串。

示例:

輸入: "Hello World"

輸出: 5

偷個懶，也是一個很不要臉的方法：

Java字符串中帶有方法split(String regex)，將字符串按照regex拆分成字符串數組；

所以將字符串根據空格拆分成數組，之後統計最後一個字符串長度即可。

我們目的是計算最後一個單詞的長度。

所以需要兩個指針

指針1：從後往前找，找到第一個不為空的位置；

指針2：在指針1的基礎上，繼續往前找，找到第一個為空的位置；

兩個指針相減，則為最後一個單詞長度。

定義一個變量length，從後遍歷,遇到不為空的字符就加1；

遇到空，且長度不為0，則返回；

這裡有個問題，有一起學習的小夥伴給出下面的方法：

差別就在於，將字符串轉成了字符數組，之後再遍歷字符數組。這裡也不是說不可以。我們可以看到String在Java中的源碼，值就是使用 char數組存儲的，也就是字符串字符是可以隨機取得，沒必要再轉成字符數組。

我們也可以看看toCharArray()具體幹了什麼；

從下圖源碼我們可以看到，它是複製了原字符串中，新返回了一個字符數組，總體來說代價是不划算的。

在實際測試里

執行用時分別是：0ms,0ms,0ms

內存消耗分別是:37.7MB,37.6MB,37.8MB

添加微信進群學習：miraclesComing

數據結構算法不用抖，

大廠面試筆試不用愁！