LeetCode笔记：717. 1-bit and 2-bit

问题（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）表示。

现在给出一个多个比特组成的字符串。返回最后一个字符是否必须是一比特的字符。给出的字符串总是以0结尾。

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

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

注意：

• 1 <= len(bits) <= 1000。
• bits[i]永远是0或1。

思路：

我们可以找一下规律：

如果只有一个0肯定是单字符；

如果有两个数字，看倒数第二个是1还是0就可以判断，是1则可以是双字符；

如果有三个数字。看倒数第二、第三个数字是什么，也就是最后的0前面是什么，如果是“010”，则可以双字符，如果是“110”，则只能单字符，如果“100”或者“000”，肯定也只能单字符，也即是说，0前面如果紧跟着单数个1，则可以双字符，如果是双数个1（比如0个或2个），则只能单字符，这个规律对不对呢？

假设有五个数字，最后的0前有双数个1的话，比如“11110”、“00110”都只能单字符，如果最后的0前是单数个1的话，比如“01110”、“00010”，则可以双字符，看来这个规律是对的，所以只用判断最后的0前连续的1的个数是单还是双即可。

代码（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;
    }
};

他山之石

看到别人的一个方法，遍历一遍数组内容，遇到1则前进两步（因为1开头一定是包含两个比特的），遇到0则前进一步。遇到1则令结果变量为false，遇到0则令结果变量为true，也就是说，当遍历完时，如果最后走的一步恰好为遇到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

查看作者首页