题目：
有两种特殊字符。第一种字符可以用一比特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.
解答：
解法1：
思路：如果最后一位的前一位是0，那该字符是一字节字符，所以只要判断前一位是1的情况；
根据1的个数，即可以判断该字符的类型： 只有两种情况
1）xxx0(1111*n)0 : 只要判断最后一个零与倒数第一个0之间1的个数，便可以判断最后的0与1有无关系
2) (111*n)0: 若除了字符最后一位的零之外没有其他0， 则直接判断1的个数
*： 1的个数与字符类型的关系是： $$n \% 2 === 0$$
以下是以递归实现，速度 68 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var isOneBitCharacter = function (bits) {
if (bits.length === 1) return true
return check(bits, 1)
function check (bits, i) {
var len = bits.length
if (bits[len - 1 - i] === 0) return i % 2 === 1
else {
if (len === i + 1) return i % 2 === 0
else if (len > i + 1) {
return check(bits, i + 1)
}
}
}
}
|
解法2：
以下是直接找最后的0与（倒数的0/ 或者最后的1）之间的1的个数来判断，
速度 116 ms
1
2
3
4
5
6
7
8
9
10
| const isOneBitCharacter2 = function (bits) {
if (bits.length === 1) return true
for (let i = 2, len = bits.length; i <= len; i++) {
if (bits[len - i] === 0) {
return (i - 2) % 2 === 0
}
}
return (bits.length - 1) % 2 === 0
}
|
结果递归的实现比较迅速
