Given an array of strings nums
containing n
unique binary strings each of length n
, return a binary string of length n
that does not appear in nums
. If there are multiple answers, you may return any of them.
Example 1:
Input: nums = ["01","10"] Output: "11" Explanation: "11" does not appear in nums. "00" would also be correct.
Example 2:
Input: nums = ["00","01"] Output: "11" Explanation: "11" does not appear in nums. "10" would also be correct.
Example 3:
Input: nums = ["111","011","001"] Output: "101" Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.
Constraints:
n == nums.length
1 <= n <= 16
nums[i].length == n
-
nums[i]
is either‘0‘
or‘1‘
.
找出不同的二进制字符串。
给你一个字符串数组 nums ,该数组由 n 个 互不相同 的二进制字符串组成,且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案,只需返回 任意一个 即可。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-unique-binary-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题我给出一个位运算的暴力解吧。美版讨论区有一个非常简洁的写法,面试的时候不容易想得到,这里我贴出来仅供参考。
题目说 nums 数组是由 n 个 互不相同 的二进制字符串组成,且他们长度相同,所以当我们知道这其中的字符串的长度 len 之后,我们就可以知道理论上 nums 数组里都有可能出现哪些字符串。首先我们用一个 hashset 去记录 input 数组中已经出现过的二进制字符串,之后我们用位运算去模拟所有可以出现在 nums 数组里的二进制数。模拟的过程中,如果发现哪个字符串不在 hashset 中,则表示他是一个缺失的字符串。
时间O(n)
空间O(1)
Java实现
1 class Solution { 2 public String findDifferentBinaryString(String[] nums) { 3 int len = nums[0].length(); 4 HashSet<String> set = new HashSet<>(); 5 for (String num : nums) { 6 set.add(num); 7 } 8 9 int count = (int) Math.pow(2, len); 10 for (int i = 0; i < count; i++) { 11 StringBuilder sb = new StringBuilder(); 12 int temp = i; 13 for (int j = 0; j < len; j++) { 14 if ((temp & 1) == 1) { 15 sb.append(‘1‘); 16 } else { 17 sb.append(‘0‘); 18 } 19 temp >>= 1; 20 } 21 if (!set.contains(sb.toString())) { 22 return sb.toString(); 23 } 24 } 25 return null; 26 } 27 }