What is the main challenge in the 1-bit and 2-bit Characters problem?

The main challenge lies in correctly identifying whether the last character in the binary array is a one-bit character or a two-bit character by decoding the array from left to right.

How do I track the current character in the array?

You track the current character by iterating through the array and adjusting the index. After a 1, skip the next bit to account for the two-bit character.

What is the time complexity of the solution?

The time complexity of the solution is O(N), where N is the length of the array. This is because we only traverse the array once.

Can this problem be solved with more advanced algorithms?

No, the problem is simple and can be efficiently solved with an O(N) time complexity. More complex algorithms aren't necessary for this problem.

How does GhostInterview help with solving this problem?

GhostInterview guides you step-by-step through the solution process, helping you optimize your approach and avoid common pitfalls like missing edge cases.

#717

Easy

auto_awesome数组·driven

LeetCode 题解工作台

1 比特与 2 比特字符

有两种特殊字符：第一种字符可以用一比特 0 表示第二种字符可以用两比特（ 10 或 11 ）表示给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。示例 1: 输入: bits = [1, 0, 0] 输出: true 解释: 唯一的解码方…

数组

题目描述

有两种特殊字符：

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

lightbulb

解题思路

方法一：直接遍历

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

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

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

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

1

2

3

4

5

6

7

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

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidates who understand the importance of tracking the next character's position and the array-driven solution approach will likely solve the problem quickly.
question_mark
Look for candidates who can explain the logic of skipping bits after encountering a 1 and how it ensures correctness.
question_mark
Candidates who provide a detailed explanation of edge cases, such as handling arrays of length 1 or arrays with consecutive 1's followed by 0, will demonstrate thorough understanding.

warning

常见陷阱

外企场景

error
Candidates may forget to account for the scenario where the array ends with a 0, and incorrectly assume that the last bit is always a one-bit character.
error
Some candidates might miss the optimization of skipping two bits after a 1, leading to unnecessary iterations.
error
Candidates may overlook handling edge cases, like the smallest array or cases where there are multiple consecutive 1's followed by 0.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array ends with a 1 instead of a 0? How would you handle that case?
arrow_right_alt
Can this problem be extended to a more general case where bits represent a larger set of characters?
arrow_right_alt
What if the input array is given in a different encoding format, like a string of 0's and 1's?

help

常见问题

外企场景

继续练习

#718 最长重复子数组 #719 找出第 K 小的数对距离 #714 买卖股票的最佳时机含手续费