LeetCode 717. 1 比特与 2 比特字符
题目描述
题意分析
字符的编码只有
0、10、11三种。给定以0结尾的比特数组，判断最后这个0是否单独构成一个单比特字符。最后一个比特为零并不能直接确定答案，它也可能是
10的第二位。关键是从开头正确解析以后，最后一位是否已经被前面的双比特字符消耗。
解法：线性扫描解析
核心思路
[!blue]
用
i指向下一个尚未解析的字符起点，最初为0。如果起点比特为0，它只能单独编码一个字符，指针前进一位；如果为1，它只能是10或11的开头，无论下一位是什么都要消耗两位。首位就确定了长度，因此每一步解析都唯一，移动后仍然停在下一个字符的边界。循环只处理
i < n-1的位置，保留最后一位的归属供最终判断。由于每次前进一位或两位，结束时只可能有两种情况：i == n-1，最后的零尚未被消耗，只能独立成字；或者i == n，最后的零已作为双比特编码10的第二位被处理。因此直接返回
i == n-1。只有一个零时，循环一次也不执行，指针已经在最后一位，结果自然为true。
解题步骤
- 令
i = 0，表示从数组开头解析。- 只要
i < n-1，当前比特为零就前进一步，为一就前进两步。- 循环结束后比较
i与n-1：相等返回true，否则返回false。
代码实现
class Solution {
public boolean isOneBitCharacter(int[] bits) {
int n = bits.length;
int i = 0;
while (i < n - 1) {
if (bits[i] == 0) {
i++;
} else {
i += 2;
}
}
// 停在末位表示最后的零尚未被双比特字符消费。
return i == n - 1;
}
}
func isOneBitCharacter(bits []int) bool {
n := len(bits)
i := 0
for i < n-1 {
if bits[i] == 0 {
i++
} else {
i += 2
}
}
// 停在末位表示最后的零尚未被双比特字符消费。
return i == n-1
}
复杂度分析
- 时间复杂度：$O(n)$。每次至少前进一步，指针不会回退。
- 空间复杂度：$O(1)$。只维护数组长度和当前解析位置。
关键点总结
[!green]
- 指针始终位于字符起点，只有在这个位置才能用首位判断编码长度。
- 起点为一就必须消费两位，起点为零就只消费一位。
- 最后判断的是末位是否尚未被消费，两个可能落点恰好对应两种答案。
易错点总结
[!yellow]
- 末位为零就返回
true，忽略它可能属于双比特编码10。- 只检查最后两个比特，无法知道倒数第二位是否处于字符起点，它可能已是前一编码的一部分。
- 遇到一仍只前进一步，会把同一个双比特字符的第二位误当成新字符起点。
- 把结束位置
i == n当成成功条件，这其实表示末位已经被双比特字符消耗。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 393. UTF-8 编码验证 | 中等 | 同样根据前缀位型决定编码长度，再跳过当前字符占据的位或字节。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！