题目信息
- 平台：LeetCode
- 题目：717. 1 比特与 2 比特字符
- 难度：Easy
- 题目链接：1-bit and 2-bit Characters
题目描述
给定一个仅包含 0 和 1 的数组
bits，其中0表示一个 1 比特字符，10或11表示 2 比特字符，并保证数组最后一个元素为0。请判断最后一个字符是否一定为 1 比特字符。
初步思路
- 模拟解码：从左到右扫描，若当前位置是
1，则这是 2 比特字符的起点，需要跳过后一个元素；若是0，就向前移动 1 步。 - 循环只需遍历到倒数第二个元素（因为题目保证最后一个为
0），若结束时指针停在最后一位，说明最后一位没有与前面的1组合，必然是 1 比特字符。
算法分析
- 核心：一次遍历，通过贪心跳步保证每次都跳过一个完整字符。
- 变形思路：只统计倒数第二位起连续的
1的数量，若为偶数则最后的0被单独解码。 - 时间复杂度：
O(n)，只需一次扫描或一次逆向统计。 - 空间复杂度：
O(1)，使用常数级指针或计数器即可。
代码实现（Python）
from typing import List
class Solution:
def isOneBitCharacter(self, bits: List[int]) -> bool:
i, n = 0, len(bits)
while i < n - 1:
i += bits[i] + 1 # 遇到 1 跳过 2 位，遇到 0 跳过 1 位
return i == n - 1代码实现（Go）
func isOneBitCharacter(bits []int) bool {
n := len(bits)
i := n - 2
for i >= 0 && bits[i] == 1 {
i--
}
return (n-i)%2 == 0
}测试用例
| 输入 | 输出 | 说明 |
|---|---|---|
| bits = [1,0,0] | true | 2 比特后剩余最后一个 0，独立成 1 比特 |
| bits = [1,1,1,0] | false | 倒数第二位起有奇数个 1，最后的 0 与前面组成 2 比特 |
| bits = [0] | true | 唯一的 0 只能是 1 比特 |
总结与反思
- 贪心跳步与统计末尾连续 1 的方法本质相同，可根据实现语言选择更直观的写法。
- 题目保证最后一位为 0，大幅简化了边界处理；若无此保证则需额外判断，确保不会越界访问。
