C++ 根据给定条件从数组中构建一个长度为K的二进制字符串

在本教程中，我们需要构建一个长度为K的二进制字符串，使得如果使用数组元素存在一个子集和等于I，那么在第i个索引处应该包含’1’。我们将学习两种方法来解决这个问题。在第一种方法中，我们将使用动态规划的方法来检查是否存在等于索引’I’的子集和。在第二种方法中，我们将使用位集来使用数组元素找到所有可能的和。

问题陈述 −我们有一个包含N个整数的数组。同时，我们有一个表示二进制字符串长度的整数M。我们需要创建一个长度为M的二进制字符串，使其满足以下条件。

• 如果我们可以从数组中找到一个子集，其和等于索引’I’，则在索引’I’处的字符为1；否则为0。

• 索引I从1开始。

示例

Input –  arr = [1, 2] M = 4

Output – 1110

解释

• 和为1的子集是{1}。

• 和为2的子集是{2}。

• 和为3的子集是{1, 2}。

• 我们找不到和为4的子集，所以我们在第4个索引处放置了0。

Input –  arr = [1, 3, 1] M = 9

Output – 111110000

解释

我们可以创建所有可能的组合来得到1到5之间的和。因此，前5个字符是1，后4个字符是0。

Input –  arr = [2, 6, 3] M = 6

Output – 011011

解释

等于1和4的总和在数组元素中是不可能的，所以我们在第一个和第四个索引处放置0。

方法1

在这个方法中，我们将使用动态规划来检查是否可以使用数组元素构造等于索引’I’的总和。我们将为每个索引检查它并在一个二进制字符串中附加1或0。

步骤

• 第 1 步： - 创建大小为 N 的向量，并使用整数值初始化。同时，使用字符串类型定义’bin’变量，并将其初始化为空字符串。

• 第 2 步： - 使用for循环进行总共 M 次迭代，等于字符串长度。

• 第 3 步： - 在for循环中，通过将数组、N 和索引值作为参数传递，调用isSubsetSum()函数。

• 第 4 步： - 如果isSubsetSum()函数返回true，则将’1’附加到’bin’中。否则，将’0’附加到’bin’中。

• 第 5 步： - 定义isSubsetSum()函数以检查是否可以使用数组元素得到总和。

• 第 5.1 步： - 定义一个名为dpTable的二维向量。

• 第 5.2 步： - 使用true初始化’dpTable[i][0]’，因为总和为零总是可能的。这里，’I’是索引值。

• 第 5.3 步： - 使用false初始化’dpTable[0][j]’，因为空数组无法得到总和。

• 第 5.4 步： - 现在，使用两个嵌套循环。第一个循环从1到N进行迭代，另一个循环从1到总和进行迭代。

• 第 5.5 步： - 在for循环中，如果当前元素的值大于总和，则忽略它。

• 第 5.6 步： - 否则，包括或排除元素以得到总和。

• 第 5.7 步： - 返回包含结果的’dpTable[N][sum]’。

示例

#include <iostream>
#include <vector>
using namespace std;
// Function to check if subset-sum is possible
bool isSubsetSum(vector<int> &arr, int N, int sum){
   vector<vector<bool>> dpTable(N + 1, vector<bool>(sum + 1, false));

   // Base cases
   for (int i = 0; i <= N; i++)

      // If the sum is zero, then the answer is true
      dpTable[i][0] = true;

   // for an empty array, the sum is not possible
   for (int j = 1; j <= sum; j++)
      dpTable[0][j] = false;

   // Fill the dp table
   for (int i = 1; i <= N; i++){
      for (int j = 1; j <= sum; j++){

         // if the current element is greater than the sum, then we can't include it
         if (arr[i - 1] > j)
            dpTable[i][j] = dpTable[i - 1][j];

         // else we can either include it or exclude it to get the sum
         else
            dpTable[i][j] = dpTable[i - 1][j] || dpTable[i - 1][j - arr[i - 1]];
      }
   }

   // The last cell of the dp table contains the result
   return dpTable[N][sum];
}
int main(){

   // Given M
   int M = 9;

   // Creating the vector
   vector<int> arr = {1, 3, 1};

   // getting the size of the vector
   int N = arr.size();

   // Initializing the string
   string bin = "";

   // Making k iteration to construct the string of length k
   for (int i = 1; i <= M; i++){

      // if the subset sum is possible, then add 1 to the string, else add 0
      if (isSubsetSum(arr, N, i)){
         bin += "1";
      }
      else{
         bin += "0";
      }
   }

   // print the result.
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   cout << bin;
   return 0;
}

输出

The constructed binary string of length 9 according to the given conditions is 111110000

时间复杂度 – O(N^3)，因为isSubsetSum()的时间复杂度是O(N^2)，而我们从驱动代码中调用它N次。

空间复杂度 – O(N^2)，因为我们在isSubsetSum()函数中使用了一个二维向量。

方法2：使用位集

在这种方法中，我们将使用位集来通过组合数组的不同元素找到所有可能的和值。这里，位集表示它创建了一个二进制字符串。在结果位集中，它的每一位表示是否可能存在等于特定索引的和，这是我们需要在这里找到的。

步骤

• 步骤1 - 定义数组和M。还要定义createBinaryString()函数。
• 步骤2 - 接下来，定义所需长度的位集，它创建了一个二进制字符串。
• 步骤3 - 将bit[0]初始化为1，因为总和为0总是可能存在的。
• 步骤4 - 使用for循环遍历数组元素
• 步骤5 - 首先，对’bit’进行左移操作与数组元素进行操作。然后，对结果值和’bit’值进行’or’操作。
• 步骤6 - 打印从索引1到M的位集值。

示例

#include <bits/stdc++.h>
using namespace std;
// function to construct the binary string
void createBinaryString(int array[], int N, int M){
   bitset<100003> bit;

   // Initialize with 1
   bit[0] = 1;

   // iterate over all the integers
   for (int i = 0; i < N; i++){
      // perform left shift by array[i], and OR with the previous value.
      bit = bit | bit << array[i];
   }

   // Print the binary string
   cout << "The constructed binary string of length " << M << " according to the given conditions is ";
   for (int i = 1; i <= M; i++){
      cout << bit[i];
   }
}
int main(){

   // array of integers
   int array[] = {1, 4, 2};
   int N = sizeof(array) / sizeof(array[0]);

   // value of M, size of the string
   int M = 8;
   createBinaryString(array, N, M);
}

输出

The constructed binary string of length 8 according to the given conditions is 11111110

时间复杂度：O(N)，因为我们使用了单个for循环。

空间复杂度：O(N)，因为我们存储了位集的值。

结论

在这里，我们优化了第二种方法，从空间和时间复杂度的角度来看，它比第一种方法更好。然而，如果您不了解位集的知识，第二种方法可能对初学者来说较难理解。