393. UTF-8 编码验证
题目描述
输入整数数组 data，每个元素只有最低 8 位有效，代表一个字节。判断这串字节是否是合法的 UTF-8 编码。合法返回 true，否则返回 false。
UTF-8 中一个字符占 1 到 4 个字节。单字节字符的最高位是 0，格式为 0xxxxxxx。
占 n 个字节（n 为 2、3 或 4）的字符：首字节最高的 n 位都是 1，紧接着一位是 0；后面跟 n - 1 个续字节，每个续字节的最高两位都是 10。其余的 x 位任意。
具体为：2 字节 110xxxxx 10xxxxxx；3 字节 1110xxxx 后接两个 10xxxxxx；4 字节 11110xxx 后接三个 10xxxxxx。整串数据必须恰好被切分成若干个合法字符。
示例 1
输入：data = [197,130,1] 输出：true
解释：字节为 11000101 10000010 00000001：一个 2 字节字符加一个 1 字节字符。
示例 2
输入：data = [235,140,4] 输出：false
解释：首字节 11101011 要求后跟两个续字节，但第三个字节 00000100 不以 10 开头。
数据范围
1 <= data.length <= 2 * 10^40 <= data[i] <= 255
解题思路
从左到右扫描，用 need 记录当前字符还缺几个续字节。need 为 0 时，当前字节必须是首字节，用右移看前缀判断字符长度并设置 need；need 大于 0 时，当前字节必须以 10 开头，然后 need 减 1。扫描结束时 need 必须为 0，否则最后一个字符不完整。
为什么正确
处理完每个字节后，已扫描部分是若干完整字符加上一个缺 need 个续字节的未完成字符。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
首字节判断要按顺序比较完整前缀：10xxxxxx 不能作为首字节，11111xxx 也非法；循环结束后别忘了检查 need == 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def validUtf8(self, data: List[int]) -> bool:
need = 0
for x in data:
if need == 0:
if x >> 7 == 0:
continue
elif x >> 5 == 0b110:
need = 1
elif x >> 4 == 0b1110:
need = 2
elif x >> 3 == 0b11110:
need = 3
else:
return False
else:
if x >> 6 != 0b10:
return False
need -= 1
return need == 0class Solution {
public boolean validUtf8(int[] data) {
int need = 0;
for (int x : data) {
if (need == 0) {
if (x >> 7 == 0) {
continue;
} else if (x >> 5 == 0b110) {
need = 1;
} else if (x >> 4 == 0b1110) {
need = 2;
} else if (x >> 3 == 0b11110) {
need = 3;
} else {
return false;
}
} else {
if (x >> 6 != 0b10) {
return false;
}
need--;
}
}
return need == 0;
}
}class Solution {
public:
bool validUtf8(vector<int>& data) {
int need = 0;
for (int x : data) {
if (need == 0) {
if (x >> 7 == 0) {
continue;
} else if (x >> 5 == 0b110) {
need = 1;
} else if (x >> 4 == 0b1110) {
need = 2;
} else if (x >> 3 == 0b11110) {
need = 3;
} else {
return false;
}
} else {
if (x >> 6 != 0b10) {
return false;
}
need--;
}
}
return need == 0;
}
};func validUtf8(data []int) bool {
need := 0
for _, x := range data {
if need == 0 {
if x>>7 == 0 {
continue
} else if x>>5 == 0b110 {
need = 1
} else if x>>4 == 0b1110 {
need = 2
} else if x>>3 == 0b11110 {
need = 3
} else {
return false
}
} else {
if x>>6 != 0b10 {
return false
}
need--
}
}
return need == 0
}var validUtf8 = function(data) {
let need = 0;
for (const x of data) {
if (need === 0) {
if (x >> 7 === 0) {
continue;
} else if (x >> 5 === 0b110) {
need = 1;
} else if (x >> 4 === 0b1110) {
need = 2;
} else if (x >> 3 === 0b11110) {
need = 3;
} else {
return false;
}
} else {
if (x >> 6 !== 0b10) {
return false;
}
need--;
}
}
return need === 0;
};function validUtf8(data: number[]): boolean {
let need = 0;
for (const x of data) {
if (need === 0) {
if (x >> 7 === 0) {
continue;
} else if (x >> 5 === 0b110) {
need = 1;
} else if (x >> 4 === 0b1110) {
need = 2;
} else if (x >> 3 === 0b11110) {
need = 3;
} else {
return false;
}
} else {
if (x >> 6 !== 0b10) {
return false;
}
need--;
}
}
return need === 0;
}