717. 1 比特与 2 比特字符

题目描述

有两种特殊字符：

第一种字符可以用一比特 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

解法

方法一：直接遍历

我们可以直接遍历数组 \(\textit{bits}\) 的前 \(n-1\) 个元素，每次根据当前元素的值决定跳过多少个元素：

如果当前元素为 \(0\)，则跳过 \(1\) 个元素（表示一个一比特字符）；
如果当前元素为 \(1\)，则跳过 \(2\) 个元素（表示一个两比特字符）。

当遍历结束时，如果当前索引等于 \(n-1\)，则说明最后一个字符是一个一比特字符，返回 \(\text{true}\)；否则，返回 \(\text{false}\)。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{bits}\) 的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRustJavaScript

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i, n = 0, len(bits)
        while i < n - 1:
            i += bits[i] + 1
        return i == n - 1

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0, n = bits.length;
        while (i < n - 1) {
            i += bits[i] + 1;
        }
        return i == n - 1;
    }
}

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0, n = bits.size();
        while (i < n - 1) {
            i += bits[i] + 1;
        }
        return i == n - 1;
    }
};

func isOneBitCharacter(bits []int) bool {
    i, n := 0, len(bits)
    for i < n-1 {
        i += bits[i] + 1
    }
    return i == n-1
}

function isOneBitCharacter(bits: number[]): boolean {
    let i = 0;
    const n = bits.length;
    while (i < n - 1) {
        i += bits[i] + 1;
    }
    return i === n - 1;
}

impl Solution {
    pub fn is_one_bit_character(bits: Vec<i32>) -> bool {
        let mut i = 0usize;
        let n = bits.len();
        while i < n - 1 {
            i += (bits[i] + 1) as usize;
        }
        i == n - 1
    }
}

/**
 * @param {number[]} bits
 * @return {boolean}
 */
var isOneBitCharacter = function (bits) {
    let i = 0;
    const n = bits.length;
    while (i < n - 1) {
        i += bits[i] + 1;
    }
    return i === n - 1;
};

717. 1 比特与 2 比特字符

题目描述

解法

方法一：直接遍历

评论