Leetcode每日一题练习 ------ 1980. 找出不同的二进制字符串

开发调优
,
1

从Leetcode 每日一题练习继续讨论：

1980. 找出不同的二进制字符串
1980. Find Unique Binary String

题解

本题考虑字符串仅包含0和1，且字符串长度最大为16，因此可以直接将字符串中的0和1当作二进制位来处理，每个字符串都对应一个二进制串从而可以计算出该串对应的整数，将这些整数保存起来，再从该长度对应的二进制数的整数范围内找到一个不包含在这些整数中的整数转化为字符串形式的二进制串即可得到结果，一种简单的方法是直接从0开始递增遍历，只要碰到的数字不包含在之前的二进制串对应的整数中即为有效数字，因为之前的二进制串对应的整数最多16个，因此最差遍历16次一定可以得到结果。

代码


class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        unordered_set<int> s;
        for (string& num : nums) {
            int val = 0;
            for (char c : num) {
                val = (val << 1) | (c - '0');
            }
            s.insert(val);
        }

        for (int i = 0; ; ++i) {
            if (s.find(i) == s.end()) {
                string res = "";
                int temp = i;
                for (int j = 0; j < n; ++j) {
                    res = (char)((temp & 1) + '0') + res;
                    temp >>= 1;
                }
                return res;
            }
        }
    }
};
2 个赞
2

来了，刷题佬

2 个赞
3

来了，刷题佬

1 个赞
4

一看到二进制就想异或，想了一下感觉不对。
直接把所有数字上下叠放，想象一个串能跟任何串都保持不同，那就至少需要这俩串有一个地方不同就OK。

那就遍历已知数组，挨个位置与对应串不同，到最后一定能得到一个串能跟所有的串都不一样。而且题目给的限制太死了，

  • n == nums.length
  • 1 <= n <= 16
  • nums[i].length == n
  • nums[i] is either '0' or '1'.
  • All the strings of nums are unique.

如果串的个数大于串的长度其实就没法用了。这个恰好可以。