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