0393. UTF-8 Validation¶
题目信息¶
- 题号:
0393
- 难度:
Medium
- 主题:
字节序列、UTF-8 前缀、连续字节、完整消费
- 原题:
- 重点:
字符长度只能为 1 到 4 字节、首字节决定后续数量、连续字节必须以二进制
10开头、序列不能残缺
题目重述¶
给定整数数组 data,每个整数位于 [0, 255],表示一个八位字节。判断整个字节序列是否符合题目规定的 UTF-8 编码格式:单字节字符的首位为 0;长度为 n 的多字节字符,其首字节前 n 位为 1、下一位为 0,其中 n 只能是 2、3 或 4;后续每个字节都必须以二进制前缀 10 开头。
数组长度位于 [1, 2 * 10^4]。每个字节必须恰好属于一个完整字符,不能出现孤立连续字节、声明五字节以上字符的首字节,或在数组结束时仍缺少连续字节。题目只按上述位模式验证,不要求返回解码后的字符。
自建示例¶
完整的三字节字符:
输入:data = [226,130,172]
输出:true
解释:226 的二进制以 1110 开头,表示还需要两个连续字节;130 和 172 都以 10 开头。
多字节字符在结尾残缺:
输入:data = [240,162,138]
输出:false
解释:240 声明一个四字节字符,但数组只提供了两个后续字节,还缺少一个连续字节。
用 remaining 表示当前字符还需几个连续字节¶
从左到右读取字节。若当前没有等待连续字节,则根据首字节的前缀判断字符长度:0 表示单字节,110、1110、11110 分别表示还需 1、2、3 个字节;其他前缀均非法。若正在等待,当前字节必须满足 10xxxxxx,通过后将剩余数减一。
数组结束时 remaining 必须为零,否则最后一个字符不完整;孤立的连续字节也会在 remaining == 0 时无法匹配任何首字节格式。
C++ 实现¶
class Solution {
public:
bool validUtf8(std::vector<int>& data) {
int remaining = 0;
for (int byte : data) {
if (remaining == 0) {
if ((byte & 0x80) == 0) {
continue;
} else if ((byte & 0xE0) == 0xC0) {
remaining = 1;
} else if ((byte & 0xF0) == 0xE0) {
remaining = 2;
} else if ((byte & 0xF8) == 0xF0) {
remaining = 3;
} else {
return false;
}
} else {
if ((byte & 0xC0) != 0x80) return false;
--remaining;
}
}
return remaining == 0;
}
};
代码分析¶
首字节只负责建立“还需几个字节”的状态,连续字节只负责消耗状态;掩码 0xF8 也会拒绝五字节及更长前缀。每个字节只检查一次,时间复杂度为 O(n),额外空间为 O(1)。