LeetCode 717. 1 比特与 2 比特字符

2021-03-17 HGNULB 约 8 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 717. 1 比特与 2 比特字符

题意分析

要什么：一个 0/1 数组是若干字符编码后拼起来的，编码规则是：0 表示一个 1 比特字符，10 和 11 各表示一个 2 比特字符。题目保证数组最后一位是 0，问最后一个字符是否必然是 1 比特字符。
约束透露的信号：这套编码是前缀无歧义的——看到 0 就必然是一个单比特字符结束，看到 1 就必然是一个双比特字符的开头，两种情况互斥且完备。所以从左往右解析时每一步的断句都是唯一确定的，根本不存在多种切分方式，「必然」二字也就有了着落：只要模拟一遍解析就能得到唯一答案，不需要枚举也不需要 DP。这一点是全题的核心，识别不出来就会误以为要做区间划分。
边界：数组末位保证为 0，所以一定能解析完；数组可能只有一个元素 [0]，此时答案是 true；1 一定成对出现在解析中，绝不会是最后一位；解析的推进必须以「字符」为单位而不是「比特」为单位。

解法：线性扫描解析

核心思路

有人会把它当成划分问题：设 f[i] 表示前 i 位能否合法解析，再考虑最后一个字符是 1 位还是 2 位。这样做没错，但完全是杀鸡用牛刀——DP 的价值在于「有多种切分方式需要择优或计数」，而本题的切分唯一。
唯一性来自编码规则的互斥性：站在某个字符的起始位置 i，如果 bits[i] == 0，这个字符只能是 1 比特的 0；如果 bits[i] == 1，这个字符只能是 2 比特的 10 或 11，无论下一位是什么都要一并吃掉。没有任何一种情形需要「试两条路」。
于是解法就是一遍确定性的解析扫描，要维护的不变量是：指针 i 始终停在某个字符的起始位置（初始时 i = 0 显然满足，每次按规则吃掉整个字符后依然满足）。
循环条件是关键：只在 i < n - 1 时继续解析。为什么不是 i < n？因为我们要判断的正是「最后一位那个 0 是不是独立成字」，所以要在还没碰到最后一位时停下来，看指针最终落在哪里。循环结束时只有两种可能：

i == n - 1：前面的字符恰好在最后一位之前解析完，最后一位的 0 只能自成一个 1 比特字符，答案为 true。

i == n：说明上一步是从 i = n - 2 出发吃掉了一个 2 比特字符 10，把最后一位也吞了进去，最后一个字符是 2 比特的，答案为 false。
所以只需返回 i == n - 1。

解题步骤

令 i = 0，进入 while (i < n - 1) 循环。为什么上界是 n - 1 而不是 n：我们关心的是最后一位是否被前面的字符吞掉，必须让循环在「还剩最后一位」时自然停下；写成 i < n 会把最后那个 0 也当作普通字符解析掉，循环结束时 i 恒等于 n，判据失效。

若 bits[i] == 0，令 i++。为什么只前进一位：0 就是一个完整的 1 比特字符，吃掉它之后指针自然落在下一个字符的开头，不变量保持成立。

否则（bits[i] == 1）令 i += 2。为什么可以不看下一位：10 和 11 都是合法的 2 比特字符，下一位是 0 还是 1 都不影响「这个字符占两位」这个事实，所以无需分支。为什么不会越界：题目保证末位是 0，所以 1 不可能出现在最后一位，i + 1 一定是合法下标。

循环结束后返回 i == n - 1。为什么这个判据充要：不变量保证 i 停在某个字符的起始位置，而循环退出意味着 i >= n - 1；等于 n - 1 说明最后一位刚好是一个新字符的开头（只能是单比特 0），大于则说明它已被前一个双比特字符吞掉。

以 bits = [1, 0, 0] 走一遍。n = 3，i = 0。循环判断 0 < 2 成立：bits[0] == 1，吃掉 10 这个 2 比特字符，i 变成 2。再判断 2 < 2 不成立，循环结束。返回 2 == 2 即 true——解析结果是 [10][0]，最后一个字符确实是 1 比特的。

再以 bits = [1, 1, 1, 0] 走一遍。n = 4，i = 0。0 < 3 成立：bits[0] == 1，i 变成 2。2 < 3 成立：bits[2] == 1，吃掉 10，i 变成 4。4 < 3 不成立，循环结束。返回 4 == 3 即 false——解析结果是 [11][10]，最后一位的 0 被第二个双比特字符吞掉了，最后一个字符是 2 比特的。这组用例正是判据的意义所在：末位虽然是 0，却未必独立成字。

代码实现

// 核心实现：线性扫描解析，维护必要状态并避免重复处理。
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)$。凭什么：指针 i 每轮至少前进 1 位且只增不减，最多走 n 步就退出，每步只做一次比较和一次加法。

空间复杂度：$O(1)$。凭什么：全程只有一个指针变量，没有 DP 数组也没有递归栈，输入数组是只读的。

关键点总结

先判断切分是否唯一，再决定用模拟还是 DP。前缀无歧义的编码（本题、UTF-8 校验）只需一遍确定性扫描；而像「解码方法」那样 1 开头既可能单独成字也可能与下一位组合，切分不唯一，才必须上 DP。这个判断是选对武器的关键。

循环边界承载了题意。本题把 i < n - 1 而不是 i < n 当作循环条件，等于把「最后一位单独留出来考察」这个问题需求直接编码进了控制流。遇到「最后一个 / 第一个元素有特殊语义」的题，先想能不能用边界把它隔离出来，比事后特判干净得多。

指针推进的步长要以「逻辑单位」为准，本题是「字符」而不是「比特」。凡是变长编码、变长分组的扫描，都要在心里明确「一次前进吃掉的是一个完整单位」。

题目给的保证（末位为 0）不是装饰，它同时保证了「解析一定能完成」和「i += 2 不会越界」。做题时把每条保证对应到代码里的哪一处，是快速建立信心的方法。

面试视角：这题代码只有五行，考察点其实是能否说清「为什么不需要 DP」和「循环边界为什么是 n-1」。另一种同样正确的写法是从倒数第二位往前数连续 1 的个数，个数为偶则最后一位独立成字；能顺手给出这条 $O(n)$ 但常数更小的解法，说明你真的理解了结构。

易错点总结

错误写法：循环条件写成 while (i < n)；用例 bits = [1, 0, 0] → 最后一位也被当作普通字符解析，i 最终为 3，返回 3 == 2 即 false，正确答案是 true。

错误写法：遇到 bits[i] == 1 时还要看下一位，只有 bits[i+1] == 0 才前进 2 位、否则前进 1 位；用例 bits = [1, 1, 0] → i = 0 时因为下一位是 1 只前进到 1，i = 1 时才吃掉 10 跳到 3，返回 3 == 2 即 false，正确答案是 true（11 本身就是一个完整的 2 比特字符，不能拆）。

错误写法：返回 i == n 而不是 i == n - 1；用例 bits = [0] → i 停在 0，返回 0 == 1 即 false，正确答案是 true，判据整体反了。

错误写法：直接返回 bits[n-1] == 0；用例 bits = [1, 1, 1, 0] → 末位确实是 0 故返回 true，但它被 10 吞掉了，正确答案是 false。题目保证末位为 0，所以这个判据恒为真，毫无信息量。

错误写法：改用逆向数 1 的解法，但起点取成最后一位而不是倒数第二位；用例 bits = [1, 0] → 从末位的 0 开始立刻停止，数出 0 个 1 判为偶数返回 true，正确答案是 false；起点必须是倒数第二位，本例从那里数出 1 个 1，奇数故为 false。

错误写法：i += 2 前不确认 i + 1 合法，且在不保证末位为 0 的变形数据上运行；用例 bits = [0, 1] → i 从 1 跳到 3 越过数组，若后续还要读取则越界。

错误写法：用 for (int i = 0; i < n; i++) 配合 if (bits[i] == 1) i++ 的写法，却忘了循环变量自身还会再自增一次；用例 bits = [1, 1, 0] → 每轮实际前进 2 位看似正确，但循环终点仍是 n，无法区分 i == n - 1 与 i == n，判据丢失。

错误写法：用 DP 求「最后一个字符是否为 1 比特」但状态定义成「前 i 位能否合法解析」；用例任意输入 → 由于切分唯一，所有前缀都能合法解析，DP 表恒为真，得不出任何结论，状态定义与问题不匹配。

错误写法：把 1 后面跟的那一位也当成新字符的起点重新判断；用例 bits = [1, 0, 0] → 从下标 1 的 0 开始又解析出一个字符，i 走到 3，返回 false，正确答案是 true。

错误写法：对空数组或长度为 0 的输入不做防护；用例 bits = [] → n - 1 为 -1，循环不执行，返回 0 == -1 即 false；题目保证长度至少为 1，但若把这段代码复用到别处，这个隐患会显形。

相似题目

题目	难度	考察点
91. 解码方法	中等	切分不唯一，同一位置既可单独成字也可与下一位组合，必须用 DP 计数
70. 爬楼梯	简单	同样是「每步走 1 或 2」，但要统计所有走法数量而非模拟唯一的一条
55. 跳跃游戏	中等	步长由数组内容动态决定且可自由选择，靠贪心维护最远可达边界而非逐字符解析