1980. Find Unique Binary String
题目 1980. Find Unique Binary String
思路分析
康托对角线法 (Cantor's Diagonalization)
这是一道经典的数学题变种。我们不需要枚举所有可能性，我们只需要构造出一个和现有所有字符串都不同的串即可。
核心逻辑：
只要我们构造的字符串 ans，满足：
- 第 0 位字符，和
nums[0]的第 0 位不同 \(\to\) 保证了ans不等于nums[0] - 第 1 位字符，和
nums[1]的第 1 位不同 \(\to\) 保证了ans不等于nums[1] - ...
- 第 i 位字符，和
nums[i]的第 i 位不同 \(\to\) 保证了ans不等于nums[i]
这样构造出来的 ans，就一定不等于 nums 中的任何一个字符串！
举例：
nums = ["01", "10"]
- 看
nums[0]("01") 的第 0 位是'0'\(\to\) 我们的结果第 0 位取反，选'1'。 - 看
nums[1]("10") 的第 1 位是'0'\(\to\) 我们的结果第 1 位取反，选'1'。 - 结果是
"11"。
代码实现
class Solution {
public String findDifferentBinaryString(String[] nums) {
int n=nums.length;
Set<String> set = new HashSet<>();
for(String s:nums){
set.add(s);
}
for(int i=0;i<(1<<n);i++){
StringBuilder sb = new StringBuilder(Integer.toBinaryString(i));
//前导零
while(sb.length()<n){
sb.insert(0,"0");
}
String current = sb.toString();
if(!set.contains(current)){
return current;
}
}
return "";
}
}
class Solution {
public String findDifferentBinaryString(String[] nums) {
int n=nums.length;
Set<String> set = new HashSet<>();
for(String s:nums){
set.add(s);
}
for(int i=0;i<(1<<n);i++){
/*
利用 1 << n (即 2^n) 强行在最前面加一个 1，把后面撑开，
然后转成字符串后截取掉最前面的 1。
假设 n=5，要把 5 (101) 变成 00101：
1 << 5 是 100000 (二进制)。
(1 << 5) | 5 变成 100101。
转成字符串 "100101"。
从索引 1 开始截取 substring(1)
to "00101"。
*/
String current = Integer.toBinaryString((1<<n)|i).substring(1);
if(!set.contains(current)){
return current;
}
}
return "";
}
}
class Solution {
public String findDifferentBinaryString(String[] nums) {
StringBuilder sb = new StringBuilder();
// 只需要遍历一次数组
for (int i = 0; i < nums.length; i++) {
// 取出第 i 个字符串的第 i 个字符
char c = nums[i].charAt(i);
// 如果是 '0' 就变成 '1'，如果是 '1' 就变成 '0'
// 并拼接到结果中
sb.append(c == '0' ? '1' : '0');
}
return sb.toString();
}
}
💬 评论