Title
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时，是否可以，这题就很良心了，开始没读题，然后以为是否可以表达成功，结果没考虑最后一个元素，后来改了一改，加了个count便ac了，其实也可以当最后一个元素为0时，去掉最后一个元素，看是否表达成功
Solution
这个是没去掉最后一个元素做的，ac
//cpp:
class Solution {
public:
int count = 0;
bool isOne(vector<int>& bits, int start) {
if (start >= bits.size()) {
return true;
}
if (bits[start] == 0) {
if (start == bits.size() - 1)
count++;
return isOne(bits, start + 1) || isTwo(bits, start + 1);
}
else
return false;
}
bool isTwo(vector<int>& bits, int start) {
if (start >= bits.size())
return true;
if (start + 1 < bits.size() && bits[start] == 1)
return isOne(bits, start + 2) || isTwo(bits, start + 2);
else
return false;
}
bool isOneBitCharacter(vector<int>& bits) {
isOne(bits, 0);
isTwo(bits, 0);
if (count > 0)
return true;
else
return false;
}
};
去掉最后一个元素，ac
class Solution {
public:
bool isOne(vector<int>& bits, int start) {
if (start >= bits.size()) {
return true;
}
if (bits[start] == 0) {
return isOne(bits, start + 1) || isTwo(bits, start + 1);
}
else
return false;
}
bool isTwo(vector<int>& bits, int start) {
if (start >= bits.size())
return true;
if (start + 1 < bits.size() && bits[start] == 1)
return isOne(bits, start + 2) || isTwo(bits, start + 2);
else
return false;
}
bool isOneBitCharacter(vector<int>& bits) {
if (bits[bits.size() - 1] == 1)
return false;
else {
bits.erase(bits.end() - 1);
}
isOne(bits, 0);
isTwo(bits, 0);
return isOne(bits, 0) || isTwo(bits, 0);
}
};
原来有更简单的方法，对于位置i,如果是0，则下一个元素必定为1，如果为1，则是0/1，因此用i，如果为0，i+1,如果为1，i+2。这么跳。
class Solution {
public boolean isOneBitCharacter(int[] bits) {
int i = 0;
while (i < bits.length - 1) {
i += bits[i] + 1;
}
return i == bits.length - 1;
}
}
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
int n=bits.size();
int i=n-2;
while(i>=0&&bits[i]>0) i--;
return (n-i)%2==0;
}
};