问题（Easy）：
We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).
Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.
Example 1:
Input:
bits = [1, 0, 0]
Output: True
Explanation:
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.Example 2:
Input:
bits = [1, 1, 1, 0]
Output: False
Explanation:
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.Note:
- 1 <= len(bits) <= 1000.
- bits[i] is always 0 or 1.
大意：
我们有两个特殊的字符，第一个字符可以用一个比特的0表示，第二个字符可以用两个比特（10或者11）表示。
现在给出一个多个比特组成的字符串。返回最后一个字符是否必须是一比特的字符。给出的字符串总是以0结尾。
例1：
输入：
bits = [1, 1, 1, 0]
输出：True
解释：
唯一的解码方式是两比特的字符串和一比特的字符。所以最后一个字符是一比特的字符。例2：
输入：
bits = [1, 1, 1, 0]
输出：False
解释：
唯一的解码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。注意：
- 1 <= len(bits) <= 1000。
- bits[i]永远是0或1。
思路：
我们可以找一下规律：
如果只有一个0肯定是单字符；
如果有两个数字，看倒数第二个是1还是0就可以判断，是1则可以是双字符；
如果有三个数字。看倒数第二、第三个数字是什么，也就是最后的0前面是什么，如果是“010”，则可以双字符，如果是“110”，则只能单字符，如果“100”或者“000”，肯定也只能单字符，也即是说，0前面如果紧跟着单数个1，则可以双字符，如果是双数个1（比如0个或2个），则只能单字符，这个规律对不对呢？
假设有五个数字，最后的0前有双数个1的话，比如“11110”、“00110”都只能单字符，如果最后的0前是单数个1的话，比如“01110”、“00010”，则可以双字符，看来这个规律是对的，所以只用判断最后的0前连续的1的个数是单还是双即可。
代码（C++）：
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
int len = bits.size();
if (len == 1) return true;
if (bits[len-2] == 0) return true;
else {
int num = 1;
int index = len - 3;
while (index >= 0) {
if (bits[index] == 1) num++;
else break;
index--;
}
if (num % 2 == 0) return true;
}
return false;
}
};
他山之石
看到别人的一个方法，遍历一遍数组内容，遇到1则前进两步（因为1开头一定是包含两个比特的），遇到0则前进一步。遇到1则令结果变量为false，遇到0则令结果变量为true，也就是说，当遍历完时，如果最后走的一步恰好为遇到1时的两步，则返回为false，如果最后走的一步是遇到0时的一步，则返回为true。
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
bool c;
for (int i = 0; i < bits.size();) {
if (bits[i]) c = 0, i+=2;
else c = 1, ++i;
}
return c;
}
};
合集：https://github.com/Cloudox/LeetCode-Record
