给你一个正整数 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

 我的解答：

java">class Solution {public List<String> validStrings(int n) {List<String> list = new ArrayList<String>();if(n == 1){list.add("0");list.add("1");return list;}int num = (int)Math.pow(2,n) - 1;StringBuilder sb = new StringBuilder(n);for(int i = 0; i < n ; i++){sb.append("0");}for(int i = 1; i <= num ; i++){// 将数值转换为二进制字符串String str = Integer.toBinaryString(i);// 二进制字符串长度小于等于n-2，即前两位为0，不符合长度为2的子字符串包含至少一个“1”if(str.length() <= n - 2) continue;sb.replace(n - str.length(),n,str);boolean isTrue = true;for(int j = 0; j < n - 1 ; j++){// 如果相邻元素都为0，则标识不符合条件并退出循环if(sb.charAt(j) == '0' && sb.charAt(j + 1) == '0') {isTrue = false;break;}}if(isTrue){list.add(sb.toString());}}return list;}
}