leetcode#717 1比特与2比特字符

https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/submissions/

题目描述

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:

输入:
bits = [1, 0, 0]
输出: True
解释:
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。

示例 2:

输入:
bits = [1, 1, 1, 0]
输出: False
解释:
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。

注意:

1 <= len(bits) <= 1000.
bits[i] 总是0 或 1.

思考

很显然，如果一个字符是1的话，那它就可以组成2比特字符（10或者11），如果是0的话，那它只能组成1比特字符（0）。

这样思考，我们可以基于字符串遍历的思想，当我们遇到1的时候，我们可以将指针+2；如果遇到0，就加1。

通过使用vector的size()函数（如[1, 2, 3]的长度为3），我们可以得到字符串的总长度。当我们一直遍历到字符串的末尾时，可能遇到以下三种情况：

• xxxx 000
• xxxx 010
• xxxx 110
• xxxx 100

基础思想是判断倒数第二个字符，如果是1的话，那么一定是以2比特字符结束，false。如果是0的话，那么一定是以1比特字符结束，true。因此我们的目标就是确保遍历到倒数第二个字符。但是以上四种情况中，后两种是可能遍历不到倒数第二个的，即不仅可能跳转到倒数第二个字符，还可能从倒数第三个“1”在+=2后直接跳转到最后一个“0”，以1比特字符结束，直接判定返回true。

代码

class Solution
{
public:
    bool isOneBitCharacter(vector<int> &bits)
    {
        int final = bits.size() - 1;  // 尽量和下标一致
        int i = 0;
        while (i < final - 1)
        {
            if (bits[i] == 0)
            {
                i++;
            }
            else
            {
                i += 2;
                if ( i == final)
                {
                    return true;
                }
            }
        }
        return bits[i] == 0 ? true: false;
    }
};

注意三元运算符配合return时的用法。