資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究基於給定條件從陣列構造一個長度為 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 - 將“dpTable[i][0]”初始化為 true，因為和為零總是可能的。這裡，“I”是索引值。
步驟 5.3 - 將“dpTable[0][j]”初始化為 false，因為對於空陣列來說和是不可能的。
步驟 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”值的“或”運算。
步驟 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)，因為我們儲存位集值。
結論
在這裡，我們優化了第二種方法，它在空間和時間複雜度方面都優於第一種方法。但是，如果您不瞭解位集，則第二種方法對於初學者來說可能難以理解。
104 次檢視
