Easy

题目描述

我们有两种特殊字符：

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

给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一比特字符，则返回 true 。

示例 1:

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

示例 2:

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

提示:

  • 1 <= bits.length <= 1000
  • bits[i] 不是 0 就是 1

解题思路

解题思路

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

  • 0 表示一比特字符
  • 10 或 11 表示两比特字符

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

方法一：模拟解码过程 从数组开头开始，按照编码规则逐个解析字符：

  • 遇到 0：这是一比特字符，指针移动1位
  • 遇到 1：这是两比特字符的开始，指针移动2位

最终检查指针是否恰好停在最后一个位置（倒数第二个索引）。如果是，说明最后一个 0 是独立的一比特字符。

方法二：逆向思维 由于最后一位必须是 0，我们可以从倒数第二位开始向前分析。关键观察：如果倒数第二位之前有连续的 1，那么这些 1 的个数决定了最后的 0 是否独立。

推荐使用方法一，思路更直观清晰。

代码实现

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        while (i < bits.size() - 1) {
            if (bits[i] == 1) {
                i += 2; // 两比特字符
            } else {
                i += 1; // 一比特字符
            }
        }
        return i == bits.size() - 1;
    }
};

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        while i < len(bits) - 1:
            if bits[i] == 1:
                i += 2  # 两比特字符
            else:
                i += 1  # 一比特字符
        return i == len(bits) - 1

public class Solution {
    public bool IsOneBitCharacter(int[] bits) {
        int i = 0;
        while (i < bits.Length - 1) {
            if (bits[i] == 1) {
                i += 2; // 两比特字符
            } else {
                i += 1; // 一比特字符
            }
        }
        return i == bits.Length - 1;
    }
}

var isOneBitCharacter = function(bits) {
    let i = 0;
    while (i < bits.length - 1) {
        if (bits[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个数组，n为数组长度
空间复杂度O(1)只使用常数额外空间

相关题目