leetcode 2026-03-08 每日一练 - 找出不同的二进制字符串

题目描述

LeetCode 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，可以把它看作区间 [0, 2^n-1] 内的一个整数。
  • nums 里一共有 n 个不同字符串，只占了该区间里很少一部分值。
  • 只要找到一个不在集合里的整数，再转回二进制字符串即可。

算法步骤

  1. 把 nums 中每个二进制字符串转换成十进制整数。
  2. 用哈希表 has 记录出现过的整数。
  3. 从 0 开始找最小的未出现整数 ans。
  4. 将 ans 还原成长度为 n 的二进制字符串（不足补前导 0）。

这个思路和“最小缺失值”很像，代码实现简单直接。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func findDifferentBinaryString(nums []string) string {
    n := len(nums)
    has := make(map[int]bool, n)
    for _, s := range nums {
        num := 0
        for _, c := range s {
            num = num*2 + int(c-'0')
        }
        has[num] = true
    }

    ans := 0
    for has[ans] {
        ans++
    }

    res := make([]byte, n)
    for i := n-1; i >= 0; i-- {
        res[i] = byte(ans%2) + '0'
        ans = ans/2
    }
    return string(res)
}

核心细节

  1. 字符串转整数：按二进制累乘，num = num*2 + bit。
  2. 哈希去重：map[int]bool 查询是否出现过是 O(1) 平均复杂度。
  3. 结果补位：从末位往前填，保证结果长度固定为 n。
  4. 正确性关键：因为 nums 只有 n 个元素，不可能占满 [0, 2^n-1]（当 n>=1 时 2^n > n），所以一定存在缺失值。

复杂度分析

  • 设 n = len(nums)，每个字符串长度也是 n。
  • 时间复杂度：O(n^2)
    • 转换阶段：n 个字符串，每个长度 n
    • 查找缺失值：最坏会扫到 n
    • 回填结果：O(n)
  • 空间复杂度：O(n)（哈希表与结果数组）

示例分析

以 nums = ["01", "10"] 为例：

  1. 转换：
    • "01" -> 1
    • "10" -> 2
    • has = {1, 2}
  2. 找最小缺失值：
    • ans = 0 时不在 has 中，停止
  3. 还原长度为 2 的二进制：
    • 0 -> "00"

最终返回 "00"（同样合法）。

总结

这题本质是把“二进制字符串判重”转成“整数判重”。

如果后续想继续优化写法，也可以尝试“对角线构造法”（康托尔思想），但当前实现已经足够清晰且可通过。