717. 1比特与2比特字符

一、题目描述

有两种特殊字符。

• 第一种字符可以用一比特0来表示。
• 第二种字符可以用两比特(10或11)来表示。

现给一个由若干比特组成的字符串。

问最后一个字符是否必定为一个一比特字符。

给定的字符串总是由0结束。

二、解题思路

我的想法是，既然最后一个是0，而且要识别这个0是不是1bit，那么就从后面往前找，直到找到不符合2bit字符的情况为止。

1. 前一个数字是0，那么00在一起，最后的0肯定是1bit；
2. 前一个数字是1，再前一个也是1，也就是110，那么无法判断，继续往前；
3. 前一个数字是1，再前一个是0，也就是010，那么后面的0肯定是属于前面的1的，肯定是2bit。

根据这样从后往前判断，就可以判断出来结果。

不过官方的解法更简洁，只要判断最后2个0之间的1的数量，就可以识别出最后一个0是不是1bit：

1. 如果最后2个0之间的1数量是偶数，说明这些1都是11组合的，所以最后1个0肯定是1bit；
2. 如果最后2个0之间的1数量是奇数，说明除了最后1个1以外，其他都是11组合，最后一个则是10组合，所以是2bit。

虽然原理上差不太多，不过官方解法确实简洁~~~

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

/**
 * 最后一个字符是否必定为一个一比特字符
 *
 * @param bits 数组
 * @return true/false
 */
private boolean isOneBitCharacter(int[] bits) {
    if (bits.length <= 0 || bits[bits.length - 1] != 0) {
        return false;
    }
    int rp = bits.length - 2;
    while (rp >= 0) {
        if (bits[rp] == 0) {
            // 如果是00，那后面的0肯定是单独的0
            return true;
        }
        if (rp - 1 >= 0 && bits[rp - 1] == 1) {
            // 前面是11，忽略它们并继续往前找
            rp -= 2;
        } else {
            // 前面是01，那么后面的0肯定属于前面的1
            return false;
        }
    }
    return true;
}

官方解法：

/**
 * 最后一个字符是否必定为一个一比特字符
 *
 * @param bits 数组
 * @return true/false
 */
private boolean isOneBitCharacter(int[] bits) {
    int i = bits.length - 2;
    while (i >= 0 && bits[i] > 0) i--;
    return (bits.length - i) % 2 == 0;
}