您的位置 首页 java

LeetCode 力扣官方题解 | 393. UTF-8 编码验证

智云科技发布于 2023年5月20日评论关闭阅读(112)

393. UTF-8 编码验证

题目描述

难易度：中等

给定一个表示数据的整数数组 data ，返回它是否为有效的 UTF-8 编码。

UTF-8 中的一个字符可能的长度为 1 到 4 字节 ，遵循以下的规则：

1.对于 1 字节 的字符，字节的第一位设为 0 ，后面 7 位为这个符号的 unicode 码。

2.对于 n 字节 的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 unicode 码。

这是 UTF-8 编码的工作方式： 

 Number of Bytes  |        UTF-8 octet sequence
                       |              (binary)
   --------------------+---------------------------------------------
            1          | 0xxxxxxx
            2          | 110xxxxx 10xxxxxx
            3          | 1110xxxx 10xxxxxx 10xxxxxx
            4          | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x 表示 二进制 形式的一位，可以是 0 或 1。

注意：输入是整数数组。只有每个整数的 最低 8 个有效位 用来存储数据。这意味着每个整数只表示 1 字节的数据。

示例 1： 

 输入：data = [197,130,1]
输出：true
解释：数据表示字节序列:11000101 10000010 00000001。
这是有效的 utf-8 编码，为一个 2 字节字符，跟着一个 1 字节字符。

示例 2： 

 输入：data = [235,140,4]
输出：false
解释：数据表示 8 位的序列: 11101011 10001100 00000100.
前 3 位都是 1 ，第 4 位为 0 表示它是一个 3 字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不以 10 开头，所以是不符合规则的。

提示：

  • 1 <= data.length <= 2 * 104
  • 0 <= data[i] <= 255

解决方案

方法一：遍历 + 位运算

思路

如果给定的数组 data 是有效的 UTF-8 编码，则可能由一个或多个 UTF-8 字符组成。第一个 UTF-8 字符的长度由 data[0] 的值决定。对于从 data[index] 开始的 UTF-8 字符，可根据 data[index] 的值得到该字符的长度 n，如果下一个 UTF-8 字符存在，则下一个 UTF-8 字符从下标 index+n 开始。因此，如果给定的数组 data 是有效的 UTF-8 编码，则其对应的 UTF-8 字符序列是唯一的，且每个 UTF-8 字符的开始下标是确定的。

基于上述分析，可以遍历数组 data 得到每个字符的开始下标和长度，并分别判断每个字符是否符合 UTF-8 编码的规则。

每个 UTF-8 字符由 1 到 4 个字节组成。以下将每个UTF-8 字符的第 1 个字节称为头字节，除了第 1 个字节以外的字节统称为其余字节。

用 m 表示 data 的长度，用 index 表示 UTF-8 字符的头字节在 data 中的下标，初始时 index=0。对于每个字符，执行如下操作。

1. 头字节包含了当前字符的字节数信息，根据头字节计算当前字符字节数的方法如下。

  • 如果头字节的最高位是 0，则当前字符由 1 个字节组成，只有头字节，没有其余字节。
  • 如果头字节的最高位是 1，则计算头字节从最高位开始的连续 1 的个数。如果连续 1 的个数为 2 个到 4 个，则连续 1 的个数表示当前字符的字节数；否则头字节不符合 UTF-8 编码的规则，data 不是有效的UTF-8 编码。

2. 当头字节符合 UTF-8 编码的规则时，根据头字节得到当前字符的字节数为 n，则当前字符包括头字节和 n−1 个其余字节。如果 data 在头字节后面的字节数小于 n−1，即 index+n > m，则 data 不是有效的 UTF-8 编码。

3. 当 data 在头字节后面的字节数大于等于 n−1 时，头字节后面的 n−1 个字节为当前字符的其余字节。判断每个其余字节的最高两位是否是 10，如果存在一个其余字节的最高两位不是 10，则 data 不是有效的 UTF-8 编码。

4. 当前字符遍历结束之后，将 index 的值加 n，则更新后的 index 是下一个字符的头字节在 data 中的下标。

重复上述操作，直到 index = n 时遍历结束，此时 data 是有效的 UTF-8 编码。

实现

判断 data 是否是有效的 UTF-8 编码时，需要对每个字符的头字节和其余字节分别做判断。判断需要通过 位运算 实现，为了方便判断，需要设计两个位掩码 MASK1 = 27 ，MASK2 = 27 + 26。

对于头字节，首先判断头字节和 MASK1 的按位与运算结果是否为 0。如果为 0 则当前字符由 1 个字节组成。如果不为 0 则创建位掩码 mask 并将初始值设为 MASK1 ，每次计算头字节和 mask 的按位与运算结果，如果结果不为 0 则将 mask 除以 2（可通过右移位运算实现）并重复该过程，直到结果为 0，此时可得到当前字符的字节数。

对于其余字节，判断最高两位是否是 10 的做法为计算其余字节和 MASK 2 的按位与运算结果是否等于 MASK1。

具体实现见代码。

代码

Python3 

 class Solution:
    def validUtf8(self, data: List[int]) ->  bool :
        MASK1, MASK2 = 1 << 7, (1 << 7) | (1 << 6)


        def getBytes(num: int) -> int:
            if (num & MASK1) == 0:
                return 1
            n, mask = 0, MASK1
            while num & mask:
                n += 1
                if n > 4:
                    return -1
                mask >>= 1
            return n if n >= 2 else -1


        index, m = 0,  len (data)
        while index < m:
            n = get Bytes (data[index])
            if n < 0 or index + n > m or any((ch & MASK2) != MASK1 for ch in data[index + 1: index + n]):
                return False
            index += n
        return True

Java 

 class Solution {
    static final int MASK1 = 1 << 7;
    static final int MASK2 = (1 << 7) + (1 << 6);


    public boolean validUtf8(int[] data) {
        int m = data.length;
        int index = 0;
        while (index < m) {
            int num = data[index];
            int n = getBytes(num);
            if (n < 0 || index + n > m) {
                return false;
            }
            for (int i = 1; i < n; i++) {
                 if  (!isValid(data[index + i])) {
                    return false;
                }
            }
            index += n;
        }
        return true;
    }


    public int getBytes(int num) {
        if ((num & MASK1) == 0) {
            return 1;
        }
        int n = 0;
        int mask = MASK1;
        while ((num & mask) != 0) {
            n++;
            if (n > 4) {
                return -1;
            }
            mask >>= 1;
        }
        return n >= 2 ? n : -1;
    }


    public boolean isValid(int num) {
        return (num & MASK2) == MASK1;
    }
}

C# 

 public class Solution {
    const int MASK1 = 1 << 7;
    const int MASK2 = (1 << 7) + (1 << 6);


    public bool ValidUtf8(int[] data) {
        int m = data.Length;
        int index = 0;
        while (index < m) {
            int num = data[index];
            int n = GetBytes(num);
            if (n < 0 || index + n > m) {
                return false;
            }
            for (int i = 1; i < n; i++) {
                if (!IsValid(data[index + i])) {
                    return false;
                }
            }
            index += n;
        }
        return true;
    }


    public int GetBytes(int num) {
        if ((num & MASK1) == 0) {
            return 1;
        }
        int n = 0;
        int mask = MASK1;
        while ((num & mask) != 0) {
            n++;
            if (n > 4) {
                return -1;
            }
            mask >>= 1;
        }
        return n >= 2 ? n : -1;
    }


    public bool IsValid(int num) {
        return (num & MASK2) == MASK1;
    }
}

C++ 

 class Solution {
public:
    static const int MASK1 = 1 << 7;
    static const int MASK2 = (1 << 7) + (1 << 6);


    bool isValid(int num) {
        return (num & MASK2) == MASK1;
    }


    int getBytes(int num) {
        if ((num & MASK1) == 0) {
            return 1;
        }
        int n = 0;
        int mask = MASK1;
        while ((num & mask) != 0) {
            n++;
            if (n > 4) {
                return -1;
            }
            mask >>= 1;
        }
        return n >= 2 ? n : -1;
    }


    bool validUtf8(vector<int>& data) {
        int m = data.size();
        int index = 0;
        while (index < m) {
            int num = data[index];
            int n = getBytes(num);
            if (n < 0 || index + n > m) {
                return false;
            }
            for (int i = 1; i < n; i++) {
                if (!isValid(data[index + i])) {
                    return false;
                }
            }
            index += n;
        }
        return true;
    }
};

C 

 static const int MASK1 = 1 << 7;
static const int MASK2 = (1 << 7) + (1 << 6);


bool isValid(int num) {
    return (num & MASK2) == MASK1;
}


int getBytes(int num) {
    if ((num & MASK1) == 0) {
        return 1;
    }
    int n = 0;
    int mask = MASK1;
    while ((num & mask) != 0) {
        n++;
        if (n > 4) {
            return -1;
        }
        mask >>= 1;
    }
    return n >= 2 ? n : -1;
}


bool validUtf8(int* data, int dataSize){
    int m = dataSize;
    int index = 0;
    while (index < m) {
        int num = data[index];
        int n = getBytes(num);
        if (n < 0 || index + n > m) {
            return false;
        }
        for (int i = 1; i < n; i++) {
            if (!isValid(data[index + i])) {
                return false;
            }
        }
        index += n;
    }
    return true;
}

JavaScript 

 const MASK1 = 1 << 7;
const MASK2 = (1 << 7) + (1 << 6);


var validUtf8 = function(data) {
    const m = data.length;
    let index = 0;
    while (index < m) {
        const num = data[index];
        const n = getBytes(num);
        if (n < 0 || index + n > m) {
            return false;
        }
        for (let i = 1; i < n; i++) {
            if (!isValid(data[index + i])) {
                return false;
            }
        }
        index += n;
    }
    return true;
};


const getBytes = (num) => {
    if ((num & MASK1) === 0) {
        return 1;
    }
    let n = 0;
    let mask = MASK1;
    while ((num & mask) !== 0) {
        n++;
        if (n > 4) {
            return -1;
        }
        mask >>= 1;
    }
    return n >= 2 ? n : -1;
}


const isValid = (num) => {
    return (num & MASK2) === MASK1;
}

Golang 

 const mask1, mask2 = 1 << 7, 1<<7 | 1<<6


func getBytes(num int) int {
    if num&mask1 == 0 {
        return 1
    }
    n := 0
    for mask := mask1; num&mask != 0; mask >>= 1 {
        n++
        if n > 4 {
            return -1
        }
    }
    if n >= 2 {
        return n
    }
    return -1
}


func validUtf8(data []int) bool {
    for index, m := 0, len(data); index < m; {
        n := getBytes(data[index])
        if n < 0 || index+n > m {
            return false
        }
        for _, ch := range data[index+1 : index+n] {
            if ch&mask2 != mask1 {
                return false
            }
        }
        index += n
    }
    return true
}

复杂度分析

  • 时间复杂度：O(m)，其中 m 是数组 data 的长度。需要遍历数组 data 一次，对于数组中的每个元素的计算时间都是 O(1)。
  • 空间复杂度：O(1)。

BY /

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。

标签:
打赏 点赞(0)

文章来源：智云一二三科技

文章标题：LeetCode 力扣官方题解 | 393. UTF-8 编码验证

文章地址：https://www.zhihuclub.com/189759.shtml

关于作者: 智云科技

相关文章

热门文章

1分享新浪图床上传接口源码

点赞(949)阅读(61,177)

2PHP简单实现路由Route功能

点赞(1.16K)阅读(35,973)

3Tideways、xhprof 和 xhgui 打造 PHP 非侵入式监控平台

点赞(379)阅读(4,304)

4centos系统如何查看是否安装了mysql

点赞(546)阅读(3,797)

5curl 工具简述

点赞(525)阅读(2,985)
网站地图