LeetCode 3211.生成不含相邻零的二进制字符串：二进制枚举+位运算优化

【LetMeFly】3211.生成不含相邻零的二进制字符串：二进制枚举+位运算优化

力扣题目链接：https://leetcode.cn/problems/generate-binary-strings-without-adjacent-zeros/

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。

返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

 

示例 1：

输出： ["010","011","101","110","111"]

解释：

长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。

示例 2：

输出： ["0","1"]

解释：

长度为 1 的有效字符串有："0" 和 "1"。

 

提示：

• 1 <= n <= 18

解题方法：二进制枚举

不位运算优化的话其实很简单，从$0$枚举到$2^n-1$，看看哪个数字对应的字符串的二进制没有连续的$0$即可。这样时间复杂度为$n{2}^n$，$18\times 2^{18}=4,718,592$，完全在合理范围内。

有没有一种办法在$O(1)$的时间复杂度内判定一个数$i$的二进制下有没有连续两个$0$呢？还真有：

将$i$二进制下低$n$位取反（$0$变$1$、$1$变$0$），$i$二进制下没有连续两个$0$等价于$X$二进制下没有连续两个$1$。

$x$二进制下没有相邻的$1$等价于$x\&(x>>1)=0$。

因此问题变成了“如何快速将$i$低$n$位取反”。也很简单，$i$异或一个$\mathrm{1111..1}$即可。其中$111.1$一共有$n$位，其值等于$(1<<n)-1$。

• 时间复杂度$O(2^n)$
• 空间复杂度$O(1)$，力扣返回值不计入算法空间复杂度

AC代码

C++

class Solution {
public:vector<string> validStrings(int n) {vector<string> ans;int mask = (1 << n) - 1;for (int i = 0; i < (1 << n); i++) {int x = i ^ mask;  // 取反if (!(x & (x >> 1))) {ans.push_back(bitset<18>(i).to_string().substr(18 - n));}}return ans;}
};

Go

package mainimport "fmt"func validStrings(n int) []string {ans := make([]string, 0)mask := (1 << n) - 1for i := 0; i < (1 << n); i++ {x := i ^ maskif (x & (x >> 1) == 0) {ans = append(ans, fmt.Sprintf("%0*b", n, i))}}return ans
}

Java

import java.util.List;
import java.util.ArrayList;class Solution {public List<String> validStrings(int n) {List<String> ans = new ArrayList<>();int mask = (1 << n) - 1;for (int i = 0; i < (1 << n); i++) {int x = i ^ mask;if ((x & (x >> 1)) == 0) {ans.add(Integer.toBinaryString((1 << n) | i).substring(1));  // 往n位“带有前导0的二进制”的前面加个1，再去掉}}return ans;}
}

Python

from typing import Listclass Solution:def validStrings(self, n: int) -> List[str]:ans = []mask = (1 << n) - 1for i in range(1 << n):x = i ^ maskif not x & (x >> 1):ans.append(f'{i:0{n}b}')return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143352841