717 1-bit and 2-bit Characters

题目

717 1-bit and 2-bit Characters

题解

题目要求：对一个只包含0和1的二进制序列，规定编码方式如下：一位字符，以0表示；两位字符，以11或10表示。现在规定二进制序列的最后一位总是0，试判断该序列的最后一个字符是否只能被解码为一位字符。

由于可能的编码只有0、11、10三种，在最后一位为0的情况下，序列中的最后一个字符只有0和10这两种可能。只知道最后一个字符是不够的，我们需要结合前面的二进制位进行判断。

首先对倒数第二位进行分析，倒数的第二位有两种情况：

1. 为0，此时最后两位为00，因此最后一个字符必须为一位字符
2. 为1，此时最后两位为10，最后一个字符的编码可能是0也可能是10。如果要使最后一个字符的编码为0，那么倒数第二位的1必须作为前一个合法编码的一部分被消耗掉，唯一的可能就是作为编码11中的第二个1被消耗掉。 要判断倒数第二位是否属于编码11，我们需要向前看更多的位来进行判断。需要注意的是，只判断倒数第三位是否为1是不够的，因为这个1有可能是更前面的11编码的一部分，一个例子是1110。 注意到含有1的编码方式中，编码11含有两个1，而编码10只含有一个1，因此我们可以从倒数第二位的1开始向前扫描出一段连续的1，并记录其中1的个数。只要连续的1的个数为偶数个，就说明倒数第二位的1就必然属于编码11。

由于算法最多对输入扫描一次，因此时间复杂度为O(n)；因为算法只记录连续的1的个数，所以空间复杂度为O(1)。

代码

#include <vector>

using namespace std;

class Solution {
public:
	bool isOneBitCharacter(vector<int>& bits) {
		int oneCount = 0;
		int i = bits.size() - 1;
		do {
			if (bits[i] == 1) {
				oneCount++;
			}
			i--;
		} while (bits[i] == 1 && i >= 0);

		return oneCount % 2 == 0;
	}
};