jaryue
2023/05/10阅读:4主题:默认主题
leetcode 717. 1 比特与 2 比特字符
题目描述
-
1 比特与 2 比特字符
有两种特殊字符:
第一种字符可以用一比特 0 表示 第二种字符可以用两比特(10 或 11)表示 给你一个以 0 结尾的二进制数组 bits ,如果最后一个字符必须是一个一比特字符,则返回 true 。
示例 1:
输入: bits = [1, 0, 0] 输出: true 解释: 唯一的解码方式是将其解析为一个两比特字符和一个一比特字符。 所以最后一个字符是一比特字符。 示例 2:
输入:bits = [1,1,1,0] 输出:false 解释:唯一的解码方式是将其解析为两比特字符和两比特字符。 所以最后一个字符不是一比特字符。
提示:
1 <= bits.length <= 1000 bits[i] 为 0 或 1
解题思路
两个0之间1的个数
这个题的关键就在于确定两个0之间1的个数,
因为0可以单独出现,亦可以与1一起出现,但是1只能与0一起出现或者成对出现,
所以需要两个0之间的1 的个数为偶数,则为真,否则为假
-
时间复杂度(O()) -
空间复杂度(O())
法2
-
时间复杂度(O()) -
空间复杂度(O())
法3
-
时间复杂度(O()) -
空间复杂度(O())
执行结果
通过遍历二进制数组,按照特定规则移动指针i。如果指针i最终指向数组的倒数第二个元素,那么最后一个字符是一比特字符,返回true;否则,最后一个字符是两比特字符,返回false。
代码中,我们初始化指针i为0,然后进行循环。在每一次循环中,判断当前位置的字符是0还是1。如果是0,表示遇到一比特字符,指针i向后移动1位;如果是1,表示遇到两比特字符,指针i向后移动2位。最后,判断指针i是否指向了数组的倒数第二个元素,如果是,则返回true,否则返回false
法1
func isOneBitCharacter(bits []int) bool {
n := len(bits)
i := 0
for i < n-1 {
if bits[i] == 0 {
i++
} else {
i += 2
}
}
return i == n-1
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 4 ms , 在所有 Go 提交中击败了 68.89% 的用户 内存消耗: 2.6 MB , 在所有 Go 提交中击败了 57.78% 的用户 通过测试用例: 93 / 93 炫耀一下:
作者介绍