力扣 393. UTF-8 编码验证

最新推荐文章于 2022-03-14 15:58:56 发布

三更鬼

最新推荐文章于 2022-03-14 15:58:56 发布

阅读量244

点赞数 1

文章标签： leetcode 算法动态规划

本文链接：https://blog.csdn.net/csdn_muxin/article/details/123459308

版权

该博客讨论了一种算法，用于检查给定的字节序列是否符合UTF-8编码规范。通过定义两个掩码，可以判断首字节和后续字节是否合法。算法首先确定编码的长度，然后验证所有字节是否符合UTF-8编码规则。如果发现不合法的编码，立即返回false，否则继续检查直至序列结束，最后返回true表示整个序列都是有效的UTF-8编码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode-cn.com/problems/utf-8-validation/

大致题意：
给一个数组，每个元素表示一个字节的二进制数。检测给定的数组元素的二进制是不是标准的 UTF-8 编码

UTF-8 编码分为两种，一种是只占一个字节的，以 0 开头；一种是多个字节的，以 1 开头，并且第一个字节高位连续的 1 的个数，表示这个编码所占的字节数（最大为 4），后面的字节以 10 开头

思路

遍历数组，根据当前 UTF-8 编码开头字节判断该编码的长度，然后根据长度再判断后面连着的元素是不是合格编码

具体实现时，可以使用两个 mask 来进行验证，一个 mask1 表示 2⁷，一个 mask2 表示 2⁷+2⁶
将编码首字节与 mask1 进行与操作可以判断编码是否只占一个字节；将长度大于 1 的编码后序字节与 mask2 进行与操作可以判断是否合格

代码：

public class ValidUtf8 {
    int MASK1 = 1 << 7;
    int MASK2 = (1 << 7) + (1 << 6);
    public boolean validUtf8(int[] data) {
        int n = data.length;
        // 数组遍历的索引
        int idx = 0;
        while (idx < n) {
            // 获取编码首字节
            int num = data[idx];
            // 获取编码长度
            int len = getLen(num);
            // 若长度不合格，直接返回 false
            if (len < 0 || len + idx > n) {
                return false;
            }
            // 长度大于 1，则对后续字节进行验证
            for (int i = idx + 1; i < idx + len; i++) {
                if (!isValid(data[i])) {
                    return false;
                }
            }
            // 更新索引
            idx += len;
        }
        return true;
    }

    // 获取编码长度
    public int getLen(int num) {
        // 与 MASK1 与操作结果为 0，表示长度为 1
        if ((num & MASK1) == 0) {
            return 1;
        }
        int n = 0;
        int mask = MASK1;
        // 获取高位连续的 1 的个数
        while ((num & mask) != 0) {
            n++;
            // 若长度大于 4，不合格
            if (n > 4) {
                return -1;
            }
            mask >>= 1;
        }
        // 若高位的 1 只有一个，不合格
        return n >= 2 ? n : -1;
    }

    // 验证长度大于 1 的编码后续字节是否合格
    public boolean isValid(int num) {
        return (num & MASK2) == MASK1;
    }
}