题目连接1980. 找出不同的二进制字符串中等算法原理解法一暴力枚举之前用到显示回溯和隐式回溯的题目E.位运算-基础——3211. 生成不含相邻零的二进制字符串显式回溯与隐式回溯的区别底层都是回溯思想只是写法随容器变而已①固定长度结构char []、数组→ 天然适合隐式回溯写法更干净②变长结构StringBuffer、List、Builder→ 必须显式回溯不然必错写法一StringBuffer→显式回溯2ms击败39.13%时间复杂度O (n × 2ⁿ)①将nums中所有数全扔进Set里方便判断是否存在②显式递归回溯给每一位填上0或1③递归出口当长度达到n时判断哈希表中是否存在过若不存在直接返回这个字符串④回溯常用到cur.deleteCharAt(int index)写法二数组直接覆盖→隐式回溯1ms击败73.91%时间复杂度O (n × 2ⁿ)由于字符串长度固定因此我们可以采用数组直接覆盖来实现原本的回溯过程其余写法与写法一相同写法三枚举二进制位对应的整数4ms击败4.35%时间复杂度O (n × 2ⁿ)先把nums中每个二进制字符串对应的整数存进Set里由于每个二进制字符串长度为n因此我们可以遍历2ⁿ-1在内的所有整数只要Set里没有就说明我们找到了答案需要注意的是 Integer.toBinaryString(String s,2)返回的二进制字符串是不含前置0的因此我们需要手动添加前置0直至长度达到n写法三的优化4ms击败4.35%时间复杂度O (2ⁿ)优化点1我们可以用一个整数ret代替遍历因为我们只需找到一个不在Set中的数即可无需统计个数因此只要Set里存在ret就可以ret遍历下个数优化点2手动添加前置0时也可以避免循环直接用0.repeat(int n)生成n个0进行拼接解法二康托对角线0ms击败100.00%时间复杂度O(N)①对于nums中的第 i 个字符串索引为 i 取它的第 i 位字符对角线位置②对该位字符取反0→11→0作为结果字符串的第 i 位③最终构造的字符串与nums中每个字符至少有一个对角线为不同因此必然不在nums中举个例子nums[111,011,000]ret[0]0≠1ret[1]1≠0ret[2]1≠0得出ret001与nums中都不同反证法比如当ret的第一位0001与后续000第一位0000相同时ret也不能与000完全相同因为它们在第三位上存在取反Java代码class Solution { //解法一暴力枚举-写法一显式递归 int n; private StringBuffer curnew StringBuffer(); public String findDifferentBinaryString(String[] nums) { nnums.length; SetString hashnew HashSet(); for(String s:nums) hash.add(s); return dfs(0,cur,hash); } private String dfs(int i,StringBuffer cur,SetString hash){ if(in) return hash.contains(cur.toString())?:cur.toString(); cur.append(0); String s0dfs(i1,cur,hash); if(s0!) return s0; cur.deleteCharAt(cur.length()-1);//回溯 cur.append(1); String s1dfs(i1,cur,hash); if(s1!) return s1; cur.deleteCharAt(cur.length()-1);//回溯 //照顾编译器因为题目保证有解 return ; } }class Solution { //解法一暴力枚举-写法二隐式回溯 int n; char[] cur; public String findDifferentBinaryString(String[] nums) { nnums.length; curnew char[n]; SetString hashnew HashSet(); for(String s:nums) hash.add(s); return dfs(0,cur,hash); } private String dfs(int i,char[] cur,SetString hash){ if(in) return hash.contains(new String(cur))?:new String(cur); cur[i]0; String s0dfs(i1,cur,hash); if(s0!) return s0; cur[i]1; String s1dfs(i1,cur,hash); if(s1!) return s1; //照顾编译器因为题目保证有解 return ; } }class Solution { //解法一暴力枚举-写法三枚举二进制对应的整数 public String findDifferentBinaryString(String[] nums) { int nnums.length; SetInteger hashnew HashSet(); //转成整型存进哈希表 for(String s:nums) hash.add(Integer.parseInt(s,2)); for(int i0;i(1n);i){ if(!hash.contains(i)){ String binInteger.toBinaryString(i); //手动添加前置0 while(bin.length()n) bin0bin; return bin; } } //照顾编译器因为题目保证有解 return ; } }class Solution { //解法一暴力枚举-写法三枚举二进制对应的整数(优化版) public String findDifferentBinaryString(String[] nums) { SetInteger hashnew HashSet(); //转成整型存进哈希表 for(String s:nums) hash.add(Integer.parseInt(s,2)); int ret0; while(hash.contains(ret)) ret; String binInteger.toBinaryString(ret); return 0.repeat(nums.length-bin.length())bin; } }class Solution { //解法二康托对角线 public String findDifferentBinaryString(String[] nums) { int nnums.length; char[] retnew char[n]; for(int i0;in;i) ret[i](char)(nums[i].charAt(i)^1); return new String(ret); } }