問題（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）表示。
現(xiàn)在給出一個多個比特組成的字符串沐绒。返回最后一個字符是否必須是一比特的字符饶氏。給出的字符串總是以0結(jié)尾呈队。
例1：
輸入：
bits = [1, 1, 1, 0]
輸出：True
解釋：
唯一的解碼方式是兩比特的字符串和一比特的字符人灼。所以最后一個字符是一比特的字符坐昙。例2：
輸入：
bits = [1, 1, 1, 0]
輸出：False
解釋：
唯一的解碼方式是兩比特字符和兩比特字符。所以最后一個字符不是一比特字符溉浙。注意：
- 1 <= len(bits) <= 1000烫止。
- bits[i]永遠(yuǎn)是0或1。
思路：
我們可以找一下規(guī)律：
如果只有一個0肯定是單字符戳稽；
如果有兩個數(shù)字馆蠕，看倒數(shù)第二個是1還是0就可以判斷，是1則可以是雙字符；
如果有三個數(shù)字互躬〔チ蓿看倒數(shù)第二、第三個數(shù)字是什么吼渡，也就是最后的0前面是什么容为，如果是“010”，則可以雙字符寺酪，如果是“110”坎背，則只能單字符，如果“100”或者“000”房维，肯定也只能單字符沼瘫，也即是說，0前面如果緊跟著單數(shù)個1咙俩，則可以雙字符耿戚，如果是雙數(shù)個1（比如0個或2個），則只能單字符阿趁，這個規(guī)律對不對呢膜蛔？
假設(shè)有五個數(shù)字，最后的0前有雙數(shù)個1的話脖阵，比如“11110”皂股、“00110”都只能單字符，如果最后的0前是單數(shù)個1的話命黔，比如“01110”呜呐、“00010”，則可以雙字符悍募，看來這個規(guī)律是對的蘑辑，所以只用判斷最后的0前連續(xù)的1的個數(shù)是單還是雙即可。
代碼（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;
}
};
他山之石
看到別人的一個方法坠宴，遍歷一遍數(shù)組內(nèi)容洋魂，遇到1則前進(jìn)兩步（因為1開頭一定是包含兩個比特的），遇到0則前進(jìn)一步喜鼓。遇到1則令結(jié)果變量為false副砍，遇到0則令結(jié)果變量為true，也就是說庄岖，當(dāng)遍歷完時豁翎，如果最后走的一步恰好為遇到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
