算法-1byte和2byte

算法-1byte和2byte

Posted by limantang on March 22, 2019

1byte和2byte

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

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:

输入: bits = [1, 0, 0] 输出: True 解释: 唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。 示例 2:

输入: bits = [1, 1, 1, 0] 输出: False 解释: 唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。 注意:

1 <= len(bits) <= 1000. bits[i] 总是0 或 1.

    /**
     * @param {number[]} bits
     * @return {boolean}
     */
        
    const isOneBitCharacter = function (bits) {
        const length = bits.length - 1;
        let i = 0;
        while(i < length) {
            if (bits[i] === 1) {
                i += 2;
            } else {
                i += 1;
            }
        }
        return i === bits.length ? false : true;
    };

思路

整体的想法是判断最后一位的0是否和之前的数字配对, 如果最后一位的0是单独的那么最后就返回true 如果最后一位的0是和前一位的1配对那么就返回false 还有一点就是2byte是10或者11而且最后一位只为0 那么可以利用一个指针从第一位开始,如果碰到1就走两步 如果碰到0就走一步。 如果指针正好走到数组的最后一位,那么说明最后一位的0是独立的 如果指针走到数组的倒数第二位,那么说明最后一位的0是和前面的1配对的