LeetCode刷题实战393：UTF-8 编码验证-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 UTF-8 编码验证，我们先来看题面：

https://leetcode-cn.com/problems/utf-8-validation/

示例

示例 1：
data = [197, 130, 1], 表示 8 位的序列: 11000101 10000010 00000001.
返回 true 。
这是有效的 utf-8 编码，为一个2字节字符，跟着一个1字节字符。

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

解题

首先需要读懂题目，分析题目可以知道我们模拟整个过程即可，首先我们判断当前位置的数字对应的二进制的第7位是否是1，如果为0那么continue即可，说明是一字节的字符不用管，如果为1的时候那么我们就需要计算当前的二进制数字从最高位连续的1的数目，如果k等于1或者大于4都是不满足条件的，因为utf-8编码最多是四个字节字符，当前对应的二进制数字从最高位连续的1的数目k大于1小于等于4的时候那么计算后面的k - 1个数字对应的二进制数字是否满足条件即可，也即判断后面k - 1个数字对应的二进制数字的第7位与第6位是否是10如果不是那么返回False，当满足条件的时候更新一下循环的变量判断后面的数字是否满足条件即可。

from typing import List
 
class Solution:
    # 获取x的二进制表示从右开始计算的第k位数字
    def get(self, x: int, k: int):
        return x >> k & 1
 
    def validUtf8(self, data: List[int]) -> bool:
        i = 0
        while i < len(data):
            # 获取当前这个数字的二进制表示中第七位是否是1判断是几个字节
            if self.get(data[i], 7) == 0:
                i += 1
                continue
            k = 0
            # 计算当前对应的二进制数字最高位开始连续的1的数目
            while k <= 4 and self.get(data[i], 7 - k): k += 1
            if k == 1 or k > 4: return False
            # k表示后面需要有k - 1个10的
            for j in range(k - 1):
                t = i + j + 1
                # 注意需要判断下面这一句代码
                if t >= len(data): return False
                if t < len(data):
                    if not (self.get(data[t], 7) == 1 and self.get(data[t], 6) == 0): return False
            i = i + k
        # 更新下一次需要判断的数字
        return True