LeetCode 393. UTF-8 编码验证
题目描述
题意分析
按题面给定的字节格式，判断整个数组能否恰好分成若干完整字符，不需要还原字符内容。每项只取低 8 位；一个字符占 1 到 4 个字节，首字节决定长度，其余字节都必须以二进制
10开头。
解法：记录还需要的续字节数量
核心思路
[!blue]
用
remaining表示当前字符还缺多少个续字节。remaining == 0说明前面的字符已经完整，当前字节必须是新字符的首字节；remaining > 0则说明当前字节只能接在前一个首字节之后，不能另起一个字符。对首字节，前缀
0xxxxxxx表示单字节字符，无需续字节；前缀110xxxxx、1110xxxx、11110xxx分别表示总长为 2、3、4 字节，因此将remaining设为 1、2、3。其他前缀都不合法，包括没有首字节引领的10xxxxxx，以及超过四字节长度的前缀。代码通过右移丢弃内容位，只比较前缀：
b >> 7 == 0检查最高位为0；b >> 5 == 6、b >> 4 == 14、b >> 3 == 30分别检查110、1110、11110。这些模式互斥，不会把一个合法首字节识别为两种长度。等待续字节时，只接受
b >> 6 == 2，即最高两位为10，随后将remaining减一。降到 0 就说明该字符恰好结束，下一项可以开始新字符。若格式不符，立即返回false。这样每个字节都按当前字符所需的位置验证，且只有收齐续字节后才能开始下一个字符。数组结束时还要检查
remaining == 0，否则虽然已读字节的前缀都正确，最后一个字符仍然不完整。
解题步骤
- 初始化
remaining = 0，逐项计算b = num & 255，只保留低 8 位。- 若
remaining == 0，识别合法首字节并设置所需续字节数；单字节字符直接处理下一项，无法匹配则返回false。- 若
remaining > 0，检查当前字节是否以10开头，不符合就返回false，符合则执行remaining--。- 扫描结束后返回
remaining == 0，确认没有缺失的续字节。
代码实现
class Solution {
public boolean validUtf8(int[] data) {
int remaining = 0;
for (int num : data) {
int b = num & 255;
// 开始新字符：前缀常量分别对应二进制 0、110、1110、11110
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
// 开始新字符：前缀常量分别对应二进制 0、110、1110、11110
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)$，逐字节处理。
- 空间复杂度：$O(1)$，只保存剩余数量。
关键点总结
[!green]
remaining先决定当前字节扮演首字节还是续字节，再决定应检查哪种前缀。- 首字节给出的是字符总长度，所需续字节数要减去已经读取的首字节。
- 过程中的前缀检查与结束时的数量检查缺一不可。
易错点总结
[!yellow]
- 只检查每个字节属于某种合法前缀，不检查它出现的位置，会接受孤立续字节。
- 还欠续字节时不能接受新的首字节，即使这个首字节本身格式正确。
- 识别多字节首部时，还必须确认连续的 1 后面是 0；仅数出部分前导 1 不足以确定合法长度。
- 不能在循环正常结束后直接返回
true，末尾仍可能缺少续字节。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 717. 1 比特与 2 比特字符 | 简单 | 同样从首位模式确定接下来应消费多少位或字节，本题需要逐个验证后续字节前缀。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！