class Solution {
public:
bool validUtf8(vector<int>& data) {
}
};
393. UTF-8 编码验证
给定一个表示数据的整数数组 data ，返回它是否为有效的 UTF-8 编码。
UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：
这是 UTF-8 编码的工作方式：
Number of Bytes| UTF-8 octet sequence | (binary) --------------------+--------------------------------------------- 1 | 0xxxxxxx 2 | 110xxxxx 10xxxxxx 3 | 1110xxxx 10xxxxxx 10xxxxxx 4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x 表示二进制形式的一位，可以是 0 或 1。
注意：输入是整数数组。只有每个整数的 最低 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 * 1040 <= data[i] <= 255原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 42.2 MB, 提交时间: 2023-02-27 14:38:00
class Solution {
private static final int ONE = 1 << 7, TWO = ONE + (1 << 6);
public boolean validUtf8(int[] data) {
for(int i = 0; i < data.length;) {
int l = 1;
for(; l < 7 && ((data[i] >> (8 - l)) & 1) == 1; l++) {}
if(l == 2 || l > 5 || i + l - 2 >= data.length)
return false;
if(l > 2) l--;
for(int j = i + 1; j < i + l; j++)
if((data[j] & TWO) != ONE)
return false;
i += l;
}
return true;
}
}
javascript 解法, 执行用时: 84 ms, 内存消耗: 41.7 MB, 提交时间: 2023-02-27 14:37:42
/**
* @param {number[]} data
* @return {boolean}
*/
const ONE = 1 << 7, TWO = ONE + (1 << 6)
var validUtf8 = function(data) {
for(let i = 0; i < data.length; ) {
let l = 1
for(;l < 7 && (data[i] >> (8 - l)) & 1 == 1; l++) {}
if(l == 2 || l > 5 || i + l - 2 >= data.length)
return false
if(l > 2)
l--
for(let j = i + 1; j < i + l; j++)
if((data[j] & TWO) != ONE)
return false
i += l
}
return true
};
python3 解法, 执行用时: 36 ms, 内存消耗: 15.2 MB, 提交时间: 2023-02-27 14:37:25
ONE = 1 << 7
TWO = ONE + (1 << 6)
class Solution:
def validUtf8(self, data: List[int]) -> bool:
i = 0
while i < len(data):
l = 1
while l < 7 and data[i] >> (8 - l) & 1:
l += 1
if l == 2 or l > 5:
return False
if l > 2:
l -= 1
if i + l - 1 >= len(data):
return False
for j in range(i + 1, i + l):
if (data[j] & TWO) != ONE:
return False
i += l
return True
golang 解法, 执行用时: 12 ms, 内存消耗: 5 MB, 提交时间: 2023-02-27 14:37:02
const one int = 1 << 7
const two int = one + (1 << 6)
func validUtf8(data []int) bool {
for i := 0; i < len(data); {
l := 1
for l < 7 && (data[i] >> (8 - l)) & 1 == 1 {
l++
}
if l == 2 || l > 5 || i + l - 2 >= len(data) {
return false
}
if l > 2 {
l--
}
for j := i + 1; j < i + l; j++ {
if data[j] & two != one {
return false
}
}
i += l
}
return true
}
golang 解法, 执行用时: 12 ms, 内存消耗: 5 MB, 提交时间: 2023-02-27 14:36:45
const mask1, mask2 = 1 << 7, 1<<7 | 1<<6
func getBytes(num int) int {
if num&mask1 == 0 {
return 1
}
n := 0
for mask := mask1; num&mask != 0; mask >>= 1 {
n++
if n > 4 {
return -1
}
}
if n >= 2 {
return n
}
return -1
}
func validUtf8(data []int) bool {
for index, m := 0, len(data); index < m; {
n := getBytes(data[index])
if n < 0 || index+n > m {
return false
}
for _, ch := range data[index+1 : index+n] {
if ch&mask2 != mask1 {
return false
}
}
index += n
}
return true
}
python3 解法, 执行用时: 60 ms, 内存消耗: 15.2 MB, 提交时间: 2023-02-27 14:36:29
class Solution:
def validUtf8(self, data: List[int]) -> bool:
MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)
def getBytes(num: int) -> int:
if (num & MASK1) == 0:
return 1
n, mask = 0, MASK1
while num & mask:
n += 1
if n > 4:
return -1
mask >>= 1
return n if n >= 2 else -1
index, m = 0, len(data)
while index < m:
n = getBytes(data[index])
if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):
return False
index += n
return True