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

题目描述

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。
现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:

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

示例 2:

1
2
3
4
5
输入: 
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。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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/

1
2
3
4
5
6
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

第二种方法:

1
2
3
4
5
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;