Medium
题目描述
给定一个表示数据的整数数组 data，返回它是否为有效的 UTF-8 编码（即它是否可以翻译为一序列有效的 UTF-8 编码字符）。
UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：
- 对于 1 字节的字符，字节的第一位设为 0，后面 7 位为这个符号的 unicode 码。
- 对于 n 字节的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0，后面字节的前两位一律设为 10。余下的没有提及的二进制位，全部为这个符号的 unicode 码。
UTF-8 的编码规则如下：
字符数 | UTF-8 八位字节序列
| (二进制)
----------------+---------------------------------------------
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
解释：数据表示字节序列:11101011 10001100 00000100。
前 3 个位都是 1 ，第 4 个位是 0 表示它是一个 3 字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不是以 10 开头，所以是不符合规则的。
提示：
1 <= data.length <= 2 * 10^40 <= data[i] <= 255
解题思路
解题思路
这道题需要我们验证一个整数数组是否符合 UTF-8 编码规则。关键在于理解 UTF-8 的编码模式：
- 1字节字符：以
0开头 (0xxxxxxx) - 2字节字符：第一字节以
110开头，第二字节以10开头 - 3字节字符：第一字节以
1110开头，后续两字节都以10开头 - 4字节字符：第一字节以
11110开头，后续三字节都以10开头
核心算法：
- 遍历数组，对每个字节判断它是字符的开始还是延续字节
- 如果是开始字节，根据前缀确定字符长度（1-4字节）
- 检查后续的延续字节是否都以
10开头 - 使用位运算来检测字节模式：
byte & 0x80 == 0：检测是否以0开头（1字节字符）byte & 0xE0 == 0xC0：检测是否以110开头（2字节字符首字节）byte & 0xF0 == 0xE0：检测是否以1110开头（3字节字符首字节）byte & 0xF8 == 0xF0：检测是否以11110开头（4字节字符首字节）byte & 0xC0 == 0x80：检测是否以10开头（延续字节）
时间复杂度为 O(n)，空间复杂度为 O(1)。
代码实现
class Solution {
public:
bool validUtf8(vector<int>& data) {
int i = 0;
while (i < data.size()) {
int byte = data[i] & 0xFF;
int numBytes = 0;
// 确定字符的字节数
if ((byte & 0x80) == 0) {
numBytes = 1;
} else if ((byte & 0xE0) == 0xC0) {
numBytes = 2;
} else if ((byte & 0xF0) == 0xE0) {
numBytes = 3;
} else if ((byte & 0xF8) == 0xF0) {
numBytes = 4;
} else {
return false;
}
// 检查是否有足够的字节
if (i + numBytes > data.size()) {
return false;
}
// 检查后续的延续字节
for (int j = 1; j < numBytes; j++) {
if ((data[i + j] & 0xC0) != 0x80) {
return false;
}
}
i += numBytes;
}
return true;
}
};
class Solution:
def validUtf8(self, data: List[int]) -> bool:
i = 0
while i < len(data):
byte = data[i] & 0xFF
num_bytes = 0
# 确定字符的字节数
if (byte & 0x80) == 0:
num_bytes = 1
elif (byte & 0xE0) == 0xC0:
num_bytes = 2
elif (byte & 0xF0) == 0xE0:
num_bytes = 3
elif (byte & 0xF8) == 0xF0:
num_bytes = 4
else:
return False
# 检查是否有足够的字节
if i + num_bytes > len(data):
return False
# 检查后续的延续字节
for j in range(1, num_bytes):
if (data[i + j] & 0xC0) != 0x80:
return False
i += num_bytes
return True
public class Solution {
public bool ValidUtf8(int[] data) {
int i = 0;
while (i < data.Length) {
int byteVal = data[i] & 0xFF;
int numBytes = 0;
// 确定字符的字节数
if ((byteVal & 0x80) == 0) {
numBytes = 1;
} else if ((byteVal & 0xE0) == 0xC0) {
numBytes = 2;
} else if ((byteVal & 0xF0) == 0xE0) {
numBytes = 3;
} else if ((byteVal & 0xF8) == 0xF0) {
numBytes = 4;
} else {
return false;
}
// 检查是否有足够的字节
if (i + numBytes > data.Length) {
return false;
}
// 检查后续的延续字节
for (int j = 1; j < numBytes; j++) {
if ((data[i + j] & 0xC0) != 0x80) {
return false;
}
}
i += numBytes;
}
return true;
}
}
/**
* @param {number[]} data
* @return {boolean}
*/
var validUtf8 = function(data) {
let i = 0;
while (i < data.length) {
let byte = data[i];
let numBytes;
if ((byte >> 7) === 0) {
numBytes = 1;
} else if ((byte >> 5) === 0b110) {
numBytes = 2;
} else if ((byte >> 4) === 0b1110) {
numBytes = 3;
} else if ((byte >> 3) === 0b11110) {
numBytes = 4;
} else {
return false;
}
if (i + numBytes > data.length) {
return false;
}
for (let j = 1; j < numBytes; j++) {
if ((data[i + j] >> 6) !== 0b10) {
return false;
}
}
i += numBytes;
}
return true;
};
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 位运算模式匹配 | O(n) | O(1) |
其中 n 是数组长度。我们需要遍历整个数组一次，对每个字节进行常数时间的位运算检查。