力扣算法 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

解法1：常规解法，时间复杂度O(n)

解析：该解法是遍历bits数组，两种字符，可以看第一个字符是是否是0，如果是0，说明是1比特，再次判断下数组是否遍历完了；如果不是0，那么就是10或11，那么就跳两个步长，进入下一次循环

class Solution {public boolean isOneBitCharacter(int[] bits) {for ( int i = 0; i < bits.length;){if ( bits[i] == 0){i++;if (i == bits.length) {return true;}}else{i+=2;}} return false;}
}

解法2：正则表达式解法，时间复杂度O(1)

解析：

1. 先将bits数组转为字符串
2. 0$代表匹配字符串的末尾的单个0；
3. (11)\* 匹配连续成对出现的 "11"（零次或多次）。 ?> 是“原子组”语法。它表示一旦该组匹配成功，引擎将不会回退或重新尝试匹配组内的模式。这能防止回溯，确保所有成对的 "11"被牢牢锁定为完整的两比特字符，不会在后续匹配失败时被拆开。
4. (^|0) 这是一个关键的分隔条件。它匹配两种位置：
   1. ^：字符串的开头。
   2. 0：一个单独的、完整的一比特字符 0。
      它的作用是确保在它后面出现的成对 "11"之前，是一个合法的字符边界。因为 0表示一个字符的结束，而 1必须和后面一位组成一个字符。
5. RegexOptions.RightToLeft：指示正则表达式引擎从右向左进行匹配

using System.Text.RegularExpressions;
public class Solution {public bool IsOneBitCharacter(int[] bits) {return Regex.IsMatch(string.Join("", bits), @"(^|0)(?>(11)*)0$", RegexOptions.RightToLeft);}
}