[LeetCode] 1980. Find Unique Binary String

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 }

 

LeetCode 题目总结

[LeetCode] 1980. Find Unique Binary String

上一篇:初识Ildasm.exe——IL反编译的实用工具


下一篇:node