UTF-8 中的一个字符可能的长度为 1 到 4 字节,遵循以下的规则:
对于 1 字节的字符,字节的第一位设为 0 ,后面 7 位为这个符号的 unicode 码。对于 n 字节的字符 (n > 1),第一个字节的前 n 位都设为1,第 n+1 位设为 0 ,后面字节的前两位一律设为 10 。剩下的没有提及的二进制位,全部为这个符号的 unicode 码。这是 UTF-8 编码的工作方式:
Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
给定一个表示数据的整数数组,返回它是否为有效的 utf-8 编码。
注意:
输入是整数数组。只有每个整数的 最低 8 个有效位 用来存储数据。这意味着每个整数只表示 1 字节的数据。
示例 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 开头,所以是不符合规则的。
解题思路
思考
这显然是一题和位 *** 作有关的题目。并且,这其中有非常多的状态需要考虑。UTF-8编码的字符可以是由 1 到 4 个字节来表示,并且从第1个字节我们就可以看出该UTF-8字符一共由几个字节组成。所以,当我们接收到第一个字节,后续的0到3个字节必须符合所有题设限制(字节数目限制、每个字节的前导比特限制)。这内部其实是一个很完整的确定有限状态机(DFA)。这里,我们选择直接建立这个自动机。
算法例如,状态 0 表示 clear,即所有之前的字节都已经处理成 UTF-8字符了。接下来,有效的输入其实只有 4 种,所以 0 这个状态其实可以转移成 4 个其他状态:
0xxxxxxx
,表示单字节UTF-8字符,那么其实可以直接转移回0(clear)。110xxxxx
,表示双字节UTF-8字符,定义一个新状态1。1110xxxxx
,表示三字节UTF-8字符,定义一个新状态2。11110xxx
,表示四字节UTF-8字符,定义一个新状态3。
剩下的状态转移可以依次类推,下面我直接给出了DFA。
我们看一个最长转移路径:0 -> 3 -> 5 -> 6 -> 0
,这条路径代表一个 4 字节的有效UTF-8字符——当我们依次接收到 11110xxx
, 10xxxxxx
, 10xxxxxx
, 10xxxxxx
,状态又跳回了clear态,即0。所有不符合这个路径特征的输入,都可以直接认为是一个无效的UTF-8字符。
// 393. UTF-8 编码验证
func validUtf8(_ data: [Int]) -> Bool {
let type0 = 0b00000000, type1 = 0b10000000, type2 = 0b11000000, type3 = 0b11100000, type4 = 0b11110000
let masks = [0b10000000, 0b11000000, 0b11100000, 0b11110000, 0b11111000]
let types = [type0, type1, type2, type3, type4]
let DFA = [0: [type0: 0, type2: 1, type3: 2, type4: 3],
1: [type1: 0],
2: [type1: 4],
3: [type1: 5],
4: [type1: 0],
5: [type1: 6],
6: [type1: 0]]
func getType(_ input: Int) -> Int {
for i in 0..<types.count {
if (masks[i] & input) == types[i] {
return types[i]
}
}
return -1
}
func getNext(_ cur: Int, _ input: Int) -> Int? {
let type = getType(input)
if type == -1 {
return nil
}
return DFA[cur]?[type]
}
var cur = 0
for datum in data {
guard let next = getNext(cur, datum) else {
return false
}
cur = next
}
return cur == 0
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)