LeetCode 393. UTF-8 编码验证

Categories:

题目描述
思路分析
1. 解法一：逐字节校验（推荐）
相似题目

题目描述

✅ 393. UTF-8 编码验证

思路分析

解法一：逐字节校验（推荐）

核心思路：

判断首字节连续 1 的个数 cnt：

cnt == 0：单字节字符。

cnt 在 [2,4]：表示多字节字符长度。

随后必须有 cnt-1 个以 10 开头的续字节。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字节数量。

空间复杂度：O(1)。

class Solution {
    public boolean validUtf8(int[] data) {
        int i = 0;
        while (i < data.length) {
            int b = data[i];
            int cnt = countLeadingOnes(b);

            if (cnt == 1 || cnt > 4) {
                return false;
            }
            if (cnt == 0) {
                i++;
                continue;
            }

            if (i + cnt > data.length) {
                return false;
            }

            for (int k = 1; k < cnt; k++) {
                if ((data[i + k] & 0xC0) != 0x80) {
                    return false;
                }
            }
            i += cnt;
        }
        return true;
    }

    private int countLeadingOnes(int b) {
        int mask = 0x80;
        int cnt = 0;
        while ((b & mask) != 0) {
            cnt++;
            mask >>= 1;
        }
        return cnt;
    }
}

func validUtf8(data []int) bool {
	i := 0
	for i < len(data) {
		b := data[i]
		cnt := leadingOnes(b)
		if cnt == 1 || cnt > 4 {
			return false
		}
		if cnt == 0 {
			i++
			continue
		}
		if i+cnt > len(data) {
			return false
		}
		for k := 1; k < cnt; k++ {
			if data[i+k]&0xC0 != 0x80 {
				return false
			}
		}
		i += cnt
	}
	return true
}

func leadingOnes(b int) int {
	mask := 0x80
	cnt := 0
	for b&mask != 0 {
		cnt++
		mask >>= 1
	}
	return cnt
}

相似题目

题目	难度	考察点
393. UTF-8 编码验证	中等	位运算
468. 验证 IP 地址	中等	字符串
8. 字符串转换整数 (atoi)	中等	字符串
65. 有效数字	困难	字符串
344. 反转字符串	简单	字符串
14. 最长公共前缀	简单	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/64169609