【leetcode】393 UTF-8 Validation

发表于 | 分类于 ，

验证 utf-8 编码


描述

UTF8中的字符长度可以是1到4个字节，符合以下规则：

对于1字节字符，第一位为0，后跟其unicode代码。
对于n字节字符，前n位全部为1，n + 1位为0，后跟n-1字节，最高有效2位为10。
这是UTF-8编码的工作方式：
（十六进制）| （二进制）
——————– + —————————– —————-
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
给定表示数据的整数数组，返回它是否是有效的utf-8编码。

注意：
输入是一个整数数组。只有每个整数的最低8位用于存储数据。这意味着每个整数仅代表1个字节的数据。

样例

1
2
输入: data = [197,130,1]
输出: true

思路

需要明确本题要求的东西是什么，要验证 utf 的有效性。一段 utf 编码可以由 1 到 4 个字节组成，若是一个字节，第一个 bit 位必须是 0 。若为两个字节，第一个字节的前三位必须是 110，后面一个字节的开头必须是 10 。若为 3 个字节，第一个字节的前4位必须是 1110 ，后面 2 个字节都以 10 开头。若为 4 个字节，第一个字节必须以 11110 开头，后面紧跟的 3 个字节以 10 开头。首先想根据第一个数计算得出后续 10 开头的个数，然后判断每段是否都满足条件。遇到一个问题，可能给的数字集合不止一个：

[ 240,162,138,147,145 ],
[ 11110000,10100100,10001010,10010011,10010001]

这组数字是不满足条件的，前四个没有问题，但是最后一个还是一个10开头，这就有问题了，它应该从0 开始，因为它是一个字节的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool validUtf8(vector<int>& data) {
        int cnt = 0;
        for (int num : data) {
            if (cnt == 0) {
                if ((num & 0x80) == 0x00) { cnt = 0; }
                else if ((num & 0xe0) == 0xc0) { cnt = 1; }
                else if ((num & 0xf0) == 0xe0) { cnt = 2; }
                else if ((num & 0xf8) == 0xf0) { cnt = 3; }
                else { return false; }
            }
            else {
                if ((num & 0xc0) != 0x80) { return false; }
                cnt--;
            }
        }
        return !cnt;
    }
};

参考

原题链接
参考代码链接