前言
经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。接下来重点专项练习,加强重难点知识的练习。
描述
给你一个正整数
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
实现原理与步骤
本题使用了移位、异或、或、与的二进制bit位的大部分操作。对二进制bit位不熟悉的可以多加练习
1.构建n位的全1的掩码mask。
2.遍历n位的二进制数,将i与mask异或将0转换成1后为x。
3.x>>1&x判断是存在连续的1.
4.通过1<<n|i,将n为的二进制最高位前加1.再通过substring输出。
代码实现
import java.util.*;
public class Main3 {
public static void main(String[] args) {
Main3 main3=new Main3();
List<String> res=main3.validStrings(3);
System.out.println(res.toString());
}
public List<String> validStrings(int n) {
List<String> ans = new ArrayList<>();
//构建位数为n的掩码,示例1中n为3,则mask为111
int mask = (1 << n) - 1;
for (int i = 0; i < (1 << n); i++) {
//i与比特位都是1的mask异或,则标记0的位置位1.
int x = mask ^ i;
//x左移1位后与自身与为0,则x不存在练习的1.
if (((x >> 1) & x) == 0) {
//此处Integer.toBinaryString由于会自动移除前面的0,则最第一位补1再通过substring移除
ans.add(Integer.toBinaryString((1 << n) | i).substring(1));
}
}
return ans;
}
}