717. 1 比特与 2 比特字符

🟢   🔖  数组  🔗 力扣 LeetCode

题目

We have two special characters:

• The first character can be represented by one bit 0.
• The second character can be represented by two bits (10 or 11).

Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.

Example 1:

Input: bits = [1,0,0]

Output: true

Explanation: The only way to decode it is two-bit character and one-bit character.

So the last character is one-bit character.

Example 2:

Input: bits = [1,1,1,0]

Output: false

Explanation: The only way to decode it is two-bit character and two-bit character.

So the last character is not one-bit character.

Constraints:

• 1 <= bits.length <= 1000
• bits[i] is either 0 or 1.

题目大意

有两种特殊字符：

• 第一种字符可以用一比特 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

解题思路

利用贪心思想逐步遍历字符：

1. 从数组起始位置开始，读取当前字符：
   • 如果是 1，则表示当前字符是 2 比特字符，需要跳过当前字符及其后一个字符（i += 2）。
   • 如果是 0，则表示当前字符是 1 比特字符，只需跳过当前字符（i += 1）。
   • 循环结束条件是 i < bits.length - 1，保证不越界，并且在判断是否为 1 比特字符之前结束循环。
2. 最终遍历结束时，若指针停留在数组倒数第二位之前，则继续跳过；若正好停留在最后一位，则表示最后一个字符是 1 比特字符。

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 bits 的长度。每次跳跃一个或两个字符，整体只需遍历一次。
• 空间复杂度：O(1)，只使用了常数额外空间。

代码

/**
 * @param {number[]} bits
 * @return {boolean}
 */
var isOneBitCharacter = function (bits) {
	let i = 0;
	while (i < bits.length - 1) {
		// 遍历至倒数第二位
		i += bits[i] + 1; // 根据当前位值跳过对应的比特字符
	}
	return i == bits.length - 1; // 是否停留在最后一位
};

相关题目

题号	标题	题解	标签	难度	力扣
89	格雷编码	[✓]	位运算 数学 回溯	🟠	🀄️ 🔗