LC393.UTF-8编码验证 - 图1

思路：位运算

  • 不要转化成字符串去判断，反复折磨，没必要
  • 位运算是最正的解法
  • 此题的逻辑是比较复杂的，可以分成几步来进行
    1. 判断当前int的前缀情况，如果是0，说明是1字节的字符;如果有n个1，说明其后有 n - 1 个后续位置（往后读 n - 1 个 int）
    2. 对于后面的 n - 1 个后续位置，分别检查是不是10开头的，是10开头，就说明符合，否则不符合，返回false
    3. 如果一直能读到最后一个位置，说明整个序列没问题，否则有错

  • 关于位运算有两点：

    1. 利用mask1去读有几个前缀的1 

      1. mask1 = (1 << 7)
      2. while (cur_num & mask1) == mask1:
      3. cur_num <<= 1
      4. distance += 1

    2. 利用mask1 和 mask2 去判断是不是10开头的，mask技巧是常见的，也是本题精要所在。按位与运算通过1去判定既定位置是不是1，按位或运算通过0去判断既定位置是不是0。

      1. mask1 = (1 << 7)
      2. mask2 = (1 << 7) + (1 << 6) - 1
      3. return (cur_num & mask1 == mask1) and (cur_num | mask2 == mask2)

      代码：

  1. class Solution:
  2.     """
  3.     此题的逻辑是比较复杂的，可以分成几步来进行
  4.     1. 判断当前int的前缀情况，如果是0，说明是1字节的字符;如果有n个1，说明其后有 n - 1 个后续位置（往后读 n - 1 个 int）
  5.     2. 对于后面的 n - 1 个后续位置，分别检查是不是10开头的，是10开头，就说明符合，否则不符合，返回false
  6.     3. 如果一直能读到最后一个位置，说明整个序列没问题，否则有错
  8.     关于位运算有两点：
  9.     1. 利用mask1去读有几个前缀的1
  10.     2. 利用mask1 和 mask2 去判断是不是10开头的
  11.     """
  12.     def validUtf8(self, data: List[int]) -> bool:
  13.         mask1 = (1 << 7)
  14.         mask2 = (1 << 7) + (1 << 6) - 1
  15.         len_data = len(data)
  17.         def getDistance(cur_num: int) -> int:
  18.             # 说明第一位是0![](https://img-blog-01.oss-cn-shanghai.aliyuncs.com/img/20220324002744.png)
  19.             if (cur_num & mask1) == 0:
  20.                 return 0
  22.             # 如果不是0
  23.             distance = 0
  24.             while (cur_num & mask1) == mask1:
  25.                 cur_num <<= 1
  26.                 distance += 1
  28.             return distance if 2 <= distance <= 4 else -1
  30.         def checkPrefix(cur_num: int) -> bool:
  31.             return (cur_num & mask1 == mask1) and (cur_num | mask2 == mask2)
  33.         begin_pos = 0
  34.         while begin_pos < len_data:
  35.             next_dis = getDistance(data[begin_pos])
  36.             if next_dis == 0:
  37.                 begin_pos += 1
  38.             elif next_dis == -1:
  39.                 return False
  40.             else:
  41.                 if begin_pos + next_dis > len_data:
  42.                     return False
  43.                 for i in range(begin_pos + 1, begin_pos + next_dis):
  44.                     if not checkPrefix(data[i]):
  45.                         return False
  46.                 begin_pos += next_dis
  48.         return True