题干与适用场景
这是一道位运算与字符串编码题。输入是字节数组，不是已经解码的 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) 状态，遇到首个确定错误即可短路，避免为错误数据分配额外缓冲区。