0393. UTF-8 编码验证

ITCharge大约 3 分钟

---

0393. UTF-8 编码验证

标签：位运算、数组
难度：中等

题目链接

0393. UTF-8 编码验证 - 力扣

题目大意

描述：

给定一个表示数据的整数数组 $data$ 。

要求：

返回它是否为有效的 $UTF-8$ 编码。

$UTF-8$ 中的一个字符可能的长度为 $1$ 到 $4$ 字节，遵循以下的规则：

对于 $1$ 字节的字符，字节的第一位设为 $0$ ，后面 $7$ 位为这个符号的 $unicode$ 码。
对于 $n$ 字节的字符 ( $n > 1$ )，第一个字节的前 $n$ 位都设为 $1$ ，第 $n+1$ 位设为 $0$ ，后面字节的前两位一律设为 $10$ 。剩下的没有提及的二进制位，全部为这个符号的 $unicode$ 码。

这是 $UTF-8$ 编码的工作方式：

    Number of Bytes  |        UTF-8 octet sequence
                     |              (binary)
---------------------+--------------------------------------------
        1            |  0xxxxxxx
        2            |  110xxxxx 10xxxxxx
        3            |  1110xxxx 10xxxxxx 10xxxxxx
        4            |  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

$x$ 表示二进制形式的一位，可以是 $0$ 或 $1$ 。

说明：

注意：输入是整数数组。只有每个整数的最低 $8$ 个有效位用来存储数据。这意味着每个整数只表示 $1$ 字节的数据。
$1 \le data.length \le 2 \times 10^{4}$ 。
$0 \le data[i] \le 255$ 。

示例：

示例 1：

输入：data = [197,130,1]
输出：true
解释：数据表示字节序列: 11000101 10000010 00000001。
这是有效的 utf-8 编码，为一个 2 字节字符，跟着一个 1 字节字符。

示例 2：

输入：data = [235,140,4]
输出：false
解释：数据表示 8 位的序列: 11101011 10001100 00000100.
前 3 位都是 1 ，第 4 位为 0 表示它是一个 3 字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不以 10 开头，所以是不符合规则的。

解题思路

思路 1：逐字节验证

核心思想：根据 UTF-8 编码规则，逐字节验证数据是否符合 UTF-8 编码格式。

算法步骤：

初始化：设置索引 $i = 0$ ，遍历整个数组 $data$ 。
判断首字节类型：
- 如果 $data[i] \& 128 = 0$ ，说明是 1 字节字符， $i$ 自增 1。
- 如果 $data[i] \& 224 = 192$ ，说明是 2 字节字符，需要验证后面 1 个字节。
- 如果 $data[i] \& 240 = 224$ ，说明是 3 字节字符，需要验证后面 2 个字节。
- 如果 $data[i] \& 248 = 240$ ，说明是 4 字节字符，需要验证后面 3 个字节。
- 其他情况都是无效的首字节。
验证后续字节：对于 $n$ 字节字符，验证后面 $n-1$ 个字节是否都以 $10$ 开头（即 $data[j] \& 192 = 128$ ）。
边界检查：确保数组长度足够，不会越界访问。

思路 1：代码

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        i = 0
        n = len(data)
        
        while i < n:
            # 获取当前字节
            byte = data[i]
            
            # 判断是几字节字符
            if (byte & 128) == 0:
                # 1 字节字符：0xxxxxxx
                i += 1
            elif (byte & 224) == 192:
                # 2 字节字符：110xxxxx 10xxxxxx
                if i + 1 >= n or (data[i + 1] & 192) != 128:
                    return False
                i += 2
            elif (byte & 240) == 224:
                # 3 字节字符：1110xxxx 10xxxxxx 10xxxxxx
                if i + 2 >= n or (data[i + 1] & 192) != 128 or (data[i + 2] & 192) != 128:
                    return False
                i += 3
            elif (byte & 248) == 240:
                # 4 字节字符：11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
                if i + 3 >= n or (data[i + 1] & 192) != 128 or (data[i + 2] & 192) != 128 or (data[i + 3] & 192) != 128:
                    return False
                i += 4
            else:
                # 无效的首字节
                return False
        
        return True

思路 1：复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是数组 $data$ 的长度。每个字节最多被访问一次。
空间复杂度： $O(1)$ ，只使用了常数额外空间。