标签: 数组
难度: Easy
有两种特殊字符：
0 表示10 或 11）表示给你一个以 0 结尾的二进制数组 bits ，如果最后一个字符必须是一个一比特字符，则返回 true 。
示例 1:
输入: bits = [1, 0, 0] 输出: true 解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。 所以最后一个字符是一比特字符。
示例 2:
输入：bits = [1,1,1,0] 输出：false 解释：唯一的解码方式是将其解析为两比特字符和两比特字符。 所以最后一个字符不是一比特字符。
提示:
1 <= bits.length <= 1000bits[i] 为 0 或 1运行时间: 25 ms
内存: 16.1 MB
class Solution:
def isOneBitCharacter(self, bits: List[int]) -> bool:
i, n = 0, len(bits)
while i < n - 1:
i += bits[i] + 1
return i == n - 1
这个题解使用了贪心算法的思路。从左到右遍历二进制数组，遇到 0 则将指针向右移动一位，遇到 1 则将指针向右移动两位。最后判断指针是否恰好指向最后一个元素，如果是则说明最后一个字符是一比特字符，否则不是。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def isOneBitCharacter(self, bits: List[int]) -> bool:
i, n = 0, len(bits)
while i < n - 1:
# 如果当前位是0，则将指针向右移动一位
# 如果当前位是1，则将指针向右移动两位
i += bits[i] + 1
# 判断指针是否恰好指向最后一个元素
return i == n - 1
在这个算法中，对于非最后一个位置的比特字符，没有特殊处理或判断。算法主要关注如何根据当前比特的值（0或1）来决定指针的移动步数（1步或2步）。对于0比特，直接移动一步，对于1比特，认为其后紧跟着的比特与其组成一个两比特字符，因此移动两步。这种处理方式保证了遍历过程中不会漏掉任何字符的解析。
贪心算法在此确保指针移动步数的正确性依赖于给定数据的规则性，即1总是表示开始一个两比特字符（10或11），而0总是表示一个单独的一比特字符。由于数组是根据这些规则构造的，按照这种贪心处理不会跳过任何有效的解码方法。每次遇到1或0时，根据它们预定义的意义移动相应的步数，从而正确解析序列。
是的，这种处理考虑了所有可能的两比特字符组合。无论紧跟在1后面的比特是0还是1（形成10或11），指针都会移动两位。这确保了无论两比特字符的第二个比特是什么，都被正确地识别为一个整体，并且指针正确跳过这两个比特。
在正常情况下，这种方法是有效的，因为算法设计时假设了数组是有效构造的，即不会以1结尾（这样最后一个比特字符不能是一个单独的0）。如果数组确实以1结束，这将违反题设条件（最后一个字符必须是一比特字符）。因此，只要输入符合题目的要求，这种方法就不会出现误判。