目标
给你一个正整数 n。
如果一个二进制字符串 x 的所有长度为 2 的 子字符串 中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。
返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。
示例 1：
输入： n = 3
输出： ["010","011","101","110","111"]
解释：
长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。示例 2：
输入： n = 1
输出： ["0","1"]
解释：
长度为 1 的有效字符串有："0" 和 "1"。说明：
- 1 <= n <= 18
思路
示例2让人困惑，字符串 0 并没有长度为 2 的子字符串，更别提包含至少一个 1 了，但它是有效字符串。
还是按照题目名称来做吧，生成长度为 n，不含相邻零的二进制字符串。直接回溯即可。
官网题解还提出了一种位运算的解法，主要思想就是将 二进制字符串 视为 数字的二进制表示，问题转化为 0 ~ 2^n - 1 的数字中不含相邻零的个数。由于超出 n 的位数不在我们的考虑范围，为了简化处理，可以直接将数字的低 n 位取反，x ^ ((1 << n) - 1))。1 << n 从 0 开始计向左移 n 位，再减 1，得到低 n 位全为 1 的数字，对它取异或相当于低 n 位取反。问题转换为 数字中是否存在连续的 1。针对每一个数字，无需遍历每一位，直接使用 x & (x >> 1) 是否等于 0 来判断是否含有相邻的 1。相当于将每一位与它前面的位相与，如果存在相邻的 1 就会存在某个位相与的结果为 1 使最终结果不为 0。
代码
/**
* @date 2024-10-29 0:23
*/
public class ValidStrings3211 {
List<String> res;
char[] path;
int n;
public List<String> validStrings(int n) {
res = new ArrayList<>();
path = new char[n];
this.n = n;
backTracing('1', 0);
return res;
}
public void backTracing(char prev, int i) {
if (i == n) {
res.add(new String(path));
return;
}
path[i] = '1';
int next = i + 1;
backTracing('1', next);
if (prev != '0') {
path[i] = '0';
backTracing('0', next);
}
}
}
性能
