題幹與適用場景
這是一道位元運算與字元編碼題。輸入是位元組陣列，不是已解碼的 Unicode 字串；需要判斷每個程式碼點使用 1 到 4 個位元組，並拒絕截斷或格式錯誤的序列。LeetCode 393 使用相同約束：陣列長度最多 2 * 10^4，每個整數只取最低 8 位。RFC 3629 規定 UTF-8 的 1 到 4 位元組格式及合法純量值範圍。
面試官考察點
- 能否從首位元組位元模式推導後續位元組數量。
- 能否用
10xxxxxx嚴格驗證延續位元組，而不是只檢查陣列長度。 - 能否拒絕多餘延續位元組、截斷輸入與 5 位元組以上起始模式。
- 能否給出
O(n)時間、O(1)額外空間的單次掃描實作。
回答前需要釐清的問題
先確認輸入是否保證每個元素已在 0..255；若沒有，應先拒絕越界值。再確認題目只要求判斷位元組格式，還是也要拒絕 UTF-8 中禁止的過長編碼、代理區與超過 U+10FFFF 的純量值。LeetCode 版本主要考察位元組格式；生產解析器還應依 RFC 3629 做更嚴格的純量值檢查。
30 秒回答框架
我會維護 remaining，表示目前字元還需要多少延續位元組。讀到首位元組時，依最高位元模式決定 0、1、2、3 個延續位元組；讀到延續位元組時必須滿足 (byte & 0b11000000) === 0b10000000，然後遞減計數。任何非法首位元組、意外延續位元組或掃描結束時 remaining !== 0 都回傳 false；整個過程只保留一個計數器。
分步驟深入解答
1. 辨識首位元組模式
0xxxxxxx 是單位元組字元；110xxxxx、1110xxxx、11110xxx 分別需要 1、2、3 個延續位元組。可以用遮罩判斷前綴：先檢查 0x80，再檢查 0xE0、0xF0，最後檢查 0xF8。如果 0xF8 仍然非零，代表 5 位元組或更長的起始模式，應拒絕。
2. 在線驗證延續位元組
掃描時若 remaining > 0，目前位元組只能符合 10xxxxxx。驗證通過後遞減計數；若讀到 ASCII 首位元組或另一個多位元組首位元組，立即失敗。如此不需回退或切片，截斷序列會在輸入結束時被發現。
3. 參考實作
isValidUtf8(bytes):
remaining = 0
for byte in bytes:
if byte < 0 or byte > 255: return false
if remaining > 0:
if (byte & 0b11000000) != 0b10000000: return false
remaining -= 1
continue
if (byte & 0b10000000) == 0:
remaining = 0
else if (byte & 0b11100000) == 0b11000000:
remaining = 1
else if (byte & 0b11110000) == 0b11100000:
remaining = 2
else if (byte & 0b11111000) == 0b11110000:
remaining = 3
else:
return false
return remaining == 04. 處理生產級嚴格性
僅依前綴計數會接受某些 overlong encoding，例如用 3 個位元組表示原可用 1 個位元組表示的值，也可能接受代理區。生產解析器應累計程式碼點並檢查最小值、代理區間與 U+10FFFF 上限；還要明確是否允許 BOM。面試中應先指出題目邊界，再說明如何擴充，而不是把額外規則悄悄混入基礎實作。
5. 測試與複雜度
測試至少涵蓋 [197,130,1] 為 true、[235,140,4] 為 false、孤立延續位元組 [128]、截斷的 [226,130]、5 位元組起始 [248,128,128,128,128] 與空陣列。掃描每個位元組一次，時間複雜度 O(n)，額外空間 O(1)；n 為陣列長度。
高品質示範回答
我把問題分成首位元組辨識與延續位元組驗證兩種狀態。首位元組依 0xxxxxxx、110xxxxx、1110xxxx、11110xxx 將 remaining 設為 0、1、2、3；在延續狀態只接受 10xxxxxx 並遞減計數。遇到 5 位元組起始、意外延續位元組、越界元素或掃描結束仍有未完成字元時回傳 false。實作是單次 O(n) 掃描、O(1) 空間；若用於生產，還要累計程式碼點以拒絕 overlong、代理區與超過 U+10FFFF 的值。
常見錯誤
- 只統計連續位元組數量，不驗證每個延續位元組的
10前綴。 - 把
111110xx當成合法的 5 位元組格式。 - 輸入結束時忘記檢查
remaining，誤把截斷序列判為合法。 - 依賴語言字串解碼器，無法展示位元模式與錯誤位置。
- 將 LeetCode 的格式判斷與 RFC 的純量值約束混為一談。
- 把
byte當成有號整數，位元運算前未規範到0..255。
追問及應對
如何回傳第一個錯誤位置？
讓函式回傳 {valid, errorIndex, reason}；發現非法首位元組、非法延續位元組或結束時仍有 remaining 時記錄目前索引。保持掃描狀態不變，呼叫方可據此標示原始位元組。
如何支援串流分塊輸入？
把 remaining 與已累計的程式碼點狀態放入解析器物件，在每個 chunk 結束時保留未完成狀態。只有收到後續 chunk 並完成字元後才報告成功；串流結束時 remaining != 0 仍是截斷錯誤。
為什麼不能只用正規表示式？
正規表示式可以表達部分前綴規則，但對跨 chunk 狀態、錯誤索引與純量值約束不如狀態機清楚。線上計數器能以常數空間處理任意長度輸入，也更容易擴充嚴格驗證。
怎樣避免 overlong encoding？
讀取首位元組時記錄序列長度與累計值，完成後檢查該值是否達到該長度的最小編碼範圍；同時拒絕 0xD800..0xDFFF 與大於 0x10FFFF 的值。
如何處理惡意超長輸入？
讓上層設定最大位元組數、逾時與錯誤取樣策略；解析器本身保持 O(1) 狀態，遇到首個確定錯誤即可短路，避免為錯誤資料配置額外緩衝區。