找到给定大小的二进制字符串数组中不存在的任意排列

2023年 8月 29日 100.5k 0

找到给定大小的二进制字符串数组中不存在的任意排列

在这个问题中,我们需要从数组中找到长度为N的所有缺失的二进制字符串。我们可以通过找到长度为N的二进制字符串的所有排列,并检查哪些排列在数组中不存在来解决这个问题。在这里,我们将看到迭代和递归的方法来解决这个问题。

问题陈述 - 我们已经给出了一个包含不同长度的二进制字符串的数组arr[],长度为N。我们需要从数组中找出所有长度为N的缺失二进制字符串。

示例例子

输入 – arr = {"111", "001", "100", "110"}, N = 3

输出 – [000, 010, 011, 101]

Explanation – 有8个长度为3的二进制字符串,因为2的3次方等于8。所以,它打印出长度为3的缺失的4个二进制字符串。

输入 – str = {‘00’, ‘10’, ‘11’}, N = 2

Output – [‘01’]

Explanation – ‘01’在数组中缺失,因此会在输出中打印出来。

方法一

在这里,我们将使用迭代的方法来找到长度为N的所有可能的二进制字符串。之后,我们将检查该字符串是否存在于数组中。如果不存在,我们将打印该字符串。

算法

  • 定义集合并使用insert()方法将数组中的所有字符串添加到集合中。

  • 用2N初始化total变量,其中2N是长度为N的字符串的总数

  • 定义变量 'cnt' 并将其初始化为零,以存储缺失组合的总数。

  • 使用循环来使'总'迭代次数,以找到所有长度为N的二进制字符串。

  • 在循环中,使用空字符串初始化“num”字符串变量。

  • 使用嵌套循环进行总共N次迭代,并从最后一次迭代开始,创建长度为N的字符串。

  • 使用find()方法来检查集合是否包含当前字符串。如果是,则将‘cnt’的值增加1。

  • 如果字符串不在映射中,则打印它以显示在输出中

  • 如果“cnt”的值等于总数,则表示数组中存在所有长度为N的字符串,并打印“-1”。

Example

#include
using namespace std;
// function to print missing combinations of a binary string of length N in an array
void printMissingCombinations(vector &arr, int N) {
unordered_set set;
// insert all the strings in the set
for (string temp : arr) {
set.insert(temp);
}
// get total combinations for the string of length N
int total = (int)pow(2, N);
// To store combinations that are present in an array
int cnt = 0;
// find all the combinations
for (int p = 0; p = 0; q--) {
// If the qth bit is set, append '1'; append '0'.
if (p & (1

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论