题目描述 1比特与2比特字符

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

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

示例 1:

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

示例 2:

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

解题思路

• 嗯，我的垃圾思路就是从前往后遍历，垃圾第一名。
• 大佬思路：从后往前偶数(包括0)个连续1就返回TRUE。
  设想给定的数组为[xx....xx011...110]，0之前的1为N(N = 0,1,2...)个，事实上这一串连续1之前的“零”将整个bits截为两段，不管这个“零”是一个单独的bit "0" 还是和它前面的bit "1" 组成两个bit "10" ,它都不会对后面的bits" 11...110 "有任何影响。所以我们只用统计后面这部分连续的1有多少个就好了，偶数个为TRUE，奇数个为FALSE。

代码

    class Solution {
    public:
        bool isOneBitCharacter(vector<int>& bits) {
            int i = 0;
            for(; i < bits.size() - 1; ){
                if(bits[i] == 1){
                    i += 2;
                }
                else{
                    i++;
                }
            }
            if(i == bits.size() - 1){
                return true;
            }
            return false;
        }
    };

大佬思路代码

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int count = 0, i = bits.size()-2;
        while(i>=0&&bits[i--]==1){
            count++;
        }
        return count%2==0;
    }
};