題目描述:
給定一個正整數 columnNumber,回傳它在 Excel 表格中對應的欄位名稱。例如:1 → "A"、26 → "Z"、27 → "AA"、28 → "AB"、701 → "ZY"。
解題思路: 這是一個 26 進位轉換問題,但與標準進位轉換不同,Excel 欄位是 1-indexed(A=1, B=2, ..., Z=26),而非 0-indexed。
關鍵步驟:
columnNumber 減 1,將其轉為 0-indexed(A=0, B=1, ..., Z=25)。(columnNumber - 1) % 26 得到當前最低位對應的字母。(columnNumber - 1) / 26 得到剩餘的高位數值。columnNumber 為 0。時間複雜度:O(log₂₆ n) — 每次迴圈將 columnNumber 除以 26,迴圈次數為欄位名稱的長度。
空間複雜度:O(log₂₆ n) — 結果字串的長度。
1. Initialize result = "" 2. While columnNumber > 0: a. Decrement columnNumber by 1 (convert to 0-indexed) b. Append character 'A' + (columnNumber % 26) to result c. columnNumber = columnNumber / 26 3. Reverse result string 4. Return result
遞迴法:基礎情況為 columnNumber == 0 時回傳空字串。遞迴呼叫 convertToTitle((columnNumber - 1) / 26) 處理高位,再接上當前字母 (char)('A' + (columnNumber - 1) % 26)。時間空間複雜度相同,但程式碼更簡潔,不需要反轉字串。
前端插入法:每次將字母插入字串前端而非尾部,省去最後的 reverse 步驟。但 string 的前端插入是 O(k) 操作(k 為當前長度),總時間為 O(k²)。對於此題 k 極小(最多 7 位),差異可忽略。
columnNumber-- 這一步?如果是標準的 0-indexed 26 進位(A=0),算法會如何不同?