---

0717. 1 比特与 2 比特字符

• 标签：数组
• 难度：简单

题目链接

• 0717. 1 比特与 2 比特字符 - 力扣

题目大意

描述：

有两种特殊字符：

• 第一种字符可以用一比特 $0$ 表示
• 第二种字符可以用两比特（$10$ 或 $11$）表示

给定一个以 $0$ 结尾的二进制数组 $bits$。

要求：

如果最后一个字符必须是一个一比特字符，则返回 true。

说明：

• $1 \le bits.length \le 10^{3}$。
• $bits[i]$ 为 $0$ 或 $1$。

示例：

• 示例 1：

输入: bits = [1, 0, 0]
输出: true
解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。
所以最后一个字符是一比特字符。

• 示例 2：

输入：bits = [1,1,1,0]
输出：false
解释：唯一的解码方式是将其解析为两比特字符和两比特字符。
所以最后一个字符不是一比特字符。

解题思路

思路 1：贪心算法

这道题的关键在于理解字符的编码规则：

• 一比特字符：0
• 两比特字符：10 或 11

由于数组以 0 结尾，我们需要判断这个 0 是作为一比特字符单独存在，还是作为两比特字符的一部分。

解题步骤：

1. 从数组开头开始遍历，使用指针 $i$ 记录当前位置。
2. 如果 $bits[i] = 1$，说明当前是两比特字符，跳过两位（$i$ 增加 $2$）。
3. 如果 $bits[i] = 0$，说明当前是一比特字符，跳过一位（$i$ 增加 $1$）。
4. 当 $i$ 到达倒数第二个位置时停止遍历。
5. 如果 $i$ 正好等于 $n - 1$（最后一个位置），说明最后一个 0 是一比特字符，返回 True。
6. 如果 $i$ 超过了 $n - 1$，说明最后一个 0 是两比特字符的一部分，返回 False。

思路 1：代码

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        n = len(bits)
        i = 0
        
        # 遍历到倒数第二个位置
        while i < n - 1:
            if bits[i] == 1:  # 两比特字符
                i += 2
            else:  # 一比特字符
                i += 1
        
        # 如果 i 正好等于 n - 1，说明最后一个 0 是一比特字符
        return i == n - 1

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $bits$ 的长度。需要遍历整个数组一次。
• 空间复杂度：$O(1)$。只使用了常数个额外变量。