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

发表于 11 天前  13 次阅读


文章目录

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时的用法。

本站文章基于国际协议BY-NA-SA 4.0协议共享;
如未特殊说明,本站文章皆为原创文章,请规范转载。

0

这里是柠檬酱,小水管服务器不要打我QAQ