題目描述:給定一個字串 s,其中包含英文字母和空格,請回傳最後一個單字的長度。「單字」定義為不含空格的連續字元序列。字串尾端可能存在多個空格,需忽略。
解題思路:從字串末尾向前掃描,分兩步驟進行:第一步,跳過所有尾端的空格(避免將尾部空格計入結果);第二步,從第一個非空格字元開始向前計數,直到遇到空格或到達字串開頭為止。計數值即為最後一個單字的長度。這種方式只需一次線性掃描,且不需要額外分割字串,非常高效。關鍵陷阱在於必須先處理尾端空格,否則若直接從尾端計數會把空格也算進去。
時間複雜度:O(n) — 最壞情況下(如字串全為空格加一個字)需掃描整個字串,n 為字串長度。
空間複雜度:O(1) — 只使用兩個整數指針,不需額外的字串或陣列空間。
1. Set pointer i = length of s - 1 2. While i >= 0 and s[i] == ' ': - Decrement i (skip trailing spaces) 3. Initialize length = 0 4. While i >= 0 and s[i] != ' ': - Increment length - Decrement i (count last word characters) 5. Return length
方法一:正向掃描記錄每個單字長度
從頭到尾掃描字串,每遇到一個完整單字(空格結束)就更新 lastLen,最終回傳 lastLen。缺點是必須完整掃描整個字串,即使答案在最末端也一樣;時間複雜度 O(n),但實際運行常數較大。
方法二:字串分割(split by spaces)
使用 STL 的 istringstream 或手動分割,將字串按空格切分成多個 token,取最後一個 token 的長度。程式碼最直觀,但需額外 O(n) 的空間來存儲所有 token,且分割過程消耗較多時間,不如從尾端掃描高效。
\t、\n),程式碼需要哪些修改?使用 isspace() 函式有何優勢?