1bit与2bit字符——简单模拟题
目录
题目
题目详解
读懂题：
此题是为了让最后以一个字符解码，也就是 $0$ ，而含 $1$ 的只能是两个字符进行解码，所以遇到 $1$ 就必须确保后面有 $0$ 或 $1$ 来用于抵消。
解题法：
- 法一：正向遍历法 直接通过遇到 $0$ 走一步，遇到 $1$ 走两步，再看最后是否能恰好走到最后一个 $0$ 的位置，如果能则 $true$ 否则 $false$ 。
- 法二：反向遍历法 由于遇到 $0$ 能直接跳过，而遇到 $1$ 则后面必须含有一个字符被抵消，所以为了让最后一个 $0$ 不被抵消，它前面的连续 $1$ 应该要为偶数个，否则 $0$ 将会被抵消。故具体做法直接记录最后一个 $0$ 前面的 $1$ 的个数即可得出答案。
解题代码
法一：
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
int sz = bits.size();
if(sz<2)
return true;
int start = 0;
while(start<sz-1){
if(bits[start]==0)
start++;
else{
start += 2;
}
}
return start==sz-1;
}
};
法二：
class Solution {
public:
bool isOneBitCharacter(vector<int>& bits) {
return find(rbegin(bits)+1, rend(bits), 0) - rbegin(bits) & 1;
}
};