資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究生成具有相同數量的 01 和 10 子序列的二進位制字串
在這個問題中，我們將找到給定長度的二進位制字串，該字串具有相同數量的“01”和“10”子序列。
解決該問題的樸素方法是生成給定長度的所有二進位制字串，並使用動態規劃技術檢查它是否包含相同數量的“10”和“01”子序列。
另一種有效的方法是根據給定長度是奇數還是偶數來準備二進位制字串。
問題陳述 - 我們給定一個大於 2 的正整數“len”。任務是找到長度為“len”的二進位制字串，該字串包含相同數量的“10”和“01”子序列。此外，字串應至少包含一個“1”和“0”。
示例
輸入
len = 4;
輸出
1001
解釋 - 字串 1001 包含兩個 10 和 01 子序列。另一個答案可以是 0110。
輸入
len = 5;
輸出
11011
解釋 - 子字串 11011 包含兩個 10 和 01 子序列。我們也可以在答案中列印 00100 字串。
輸入
len = 3;
輸出
010
解釋 - 答案可以是 010 和 101。
方法 1
在這種方法中，我們將使用遞迴函式生成給定長度的所有二進位制字串。此外，我們將使用表格動態規劃來檢查生成的字串是否包含相同數量的 10 和 01 子序列。
演算法
步驟 1 - 在 binStrUtil() 函式中，如果 temp 字串的長度等於“len”，則執行 totalSubSeqs() 函式以計算給定字串中“10”和“01”子序列的數量。
步驟 2.1 - 在 totalSubSeqs() 函式中，將“cnt”初始化為 0，並將維度為 str_len + 1 x subseq_len + 1 的“matrix”初始化為 0。
步驟 2.2 - 使用兩個巢狀迴圈遍歷矩陣。
步驟 2.3 - 如果 q 為 0，則將 matrix[p][q] 更新為 1，因為空子序列始終存在。
步驟 2.4 - 如果 p 為 0，則將 matrix[p][q] 更新為 0；長度為 0 的字串不存在子序列。
步驟 2.3 - 在其他情況下，如果 p−1 和 q − 1 索引處的字元相同，則將 matrix[p][q] 更新為 matrix[p − 1][q− 1] + matrix[p − 1][q]，其中 matrix[p − 1][q − 1] 透過考慮當前字元來計算子序列，而 matrix[p−1][q] 在不考慮當前字元的情況下計算子序列。
步驟 2.4 - 否則，將 matrix[p][q] 更新為 matrix[p−1][q]，因為如果它們不相同，我們不需要考慮當前字元。
步驟 2.5 - 從函式返回 matrix[strLen][sub_len] 值。
步驟 3 - 如果字串中“10”和“01”子序列相同，並且至少存在一個“1”和“0”，則將“answer”更新為“temp”字串。
步驟 4 - 接下來，將“0”附加到 temp，並使用 binaryUtil() 函式進行遞迴呼叫。還從字串中刪除最後一個字元。
步驟 5 - 將“1”附加到“temp”字串並進行遞迴呼叫。還從字串中刪除最後一個字元。
示例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
string answer = "";
int totalSubSeqs(const string &temp, const string &sub) {
int cnt = 0;
int sub_len = sub.length();
int strLen = temp.length();
int matrix[strLen + 1][sub_len + 1] = {0};
// Fill the matrix
for (int p = 0; p <= strLen; p++) {
for (int q = 0; q <= sub_len; q++) {
// Base cases
if (q == 0) {
matrix[p][q] = 1;
} else if (p == 0) {
// For strings with length 0.
matrix[p][q] = 0;
} else {
// When characters are the same
if (temp[p - 1] == sub[q - 1]) {
matrix[p][q] = matrix[p - 1][q - 1] + matrix[p - 1][q];
} else {
matrix[p][q] = matrix[p - 1][q];
}
}
}
}
cnt = matrix[strLen][sub_len];
return cnt;
}
void binStrUtil(string &temp, int len) {
if (temp.length() == len) {
// New binary string found
// If cnt of 10 and 01 subsequences are the same, choose it as the answer
if (totalSubSeqs(temp, "10") == totalSubSeqs(temp, "01")) {
if (count(temp.begin(), temp.end(), '1') > 0 && count(temp.begin(), temp.end(), '0') > 0)
answer = temp;
}
return;
}
// Insert 0 and backtrack
temp += '0';
binStrUtil(temp, len);
temp.pop_back();
// Insert 1 at the current index and backtrack
temp += '1';
binStrUtil(temp, len);
temp.pop_back();
}
int main() {
int len = 4;
string temp;
binStrUtil(temp, len);
cout << "The binary string of the given length and following the given condition is: " << answer << endl;
return 0;
}
輸出
The binary string of the given length and following the given condition is: 1001
時間複雜度 - O(N*2N)，其中 O(N) 用於查詢字串中 10 和 01 子序列的總數，而 O(2N) 用於查詢所有二進位制字串。
空間複雜度 - 用於 matrix[] 陣列和儲存二進位制字串的 O(N)。
方法 2
對於二進位制字串的偶數長度，如果我們將“1”放在 len/2 和 len/2 − 1 索引處，並將“0”放在其他索引處，我們可以得到具有相等 01 和 10 子序列的二進位制字串。
對於二進位制字串的奇數長度，如果我們將“1”放在 len/2 索引處，並將“0”放在其他索引處，我們可以得到給定長度的所需二進位制字串。
演算法
步驟 1 - 初始化“temp”字串和“middle”為“len/2”。
步驟 2 - 如果長度為偶數，請執行以下步驟。
步驟 2.1 - 進行等於給定“len”的迭代。如果當前索引等於中間或中間 – 1，則將“1”附加到 temp 字串。否則，將“0”附加到“temp”字串。
步驟 3 - 如果給定長度為奇數，請執行以下步驟。
步驟 3.1 - 進行等於給定“len”的迭代。如果當前索引等於中間，則將“1”附加到“temp”字串。否則，將“0”附加到“temp”字串。
步驟 4 - 返回“temp”字串。
示例
#include <iostream>
using namespace std;
string getBinStr(int len) {
string temp = "";
// Get middle of the length
int middle = len / 2;
// For even length
if (len % 2 == 0) {
for (int p = 0; p < len; p++) {
// Place two 1's at the middle
if (p == middle || p == middle - 1) {
temp += "1";
} else {
// Place 0's at the remaining places
temp += "0";
}
}
// Return the final binary string
return temp;
}
// For odd length
else {
for (int p = 0; p < len; p++) {
// Insert '1' at middle index
if (p == middle) {
temp += "1";
} else {
// Insert '0' at other indexes
temp += "0";
}
}
// Return the final binary string
return temp;
}
}
int main() {
int len = 5;
cout << "The binary string of the given length and following the given condition is " << getBinStr(len) << endl;
return 0;
}
輸出
The binary string of the given length and following the given condition is 00100
時間複雜度 - O(len) 用於生成給定長度的二進位制字串。
空間複雜度 - O(len) 用於儲存二進位制字串。
第二種方法基於觀察，它比第一種方法效率高得多。在第二種方法中，我們也可以在中間索引處列印“0”，在其他索引處列印“1”。
276 次檢視
