題目連結:
題目意譯:
給定一整數陣列 data,代表著一串數據,回傳其是否為一個合法的 UTF-8 編碼字串(即,它可以轉換成一個合法的 UTF-8 編碼字元之序列)。
一個在 UTF-8 中的字元可以是 1 到 4 位元組(Bytes)長,其遵循以下規則:
對於一個 1-位元組字元,第 1 個位元是一個 0,緊接著其 Unicode 編號。
對於一個 n-位元組字元,前 n 個位元都是 1、第 n + 1 個位元是 0,接著的 n - 1 位元組的開頭兩位元都是 10。
以下式 UTF-8 編碼的運作方式:
(位元組數) (UTF-8 位元組序列)
Number of Bytes | UTF-8 Octet Sequence
| (二進位制)
--------------------+-----------------------------------------
1 | 0xxxxxxx
2 | 110xxxxx 10xxxxxx
3 | 1110xxxx 10xxxxxx 10xxxxxx
4 | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
x 代表著某個位元在一個位元組之二進位制中可以是 0 或是 1。
注: 輸入為一整數陣列。每個整數最低位的 8 的位元才是用來儲存數據的地方,意味著每個整數只代表一位元組的數據。
限制:
1 ≦ data.length ≦ 2 × 10 ^ 4
0 ≦ data[i] ≦ 255
範例測資:
範例 1:
輸入: data = [197,130,1]
輸出: true
解釋: data 代表了位元組序列:11000101 10000010 00000001。
這是一個合法的 UTF-8 編碼,其包含著一個 2-位元組字元並緊接著一個 1-位元組字元。
範例 2:
輸入: data = [235,140,4]
輸出: false
解釋: data 代表了位元組序列:11101011 10001100 00000100。
前 3 個位元都是 1 而第 4 個位元是 0,意味著它會是一個 3-位元組字元。
接著的一個位元組是接續前一個位元組,其以 10 作為開頭,有符合規則。
但第二個接續的位元組並非以 10 作為開頭,因此此數據不合法。
解題思維:
就單純地檢查即可。
掃過 data 中每一個整數,檢查其開頭是否為 0(當然,這邊說的都是以二進位制的角度為主)。如果是,則該整數(位元組)合法,可以繼續看下一個整數;反之,則看開頭有幾個 1(假設有 L 個)。
如果 L 不是 2 、 3 或是 4,則代表這個編碼不合法(Unicode 最長只能 4 位元組)。如果 L 是 2 、 3 或是 4,則就檢查緊接著的 L - 1 個整數的開頭是否都是 10。如果這 L - 1 個整數有不是以 10 作為開頭,又或是剩下的整數根本就不足 L - 1 個,則代表整個編碼不合法。
而最後如果平安無事地掃完所有整數沒有出問題,則代表編碼合法。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。