leetcode 717 1-bit and 2-bit Characters

题目地址：https://leetcode.com/articles/1-bit-and-2-bit-characters/

题目描述

有两种特殊字符。第一种字符可以用一比特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.

解题思路

bits是一个由0或者1比特组成的字符串数组，目的是判断最后一个字符是否是一比特字符0

从bits数组的第一位开始
如果在bits数组中遇到1，说明是第二种字符(10或11)，用pop操作连续删掉这两比特；如果bits数组中遇到0，说明是第一种字符(0)，用pop操作删掉这一个比特。
用len()方法判断当前bits的长度，如果len(bits) > 1，说明还没有到最后一个比特字符，重新执行第二步。
当len(bits)<=1时，说明到最后一个比特字符了。此时，如果len(bits) == 0，即数组为空，说明最后一个比特字符0和前面一个1一起被pop出去了，返回False;如果len(bits) == 1，说明最后一个比特字符0是一个一比特字符，返回True。

代码实现

class Solution:
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        i = 0
        while len(bits)-1 > 0:
            if bits[i] == 1:
                bits.pop(i)
                bits.pop(i)
            else:
                bits.pop(i)
        if len(bits) == 0:
            return False
        else:
            return True

官方Solution学习

官网上给出的Solution地址：https://leetcode.com/problems/1-bit-and-2-bit-characters/solution/

class Solution(object):
    def isOneBitCharacter(self, bits):
        i = 0
        while i < len(bits) - 1:
            i += bits[i] + 1
        return i == len(bits) - 1

实现思路：使用i作为增量指针，记录当前遍历到的位置。如果bits[i]=0，则i增加1(btis数组中前进一位)，如果bits[i]=1，则i增加2(btis数组中前进两位)，最后保留bits数组最后一个字符(len(bits)-1)，判断bits数组剩余长度与i的大小(前进了多少位)是否相同，如果相同，说明最后一个比特字符0是一个一比特字符，返回True。否则返回False

第二种方法：

class Solution(object):
    def isOneBitCharacter(self, bits):
        parity = bits.pop()
        while bits and bits.pop(): parity ^= 1
        return parity == 0

实现思路：因为题中设定最后一位字符是0，那么倒数第二个0的位置有以下三种可能：

bits = [….., 0, 0] ，倒数第二个0在倒数第二位
bits = [1, 1, 1, … 1, 0]，没有倒数第二个0
bits = [… 0, …, 0] ，倒数第二个字符在倒数第n位(n>2)

先取出最后一位字符0保存到parity中，然后由倒数第二位开始从右向左遍历，直到遇到倒数第二个0(bits.pop==0) while结束，

通过parity ^= 1检查最后一个0和倒数第二个0之间1的个数：有偶数个1，则parity最后值是0，返回True; 有奇数个1，则parity最后值是1，返回False;