leetcode 717. 1 比特与 2 比特字符

leetcode 717. 1 比特与 2 比特字符

题目描述

717. 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 炫耀一下: