iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 3
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 3

【從面試題學邏輯-3】計算最後一詞的長度(leetcode 58. Length of Last Word)

第一階段的選題由字串與陣列的題目為主

第一階段前半部選題以簡單的開胃菜為主,避免發生看到就直接勸退入門者的慘劇/images/emoticon/emoticon03.gif
解題有易有難,我們可以逐步提升深度,不必一下子就把難度暴增到超極限模式。

同時也介紹未來文章會出現的固定提醒:

首先是最大的提醒,所有題目在看解題前,先思考過再來看,能收獲到的東西一定會更多!本系列有規劃了題目的先後順序,在部分較需要思考的題目前,會帶入同類型的較簡單題目,讓大家可以用剛解出來的概念試試身手。

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若讀者還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!

同前一項敘述的題目順序,當然直接閱讀也不會有問題,但對如剛入門的新手玩家來說,可能逐漸往下會比較舒服一點。

那麼,讓我們進主題吧


↓點下方可以直接前往LeetCode
58. Length of Last Word

簡單敘述一下題目:
給你一串字串,找出最後一個詞的長度

也就是若題目給了「iT ironman race」就要傳回race的長度,也就是4。這裡給剛新手上路的讀者第一個提示:

有時候反過來思考會更有出路

這個題目如果從最前面開始找最後一個詞,就必須要排除掉前面其他的字詞,而且在讀到最後一個詞之前,程式不會知道正在讀的那個詞是否為最後一個詞。這就導致如果從前面開始走,就必須額外處理其他問題,就會把題目變得十分複雜。

那反過來思考呢?(參考下圖)

發現了嗎?正著數的最後一個詞,就是反著數的第一個詞,所以我們反著數的話,就可以直接算第一個數到的詞,而不用去排除前面無關的東西了!/images/emoticon/emoticon07.gif

所以這裡我們得到第一個重點:

  • 反著數這個字串拿到的第一個詞就是目標

所以我們可以依照這個邏輯,在LeetCode編輯器上先得出這段程式碼:

class Solution {
    public int lengthOfLastWord(String s) {
        int count = 0;
        for(int i = s.length()-1 ; i >= 0 ; i--) {
            if(s.charAt(i)!=' ') count++;
            else break;
        }
        return count;
    }
}

一些小補充:

  • charAt(i)是代表第 i 個字元,讀者可以把字串想像是一個把字元組合在一起的陣列,就能理解charAt()的操作了
  • 由於我們是反著算,一定會是目標的最後一個詞,可以直接開始算有幾個字。不等於空白的話,就代表還是在最後一個詞,如果是空白,就代表詞結束了

讓我們試著測試看看

答案不正確

這是怎麼回事呢?由於上述的程式碼沒有考慮到如果最後有空白的情況,所以有空白就直接break了。

所以我們可以再多一個重點:

  • 反著數這個字串拿到的第一個詞就是目標
  • 要把尾巴的空白跳過

那Java有一個叫做trim()的方法能幫我們處理掉頭尾的空白,所以我們像這樣先用trim()把字串的頭尾空白去掉,再開始數詞就不會有問題了。

class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();
        int count = 0;
        for(int i = s.length()-1 ; i >= 0 ; i--) {
            if(s.charAt(i)!=' ') count++;
            else break;
        }
        return count;
    }
}

恭喜!這題解決了/images/emoticon/emoticon12.gif


這裡同時也提供 Python 與 JavaScript 的程式碼

Python:

class Solution(object):
    def lengthOfLastWord(self, s):
        return len(s.strip().split(' ')[-1])
        

JavaScript:

var lengthOfLastWord = function(s) {
    return s.trim().split(' ').pop().length;
};

簡單說明解法:

Python拿長度是用len()來拿,而strip()的效果等同去頭尾空白
split()則是依照輸入,把字串中對應的地方切斷,把字串切成陣列

舉例來說,用split(' ')處理「iT ironman race」的話,就會拿到['iT', 'ironman', 'race']這個陣列。想像一下切青菜的過程,大概就知道那個概念了喔!

而Python可以直接用-1拿到陣列內的最後一個東西,也就是最後一個詞,那我們直接算他的長度就能得到答案

注意:不是每種語言都可以用 -1 拿最後一個!

JavaScript原理也很類似,先用trim()把空白去掉,接著用split()來把字串切成很多個詞。再來pop()是讓陣列吐出最後一個東西,那我們就可以直接算長度了。

pop()讓陣列吐出東西後,那個東西就不存在於陣列內嘍!


暖身完畢了嗎?明天我們再挑戰下一題


上一篇
【從面試題學邏輯-2】題目哪裡來?該怎麼做比較好?
下一篇
【從面試題學邏輯-4】CTCI 1.1 檢查字串內是否有重複字元
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言