393. UTF-8 编码验证

难度中等108收藏分享切换为英文接收动态反馈

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

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

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

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

   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数组指针：

输入： 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 <= data.length <= 2 * 104
  • 0 <= data[i] <= 2二进制怎么算55

模拟

根据题意进行模拟即可。

  1. 先计算出 data[i] 占用几二进制转化为十进制个字节。
    • 计算过程我采用了 if 判断，详情可见 calculationByte() 函数
  2. 计算出占 n 个字节后，按照字节数依次验证后面 n 个。

在这个过程中需要注意边界条件

  • 数组中剩余的字节数是否满足编码个数
  • 不满足编码条件的情况要及时 return 
#include<iostream>
#include<vector>
#include<stack>
#include <algorithm>
using namespace std;
class Solution {
    const int oneMask = 1 << 7;
    const int towMask = oneMask + (1 << 6);
    const int thereMask = towMask + (1 << 5);
    const int fourMask = thereMask + (1 << 4);
public:
    bool validUtf8(vector<int>& data) {
        if (data.empty()) return false;
        int i = 0;
        while (i < data.size())
        {
            int b = calculationByte(data[i]);
            if (!_validUtf8(data, i, i + b - 1)) return false;
            i += b;
        }
        return true;
    }
     bool _validUtf8(vector<int>& data, int left, int right) {
         if (left > right) return false;
         if (left == right) return true;
         if (right >= data.size()) return false;
         for (int i = left + 1; i <= right; i++)
         {
            int value = data[i];
            if ((value & oneMask) != oneMask) return false;
            if (((value & (1<<6)) != 0)) return false;
         }
         return true;
     }
     int calculationByte(int value) {
        int ret = value & oneMask;
        if (ret == 0) return 1;
        ret = value & towMask;
        if ((ret == towMask) && ((value & (1 << 5)) == 0)) return 2;
        ret = value & thereMask;
        if ((ret == thereMask) && ((value & (1 << 4)) == 0)) return 3;
        ret = value & fourMask;
        if ((ret == fourMask) && ((value & (1 << 3)) == 0)) return 4;
        return -1;
     }
};