Last Updated on 2022-09-13 by Clay
題目
Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
- For a 1-byte character, the first bit is a
0, followed by its Unicode code. - For an n-bytes character, the first
nbits are all one’s, then + 1bit is0, followed byn - 1bytes with the most significant2bits being10.
This is how the UTF-8 encoding would work:
Number of Bytes | UTF-8 Octet Sequence
| (binary)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x denotes a bit in the binary form of a byte that may be either 0 or 1.
Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
Example 1:
Input: data = [197,130,1] Output: true Explanation: data represents the octet sequence: 11000101 10000010 00000001. It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
Input: data = [235,140,4] Output: false Explanation: data represented the octet sequence: 11101011 10001100 00000100. The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character. The next byte is a continuation byte which starts with 10 and that's correct. But the second continuation byte does not start with 10, so it is invalid.
Constraints:
1 <= data.length <= 2 * 1040 <= data[i] <= 255
本題是讓我們驗證接收到的 UTF-8 編碼是否『有效』。UTF-8 編碼皆為 8 位元，可以用一個整數來表達（也就是題目真正的輸入：正整數）。
- 僅有一個位元組的字元，開頭會是 0，可能表現形式為 0xxxxxxx
- 兩個位元組：110xxxxx 10xxxxxx
- 三個位元組：1110xxxx 10xxxxxx 10xxxxxx
- 四個位元組：11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
不會有五個位元組的表示形式存在，這一點需要考慮進去。而只要不是僅有一個位元組的表示，除了開頭的二進制表示開頭會有代表幾個位元組的 1’s，其後的位元組全都是 10xxxxxx 這樣的表示形式。
也就是說，假設我們的四位元組表示成：
11110xxx 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 0xxxxxxx 10xxxxxx
這樣可是無效的 UTF-8 編碼表示。多個位元組的表現形式後頭一定要接同樣的 10 開頭的 11110xxx 表示。
也要注意的是，如果一個 UTF-8 的字元表示結束了，後面當然是可以再繼續接其他字元的。這點我一開始土法煉鋼時就不小心搞錯了。
110xxxxx 10xxxxxx 0xxxxxxx
像是這樣，兩個位元組的字元表示完了，但後面當然可以再接一個單個位元組的字元表達。這是合法的 UTF-8 字串。
解題思路
我一開始很理所當然地暴力把數值轉成位元組的字串，然后計算第一個位元組開頭的 1 的數量，把後頭應該要接著的位元組數量儲存，再判斷後面的位元組是否為 10xxxxxx 的表達方式，直到符合最開頭的位元組數量，再進入下一個字元的判斷…… 依此類推，直到結束。
後來解完後，看了下討論區，發現厲害的高手們都是直接用位元操作，我這才恍然大悟…… 只能說自己對於位元操作實在太不熟了，好在被提示過後還是自己摸索出了解題法，基本上就是改進了第一個土法煉鋼版本的判斷過程，變得更有效率。
兩種解法我都一併紀錄在下方。
Brute Force
C++ 解題紀錄
class Solution {
public:
bool validUtf8(vector<int>& data) {
// Init
int currMaxN = 0;
// Determined
for (int i=0; i<data.size(); ++i) {
int currN = 0;
string s = bitset<8>(data[i]).to_string();
// Count 1's
for (int j=0; j<s.size(); ++j) {
if (s[j] == '1') {
++currN;
}
else {
break;
}
}
if (currMaxN == 0) {
if (currN == 1) {
return false;
}
else if (currN > 1) {
currMaxN = currN - 1;
}
}
else if (currMaxN > 0) {
if (currN == 1) {
--currMaxN;
}
else {
return false;
}
}
if (currMaxN >= 4) {
return false;
}
}
return currMaxN == 0;
}
};
Python 解題紀錄
Python 的 bin() 轉成的字串比較麻煩的是，如果像是 1 這樣的數值會自動省略掉一堆 0，導致很難透過字串判斷，需要另外再寫規則把 0 填充回來。
class Solution:
def validUtf8(self, data: List[int]) -> bool:
# Init
curr_n = 0
data = map(bin, data)
# Determined
for byte in data:
byte = byte[2:].zfill(8)
if curr_n == 0:
if byte[:3] == "110":
curr_n = 1
elif byte[:4] == "1110":
curr_n = 2
elif byte[:5] == "11110":
curr_n = 3
elif byte[0] != "0":
return False
else:
if byte[:2] == "10":
curr_n -= 1
else:
return False
return curr_n == 0位元操作（Bit Manipulation）
這個方法基本上也是在判斷開頭的 1 數量，不過直接透過位元操作取前幾位元判斷顯然比操作字串快得多。除此之外，整個程式的流程沒有太大改變，就是優化了判斷過程，所以速度是好上挺多的。
C++ 解題紀錄
class Solution {
public:
bool validUtf8(vector<int>& data) {
// Init
int currMaxN = 0;
// Determined
for (int i=0; i<data.size(); ++i) {
// Count 1's
if (currMaxN == 0) {
if (data[i] >> 5 == 0b110) {
currMaxN = 1;
}
else if (data[i] >> 4 == 0b1110) {
currMaxN = 2;
}
else if (data[i] >> 3 == 0b11110) {
currMaxN = 3;
}
else if (data[i] >> 7 != 0) {
return false;
}
}
else {
if (data[i] >> 6 == 0b10) {
--currMaxN;
}
else {
return false;
}
}
}
return currMaxN == 0;
}
};Python 解題紀錄
class Solution:
def validUtf8(self, data: List[int]) -> bool:
# Init
curr_n = 0
# Determined
for byte in data:
if curr_n == 0:
if byte >> 5 == 0b110:
curr_n = 1
elif byte >> 4 == 0b1110:
curr_n = 2
elif byte >> 3 == 0b11110:
curr_n = 3
elif byte >> 7:
return False
else:
if byte >> 6 == 0b10:
curr_n -= 1
else:
return False
return curr_n == 0