每日一题 --- 393. UTF-8 编码验证[力扣][Go]-阿里云开发者社区

每日一题 --- 393. UTF-8 编码验证[力扣][Go]

2023-02-23 114

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 每日一题 --- 393. UTF-8 编码验证[力扣][Go]

题目：

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

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

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

对于 n 字节的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 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

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

解题代码：

官方题解

// 位运算
// mask1 = 10000000
// mask2 = 11000000
const mask1, mask2 = 1 << 7, 1<<7 | 1<<6
// 判断占了几个字节
func getBytes(num int) int {
  if num&mask1 == 0 {
    return 1
  }
  n := 0
  // >>=  即 mask = mask>>1
  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])
    // 如果超出范围就返回 false
    if n < 0 || index+n > m {
      return false
    }
    // 遍历这个字节处第一个元素外应该有的元素
    for _, ch := range data[index+1 : index+n] {
      // ch&mask2 != mask1 用于判断ch前两位数是否为 10
      if ch&mask2 != mask1 {
        return false
      }
    }
    // 跳过该字节应有的数字数
    index += n
  }
  return true
}

我的题解，测试用例通过，提交出错

var binaryPre = []string{"0","110","1110","11110"}
func validUtf8(data []int) bool {
  var binary []string
  // 将data转换为二进制
  for _, datum := range data {
    binary = append(binary, int2binary(datum))
  }
  // 判断第几个是几字节的开始
  var m = make(map[int]int)
  for i := 0; i < len(binary); i++ {
    if strings.Index(binary[i],binaryPre[0]) == 0{
      m[i] = 0
    } else if strings.Index(binary[i],binaryPre[1]) == 0 {
      m[i] = 1
      i += 1
    } else if strings.Index(binary[i],binaryPre[2]) == 0 {
      m[i] = 2
      i += 2
    } else if strings.Index(binary[i],binaryPre[3]) == 0 {
      m[i] = 3
      i += 3
    } else {
      return false
    }
  }
  for i1, i2 := range m {
    if i2 != 0{
      for i := i2 - 1; i >= 0; i-- {
        if strings.Index(binary[i1 + i2 -i], "10") != 0 {
          return false
        }
      }
    }
  }
  return true
}
func int2binary(n int) string {
  var ans string
  for n != 0 {
    ans = strconv.Itoa(n % 2) + ans
    n = n/2
  }
  for len(ans) < 8 {
    ans = "0" + ans
  }
  return ans
}