題目描述

這是 LeetCode 上的 393. UTF-8 編碼驗(yàn)證 ，難度為 中等。

Tag : 「模擬」

給定一個(gè)表示數(shù)據(jù)的整數(shù)數(shù)組 data ，返回它是否為有效的 UTF−8 編碼。

UTF-8 中的一個(gè)字符可能的長度為 1 到 4 字節(jié)，遵循以下的規(guī)則：

• 對于 1字節(jié) 的字符，字節(jié)的第一位設(shè)為 0，后面 7 位為這個(gè)符號的 unicode 碼。
• 對于 n 字節(jié) 的字符 (n>1)，第一個(gè)字節(jié)的前 n 位都設(shè)為 1，第 n+1 位設(shè)為 0 ，后面字節(jié)的前兩位一律設(shè)為 10。剩下的沒有提及的二進(jìn)制位，全部為這個(gè)符號的 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

注意：輸入是整數(shù)數(shù)組。只有每個(gè)整數(shù)的 最低 8 個(gè)有效位 用來存儲數(shù)據(jù)。這意味著每個(gè)整數(shù)只表示 1 字節(jié)的數(shù)據(jù)。

示例 1：

輸入：data = [197,130,1]
輸出：true
解釋：數(shù)據(jù)表示字節(jié)序列:11000101 10000010 00000001。
這是有效的 utf-8 編碼，為一個(gè) 2 字節(jié)字符，跟著一個(gè) 1 字節(jié)字符。

示例 2：

輸入：data = [235,140,4]
輸出：false
解釋：數(shù)據(jù)表示 8 位的序列: 11101011 10001100 00000100.
前 3 位都是 1 ，第 4 位為 0 表示它是一個(gè) 3 字節(jié)字符。
下一個(gè)字節(jié)是開頭為 10 的延續(xù)字節(jié)，這是正確的。
但第二個(gè)延續(xù)字節(jié)不以 10 開頭，所以是不符合規(guī)則的。

提示:

模擬

根據(jù)題意進(jìn)行模擬即可。

如果上述過程滿足要求，跳到下一個(gè)檢查點(diǎn)進(jìn)行檢查，整個(gè) data 都沒有沖突則返回 True。

代碼：

class Solution {
    public boolean validUtf8(int[] data) {
        int n = data.length;
        for (int i = 0; i < n; ) {
            int t = data[i], j = 7;
            while (j >= 0 && (((t >> j) & 1) == 1)) j--;
            int cnt = 7 - j;
            if (cnt == 1 || cnt > 4) return false;
            if (i + cnt - 1 >= n) return false;
            for (int k = i + 1; k < i + cnt; k++) {
                if ((((data[k] >> 7) & 1) == 1) && (((data[k] >> 6) & 1) == 0)) continue;
                return false;
            }
            i += cnt == 0 ? 1 : cnt;
        }
        return true;
    }
}

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

最后

這是我們「刷穿 LeetCode」系列文章的第 No.393 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個(gè)系列文章里面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板。

為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼，我建立了相關(guān)的倉庫：github.com/SharingSour… 。

以上就是java LeetCode普通字符串模擬題解示例的詳細(xì)內(nèi)容，更多關(guān)于java LeetCode普通字符串的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論