2025-02-24：生成不含相邻零的二进制字符串。用go语言，给定一个正整数 n。
一个二进制字符串 x 被称为有效字符串，如果它的所有长度为 2 的子字符串中至少包含一个 "1"。
你的任务是返回所有长度为 n 的有效字符串，顺序可以任意。
1 <= n <= 18。
输入： n = 3。
输出： ["010","011","101","110","111"]。
解释：
长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。
答案2025-02-24：
chatgpt[1]
题目来自leetcode3211。
大体步骤如下：1.初始化：开始时，我们先定义一个空数组 res 用于存储最终结果，然后确定一个长度为 n 的二进制字符串 temp，初始内容为空。
2.递归生成有效字符串：
• 定义一个递归函数，该函数接收一个当前位置 pos 和当前的二进制字符串 temp。• 从当前位置 pos 开始，尝试添加 '0' 和 '1' 到当前的二进制字符串 temp，并检查是否生成的子串符合条件（不含相邻零）。• 如果符合条件，继续递归调用函数，向下一个位置前进。• 当递归到字符串长度为 n 时，将有效的二进制字符串存入 res 中。3.回溯：
• 在递归结束后，回溯到上一个位置，尝试其他可能性，以生成所有有效的二进制字符串。4.总的时间复杂度：
• 由于要生成所有长度为 n 的有效字符串，对于每个位置有两种选择，时间复杂度为 O(2^n)。5.总的额外空间复杂度：
• 在递归过程中，需要保存当前的二进制字符串以及结果数组，额外空间为 O(2^n)。综上所述，通过递归生成所有符合条件的二进制字符串，时间复杂度为 O(2^n)，额外空间复杂度为 O(2^n)。这种方法会枚举所有可能的二进制字符串，并检查它们是否符合条件。
Go完整代码如下：package mainimport ( "fmt")func validStrings(n int) []string { res := []string{} mask := (1 << n) - 1 for i := 0; i < 1<<n; i++ { t := mask ^ i if t>>1&t == 0 { res = append(res, fmt.Sprintf("%0*b", n, i)) } } return res}func main() { n := 3 result := validStrings(n) fmt.Println(result)}
在这里插入图片描述
Rust完整代码如下：
fn valid_strings(n: i32) -> Vec<String> { let mut res: Vec<String> = Vec::new(); let mask = (1 << n) - 1; for i in 0..(1 << n) { let t = mask ^ i; if t >> 1 & t == 0 { res.push(format!("{:0width$b}", i, width = n as usize)); } } res}fn main() { let n = 3; let result = valid_strings(n); println!("{:?}", result);}
在这里插入图片描述
Python完整代码如下：
# -*-coding:utf-8-*-def valid_strings(n): res = [] mask = (1 << n) - 1 for i in range(1 << n): t = mask ^ i if t >> 1 & t == 0: res.append(format(i, f'0{n}b')) return resdef main(): n = 3 result = valid_strings(n) print(result)if __name__ == "__main__": main()
在这里插入图片描述
引用链接[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP
