3211、生成不含相邻零的二进制字符串-cangjie

题目

3211、生成不含相邻零的二进制字符串

思路

dfs

代码

class Solution {let numRune = [r'0', r'1']func dfs(arr: ArrayList<Rune>, ans: ArrayList<String>,n: Int64):Unit{if(arr.size >= n){ans.insert(0, String(arr))// println("insert ${String(arr)}")return}// println("String(arr) = ${String(arr)}")for(i in 0..=1){// println("for i = ${i}")if(i == 0 && arr[arr.size-1] == r'0'){// println("continue")continue}var tmparr = ArrayList<Rune>(arr)tmparr.insert(arr.size, numRune[i])// println("String(tmparr) before dfs = ${String(tmparr)}")dfs(tmparr, ans, n)// println("String(tmparr) after dfs = ${String(tmparr)}")}// println("return")}func validStrings(n: Int64): ArrayList<String> {var ans = ArrayList<String>()for(i in 0..=1){var arr = ArrayList<Rune>()arr.insert(arr.size, numRune[i])dfs(arr, ans, n)}return ans}
}

复杂度

时间复杂度：O(sizeof(ans))
每个字符位置有0和1两种选择的话是O(2^n)，但是由于做的剪枝，所以相对于全访问，复杂度降低

if(i == 0 && arr[arr.size-1] == r'0'){// println("continue")continue}

空间复杂度：O(n^2)
最深最多保存n个size in 1..n的arr

遇到的坑

1、深浅拷贝问题

var tmparr = ArrayList<Rune>(arr)

如果这一行使用

var tmparr = arr

则在后续修改tmparr的时候，因为是浅拷贝（引用拷贝），因此会直接修改到arr，导致程序出错
n=3时
var tmparr = arr结果

String(arr) = 0
for i = 0
continue
for i = 1
String(tmparr) before dfs = 01
String(arr) = 01
for i = 0
String(tmparr) before dfs = 010
insert 010
String(tmparr) after dfs = 010
for i = 1
String(tmparr) before dfs = 0101
insert 0101
String(tmparr) after dfs = 0101
return
String(tmparr) after dfs = 0101
return
String(arr) = 1
for i = 0
String(tmparr) before dfs = 10
String(arr) = 10
for i = 0
continue
for i = 1
String(tmparr) before dfs = 101
insert 101
String(tmparr) after dfs = 101
return
String(tmparr) after dfs = 101
for i = 1
String(tmparr) before dfs = 1011
insert 1011
String(tmparr) after dfs = 1011
return

var tmparr = ArrayList(arr)结果

String(arr) = 0
for i = 0
continue
for i = 1
String(tmparr) before dfs = 01
String(arr) = 01
for i = 0
String(tmparr) before dfs = 010
insert 010
String(tmparr) after dfs = 010
for i = 1
String(tmparr) before dfs = 011
insert 011
String(tmparr) after dfs = 011
return
String(tmparr) after dfs = 01
return
String(arr) = 1
for i = 0
String(tmparr) before dfs = 10
String(arr) = 10
for i = 0
continue
for i = 1
String(tmparr) before dfs = 101
insert 101
String(tmparr) after dfs = 101
return
String(tmparr) after dfs = 10
for i = 1
String(tmparr) before dfs = 11
String(arr) = 11
for i = 0
String(tmparr) before dfs = 110
insert 110
String(tmparr) after dfs = 110
for i = 1
String(tmparr) before dfs = 111
insert 111
String(tmparr) after dfs = 111
return
String(tmparr) after dfs = 11
return

2、ArrayList 的 insert 位置问题
如果是顺序不敏感的ans，就可以直接在 0 位置插入 String(arr),但是如果是对顺序敏感的arr，则需要插入到队尾，即arr.size,注意不是size-1,相当于end()迭代器的位置
3、Rune(i)使用问题
在一开始写的时候，我尝试过
···cangjie
arr.insert(arr.size, Rune(i))
···
这样会导致乱码

最后还是

let numRune = [r'0', r'1']
arr.insert(arr.size, numRune[I])

结果

cangjie