LeetCode 393. UTF-8 编码验证
目录
题目描述
题意分析
给一个整数数组
data，每个整数代表一个字节，判断整个数组是否构成一段合法的 UTF-8 编码，返回布尔值。
题面里有一条极易被忽略的约束：每个整数只有低 8 位是有效数据，高位可能是任意值（因为整数在这里只是字节的容器）。所以每个元素在参与判断之前都必须先与
0xFF做按位与，否则右移得到的前缀会混入高位垃圾，判断全错。
UTF-8 的规则本身题目已经给出，归纳起来是：一个字符占 1 到 4 个字节；1 字节字符的首字节形如
0xxxxxxx；n字节字符（n为 2、3、4）的首字节以n个 1 加一个 0 开头，即110xxxxx、1110xxxx、11110xxx；而所有续字节一律形如10xxxxxx。也就是说，只看一个字节的高位前缀就能确定它的角色，这是本题所有判断的依据。
「首字节自己声明了这个字符还要跟几个续字节」是一个很强的结构信号：它意味着整个数组可以被一趟从左到右扫描完，扫描过程中只需要记住「当前还欠几个续字节」这一个整数即可，不需要回头，也不需要额外容器。这类「读一个头部、按头部声明继续读若干体」的形状，在协议解析里非常常见。
边界要盯住三处：数组末尾恰好把某个多字节字符截断了（还欠续字节就结束），必须判为非法；某个字节以
11111xxx开头（声称 5 字节或更长），UTF-8 不允许，必须判为非法；在还欠续字节时遇到的字节若不是10开头（哪怕它本身是个合法的首字节），也必须判为非法。
解法：记录还需要的续字节数量
核心思路
一个想当然的做法是把整个数组按
10开头与否切成若干段，再逐段校验长度。这条路要处理很多分组边界，而且「一个合法首字节紧跟在另一个未完成字符后面」这种错误很难在分段视角下被自然发现。
关键观察是：任何时刻，解析器的全部状态只有一个数字——当前字符还欠几个续字节。因为首字节一旦读到，字符总长度就完全确定了；此后要做的只是核对接下来的若干个字节是不是
10开头，不需要记住它们的内容，也不需要记住这是第几个字符。状态空间小到只有{0, 1, 2, 3}四个值，于是一个int就够了，这就是所谓的有限状态机退化成计数器。
于是扫描逻辑分成两种互斥的情形。
remaining == 0时，当前字节必须是某个字符的首字节：按高位前缀分类，0xxxxxxx是单字节字符（不欠任何续字节），110xxxxx欠 1 个，1110xxxx欠 2 个，11110xxx欠 3 个，其余前缀（包括10xxxxxx这种孤立的续字节，以及11111xxx这种过长声明）一律非法。remaining > 0时，当前字节必须是10xxxxxx，核对通过就把remaining减一。
不变量：每处理完一个字节，
remaining恒等于「为了让已扫描部分构成若干个完整字符，还必须紧接着出现的续字节个数」。初始remaining = 0表示「已扫描部分（空）本身就是完整的」；读首字节时按声明置数，读续字节时减一，不变量得以维持。
循环结束后的返回值直接由不变量给出：
remaining == 0说明所有字符都收尾了，合法；大于 0 说明最后一个字符被数组末尾截断，非法。
前缀判断用右移比较常数实现：
b >> 7 == 0判0xxxxxxx，b >> 5 == 0b110 == 6判两字节首字节，b >> 4 == 0b1110 == 14判三字节，b >> 3 == 0b11110 == 30判四字节，b >> 6 == 0b10 == 2判续字节。每个判断都把不关心的低位全部移走，只留下前缀本身，比用掩码加比较更短。
解题步骤
remaining初始化为 0：表示还没有任何未完成的字符，下一个字节必须是首字节。每个元素先做
b = num & 255：题目只保证低 8 位有效，高位可能有垃圾。不做这一步，num >> 7会把高位内容带进来，num = 256（低 8 位全 0，本应是合法单字节）会被判成非法。按
remaining == 0与否分成两条互斥分支：状态决定了当前字节该被当作首字节还是续字节，两种角色的判据完全不同，混在一起写必然出错。首字节分支按前缀从短到长依次判断：先判
b >> 7 == 0（单字节），再判>> 5 == 6、>> 4 == 14、>> 3 == 30。顺序不能乱——如果先判b >> 3 == 30，一个0xxxxxxx的字节右移 3 位得到的值范围是 0 到 15，不会误命中，但11110xxx与111110xx在更粗的前缀判断下会互相干扰，按前缀长度递增的顺序判断最不容易漏。单字节情形直接
continue：它不欠任何续字节，remaining保持 0，下一个字节仍按首字节处理。所有其余前缀走
else返回false：这一条同时封杀了两类错误——10xxxxxx出现在不该出现的位置（孤立续字节），以及11111xxx这种声明 5 字节及以上的前缀。少了这个兜底分支，非法输入会被静默放过。续字节分支只校验
b >> 6 == 2，通过则remaining--：续字节的低 6 位是数据，内容任意，不需要检查；唯一要确认的就是高两位是10。返回
remaining == 0：这是「末尾截断」的唯一检测点。直接return true会漏掉[11000010]这类只有首字节没有续字节的输入。以
data = [197, 130, 1]走一遍。
197 & 255 = 197，二进制11000101。remaining == 0，走首字节分支：b >> 7 = 1不为 0；b >> 5 = 0b110 = 6命中，说明这是一个两字节字符的首字节，置remaining = 1。
130 & 255 = 130，二进制10000010。remaining == 1 > 0，走续字节分支：b >> 6 = 0b10 = 2，校验通过，remaining减为 0。此时两字节字符11000101 10000010完整。
1 & 255 = 1，二进制00000001。remaining == 0，走首字节分支：b >> 7 = 0命中，是一个单字节字符，continue。循环结束，
remaining == 0，返回true。再看反例
data = [235, 140, 4]。235是11101011，b >> 4 = 0b1110 = 14，是三字节首字节，remaining = 2。140是10001100，b >> 6 = 2通过，remaining = 1。4是00000100，此时remaining > 0要求它必须是10开头，而4 >> 6 = 0，校验失败，立刻返回false。注意4本身是一个完全合法的单字节字符——但它出现在了一个未完成的三字节字符中间，所以整体非法。这正是「必须按状态分支判断」而不是「逐字节独立判断」的原因。最后看末尾截断的
data = [194]：11000010置remaining = 1后数组就结束了，循环外的remaining == 0判断给出false，正确。
代码实现
class Solution {
public boolean validUtf8(int[] data) {
int remaining = 0;
for (int num : data) {
int b = num & 255;
if (remaining == 0) {
if ((b >> 7) == 0) {
continue;
} else if ((b >> 5) == 6) {
remaining = 1;
} else if ((b >> 4) == 14) {
remaining = 2;
} else if ((b >> 3) == 30) {
remaining = 3;
} else {
return false;
}
} else {
if ((b >> 6) != 2) {
return false;
}
remaining--;
}
}
return remaining == 0;
}
}
func validUtf8(data []int) bool {
remaining := 0
for _, num := range data {
b := num & 255
if remaining == 0 {
if b>>7 == 0 {
continue
} else if b>>5 == 6 {
remaining = 1
} else if b>>4 == 14 {
remaining = 2
} else if b>>3 == 30 {
remaining = 3
} else {
return false
}
} else {
if b>>6 != 2 {
return false
}
remaining--
}
}
return remaining == 0
}
复杂度分析
- 时间复杂度：$O(n)$，
n是数组长度。每个字节恰好被访问一次，内部只做常数次移位和比较，没有回退也没有嵌套循环。这是下限——判断合法性必须看完每一个字节，因为最后一个字节就可能让整体非法。- 空间复杂度：$O(1)$。只有
remaining和b两个整数，与输入规模无关。相比「先分组再校验」的思路，这里连一个存放分组结果的容器都不需要，因为状态被压缩成了一个计数器。
关键点总结
- 「读一个头部、按头部声明再读若干个体」的协议解析题，都可以用「还欠几个」的计数器一趟扫完。状态空间越小越好，本题压到了一个 0 到 3 的整数，这是解法优雅的根源。
- 判断字节角色只看高位前缀，用右移把不关心的低位移走后与常数比较，比构造掩码再按位与更简洁。写的时候把二进制形式写在注释或心里对齐一遍，
6、14、30、2这几个魔数就不再难记。- 只要题目说「只用低 8 位」，就必须先
& 0xFF再做任何移位。这类「输入容器比实际数据宽」的约定在位运算题里很常见，漏掉一次就全盘皆错。- 循环结束后的收尾判断（本题的
remaining == 0）和循环内的非法返回同等重要。状态机类题目的正确性由「过程合法」与「终态合法」两部分共同保证，只写前者是最常见的失分点。- 面试中被追问「还有哪些 UTF-8 规则没验」时，可以指出真实的 UTF-8 还禁止过长编码（比如用两字节表示本该单字节的码点）和代理区码点，但本题只要求校验前缀结构。能划清「题目要求」与「真实规范」的边界，比多写一堆无关校验更受认可。
易错点总结
- 不做
num & 255：data = [256]的低 8 位是00000000，本应是合法单字节；直接算256 >> 7 = 2不为 0，接着256 >> 5 = 8、>> 4 = 16、>> 3 = 32都不命中，返回false。- 循环结束后直接
return true：data = [194]声明了两字节字符却没有续字节，会被误判为合法。- 不检查 5 字节及以上前缀：
data = [248]即11111000，若没有else return false的兜底而是默认当作合法首字节，会漏掉这个非法输入。- 续字节判断写成
b >> 6 == 3：data = [197, 130]中130 >> 6 = 2，条件不成立而返回false，把合法输入判成非法。- 在
remaining > 0时仍按首字节分支处理：data = [235, 140, 4]中的4是合法单字节，若不区分状态就会被放行，最终返回true，而正确答案是false。- 首字节分支里把
remaining设成字符总长度而不是续字节数：data = [197, 130]中remaining被设成 2，扫完130后还剩 1，循环结束返回false。- 单字节情形忘记
continue而落入后续分支：data = [1]中1 >> 7 == 0命中后若不跳过，接着判1 >> 5 == 6不成立、一路走到else返回false。- 续字节校验通过后忘记
remaining--：data = [197, 130, 1]中remaining永远停在 1，1这个字节被当成续字节校验失败，返回false；即便侥幸不失败，末尾判断也会因为remaining != 0而返回false。- 用
>>>之外的算术右移处理负数输入：若题目变体允许传入负整数表示字节，Java 的>>会做符号扩展，-1 >> 7得到-1而不是1；先做& 255恰好也顺带消除了这个隐患，这也是那一步不能省的另一个理由。- 误以为
10xxxxxx在任何位置都合法：data = [130]是一个孤立的续字节，没有对应的首字节，正确答案是false；若首字节分支缺少兜底返回，这个输入会被当成合法。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 468. 验证IP地址 | 中等 | 同为格式校验，规则分支更多且要处理分段与进制，考察分类讨论的完备性 |
| 65. 有效数字 | 困难 | 典型的有限状态机题，状态数远多于本题，适合对照「状态能否压成计数器」 |
| 20. 有效的括号 | 简单 | 同样靠「计数或栈 + 终态校验」判定合法性，收尾时也必须检查是否有未闭合项 |
| 165. 比较版本号 | 中等 | 手写分段解析并逐段比较，重点在补位与前导零处理而非位运算 |
| 8. 字符串转换整数 (atoi) | 中等 | 按阶段解析输入并随时判断非法，还需处理溢出边界 |
| 191. 位1的个数 | 简单 | 位运算基本功，练习移位与掩码取位，是本题前缀判断的底层技能 |
| 405. 数字转换为十六进制数 | 简单 | 按 4 位一组做移位与掩码，是「只取某几位」这一手法的直接应用 |
| 38. 外观数列 | 中等 | 同为「读一段、按声明生成下一段」的结构，可对照编码与解码两个方向 |