【C++刷题】力扣-#717-1比特与2比特字符

题目描述

有两种特殊字符：
● 第一种字符可以用一比特 0 表示
● 第二种字符可以用两比特（10 或 11）表示
给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。

示例

示例 1

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

示例 2

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

题解

这个问题可以通过遍历数组并检查每个子串来解决。

1. 检查最后一个字符：首先检查数组的最后一个字符是否为 0，如果不是，则直接返回 false，因为最后一个字符必须是一比特字符。
2. 遍历数组：从数组的第一个元素开始遍历，直到倒数第二个元素。
   ○ 如果当前字符是 0，则它是一个一比特字符，继续检查下一个字符。
   ○ 如果当前字符是 1，则检查下一个字符：
   ■ 如果下一个字符是 0 或 1，则它们组成一个两比特字符，继续检查后面的字符。
   ■ 如果下一个字符是数组的最后一个字符且为 1，则返回 false，因为这意味着数组不能被正确解析。
3. 返回结果：如果遍历结束后没有找到不满足条件的子串，则返回 true。

代码实现

bool isOneBitCharacter(vector<int>& bits) {
    int n = bits.size();
    if (bits[n - 1] != 0) {
        return false;
    }
    for (int i = 0; i < n - 1; i++) {
        if (bits[i] == 0) {
            continue;
        }
        if (i == n - 2 && bits[i] == 1) {
            return false;
        }
        i++;
    }
    return true;
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 bits 的长度。我们需要遍历一次数组。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法通过一次遍历数组并检查每个字符来确定数组是否能被解释为由一比特和两比特字符组成的序列，其中最后一个字符必须是一比特字符。