前往
大廳
主題

LeetCode - 0393. UTF-8 Validation 解題心得

Not In My Back Yard | 2023-08-03 12:00:05 | 巴幣 0 | 人氣 88

題目連結:


題目意譯:
給定一整數陣列 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 個,則代表整個編碼不合法。

而最後如果平安無事地掃完所有整數沒有出問題,則代表編碼合法。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作