久违的LeetCode每日一题又回来啦！，这一次是简单题！虽然表面上是普通题！来看题目！LeetCode 393. UTF-8 编码验证

题目

给定一个表示数据的整数数组data，返回它是否为有效的 UTF-8 编码。

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

  1. 对于 1 字节 的字符，字节的第一位设为 0 ，后面 7 位为这个符号的 unicode 码。
  2. 对于 n 字节 的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 unicode 码。
  3. 这是 UTF-8 编码的工作方式：
    1
    2
    3
    4
    5
    6
    7
    Char. number range  |        UTF-8 octet sequence
       (hexadecimal)    |              (binary)
    --------------------+---------------------------------------------
    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

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

示例

示例 1：

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

示例 2：

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

题解

先来读懂题目！data 中的每一个整数元素都代表着一个字节，题目要求我们判别用整数数组 data 来表示的一段编码流是否符合 UTF-8 编码标准， 先来说明 UTF-8 编码标准。

  1. 作为一个 1 字节 字符的编码，前 1 位不能为 1 ，例如 0100 0000 、 0100 1111.
  2. 作为一个 n 字节 字符的编码，第一个字节的编码的前 n 位必须为 1 ，且第 n+1 位必须为 0 ，而后 n-1 个字节的编码必须是 10 开头， 例如 1110 0000 1000 0000 1011 0000
  3. UTF-8 编码最多只存在 4 字节字符。

乍一看，我去怎么要搞二进制，心里就开始盘算起D转B那些个不想回忆的东西；不过当真正看懂题目后，其实是非常简单的，只要数组data没有以下提到的几个条件，那么它就是合规范的 UTF-8 编码。

  1. 存在与前后字节无关系的前两位为 10 的字节，例如 1100 1000 1000 1000 1000 0000（前两个字节的编码为一个 2 字节 编码）。
  2. 存在作为一个 n 字节 编码的第二、三、四字节中一个字节及以上非 10 开头，例如 1110 0000 1000 0000 1110 0000 或 1110 0000 0000 0000 1000 0000 。
  3. 存在作为一个 n 字节 编码却缺失字节，例如 1100 0000 (data.size()==1)。
  4. 存在从前往后数有超过五位数为1的单个字节，例如 1111 1000 。

如果逃过了以上条件的data，那么它就一定是一串符合UTF-8编码的编码流。

在验证以上四点时，我们没必要一定将单个十进制整数元素转换成二进制再进行验证，那样计算太慢了，我们不妨反过来将几个二进制阈值手算转换为十进制进行验证。

如1111 0000转换成十进制是 240，或 1000 0000转换为十进制是 128，瞬间就变简单了有木有！ψ(｀∇´)ψ

于是让我们开始敲代码吧！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 2022/03/13 执行 8ms 超越 97.92%，内存 13.5MB 超越 88.43%

class Solution {
public:
    bool validUtf8(vector<int>& data) {
        
        int i=0;
        while(i<data.size())
        {
            int count_=1;
            if(data[i]>247) //字节超出4位即非法
                return false;
            if(data[i]<128) //1字节跳过
            {
                i++;
                continue;
            }
            if(data[i]<192) //一字节前两位10即违法
                return false;
            if(data[i]>=240) //大于1111 0000 count++
                count_++;
            if(data[i]>=224) //大于1110 0000 count++
                count_++;
            if(data[i]>=192) //大于1100 0000 count++
                count_++;
            if(count_+i>data.size()) //字节超出数组范围即非法
                return false;
            for(int j=1;j<count_;j++)
            {
                if( data[i+j]<128 || data[i+j]>=192 )  //在二三四字节前两位非10即非法
                    return false;
            }
            i+=count_;
        }
        return true;
    }
};

PS

此解法非唯一解，且不一定是最好的解法，如果您有更好的解法，欢迎在评论区中提出。