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)``。