难度: Medium
给你一个字符串数组 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 中的所有字符串 互不相同运行时间: 26 ms
内存: 15.9 MB
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
n=len(nums)
nums=set(map(lambda x:int(x,2),nums))
for i in range(1<<n):
if i not in nums:
ans=bin(i)[2:]
if len(ans)<n:
ans="0"*(n-len(ans))+ans
return ans
本题解首先将输入的二进制字符串数组转换为整数集合，方便后续查找。接着，生成从0到2的n次方减1（包含所有可能的n位二进制数）的所有整数，检查每个整数是否不在之前转换的集合中。找到第一个不在集合中的整数后，将其转换回二进制格式，并确保其长度为n（在前面填充0以达到长度n），然后返回这个二进制字符串。
时间复杂度: O(2^n)
空间复杂度: O(n)
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
n = len(nums) # 获取数组长度，即二进制字符串的长度
nums = set(map(lambda x: int(x, 2), nums)) # 将二进制字符串转换为整数并存入集合
for i in range(1 << n): # 生成从0到2^n - 1的所有整数
if i not in nums: # 检查当前整数是否不在集合中
ans = bin(i)[2:] # 将整数转换为二进制字符串
if len(ans) < n: # 如果字符串长度小于n，则在前面补充0
ans = '0' * (n - len(ans)) + ans
return ans # 返回结果
将二进制字符串转换为整数主要有两个优势：一是整数的比较和查找操作通常比字符串操作更快，这可以简化包含性（membership）检查的复杂度；二是处理整数范围的循环通常比操作字符串更直观且易于控制，尤其是在生成连续整数序列时。此外，使用整数还可以利用位操作，这在处理二进制数据时可能更高效。
如果n的值非常大，生成所有可能的二进制数将导致指数级增长的计算量，这可能导致性能问题。一种更有效的方法是使用Cantor对角线法或数学归纳法来直接构造一个不存在于输入集合中的二进制字符串。例如，可以通过检查每个位置上的字符，如果大多数二进制字符串在某位置是'0'，则在该位置选择'1'，否则选择'0'。这样构造的字符串有很大可能是新的二进制字符串。
在Python中，可以使用字符串的`zfill()`方法来简洁地实现在前面补0的需求。例如，`bin(i)[2:].zfill(n)`会自动将生成的二进制字符串前面补足0直到总长度达到n，这样可以更简洁地替代手动计算和添加0的过程。
使用随机或其他非线性方法来寻找缺失的二进制字符串是一个可行的策略，特别是在大数据集中可能更快地找到缺失项。优点在于可能快速找到缺失的字符串，特别是当缺失的字符串较少时。缺点是可能需要更多的迭代来保证找到一个确实缺失的字符串，且难以保证在最坏情况下的性能。此外，随机方法的结果不可预测，且重现性差，这在某些需要确定性结果的应用场景中可能不合适。