class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
}
};
1980. 找出不同的二进制字符串
给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。
示例 1：
输入：nums = ["01","10"] 输出："11" 解释："11" 没有出现在 nums 中。"00" 也是正确答案。
示例 2：
输入：nums = ["00","01"] 输出："11" 解释："11" 没有出现在 nums 中。"10" 也是正确答案。
示例 3：
输入：nums = ["111","011","001"] 输出："101" 解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。
提示：
n == nums.length1 <= n <= 16nums[i].length == nnums[i] 为 '0' 或 '1'nums 中的所有字符串 互不相同原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2022-12-05 15:48:55
func findDifferentBinaryString(nums []string) string {
has := map[int]bool{}
for _, s := range nums {
v, _ := strconv.ParseInt(s, 2, 64)
has[int(v)] = true
}
v := 0
for has[v] { v++ }
return fmt.Sprintf("%0*b", len(nums[0]), v)
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 9.8 MB, 提交时间: 2022-12-05 15:48:20
/**
* 只要和第i个串下标i的字符 nums[i][i]不同，构造出来的串就和所有的串都不同。
* 只限于串数不超过串长的情况。
*/
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
string ans;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i][i] == '0') {
ans += '1';
} else {
ans += '0';
}
}
return ans;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 14.8 MB, 提交时间: 2022-12-05 15:47:07
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
n = len(nums)
# 预处理对应整数的哈希集合
vals = {int(num, 2) for num in nums}
# 寻找第一个不在哈希集合中的整数
val = 0
while val in vals:
val += 1
# 将整数转化为二进制字符串返回
res = "{:b}".format(val)
return '0' * (n - len(res)) + res