資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學統計最多隻有兩個相鄰不同對的 N 個大小的字串的形成方式
在這個問題中，我們將計算大小為 N 的二進位制字串的數量，其中最多包含 2 對相鄰的不同字元。這意味著字串最多應包含 2 個 '01' 或 '10' 對。
第一種方法是生成所有二進位制字串，如果任何二進位制字串包含小於或等於 2 對不同的字元，則將其計數包含在結果中。
對於最佳解決方案，我們可以計算包含 0、1 和 2 個相鄰不同對的二進位制字串的數量，並將它們相加。
問題陳述 - 我們給定一個正整數 N，表示二進位制字串的大小。我們需要計算大小為 N 的二進位制字串的數量，這些字串最多包含 2 對字元值不同的相鄰字元對。
示例
輸入
N = 3
輸出
8
解釋 - 所有長度為 3 的字串都最多包含 2 對相鄰的不同字元。
這些字串是 000、001、010、100、011、110、101、111
輸入
N = 4
輸出
14
解釋 - 有效的二進位制字串是 0000、0001、0010、0011、0100、0101、0110、0111、1000、1001、1010、1011、1100、1101、1110、1111。我們可以觀察到所有字串最多包含 2 對相鄰的不同字元。
輸入
N = 5
輸出
22
解釋 - 我們可以生成長度為 5 的 2^5 = 32 個二進位制字串，但根據問題中給出的條件，只有 22 個是有效的。
有效的二進位制字串是 00000、00001、00010、00011、00100、00101、00110、00111、01000、01001、01010、01011、01100、01101、01110、01111、10000、10001、10010、10011、10100、10101、10110、10111、11000、11001、11010、11011、11100、11101、11110、11111。
方法一
在這種方法中，我們將使用遞迴函式來生成所有二進位制字串。對於每個二進位制字串，我們檢查它包含多少個相鄰的不同對。如果少於 3 個，我們將結果計數值加 1。
演算法
步驟 1 - 用 N 個 0 初始化 'current' 字串。
步驟 2 - 還將 'cnt' 初始化為 0 以儲存有效二進位制字串的計數，並將其作為引用引數傳遞到 getBinaryStr() 函式中。
步驟 3 - 在 getBinaryStr() 函式中，如果索引等於字串長度，我們將獲得二進位制字串，並按照以下步驟計算相鄰不同對的數量。
步驟 3.1 - 將 'diff' 變數初始化為 0 以儲存相鄰不同對的數量。
步驟 3.2 - 開始遍歷字串，如果第 i 個和第 (i + 1) 個索引處的字元不同，則將 'diff' 值加 1。
步驟 3.3 - 遍歷字串後，如果 'diff' 值小於或等於 2，則將 'cnt' 值加 1，並執行 'return' 語句。
步驟 3.4 - 在當前索引處插入 '0'，並透過將索引值加 1 來進行遞迴函式呼叫。
步驟 3.5 - 在當前索引處插入 '1'，並透過將索引值加 1 來進行遞迴函式呼叫。
步驟 4 - 在 countStrings() 函式中，列印 'cnt' 值。
示例
#include <bits/stdc++.h>
using namespace std;
void getBinaryStrs(int len, string ¤t, int index, int &cnt) {
// Base case
if (index == len) {
// Checking the number of different adjacent characters
int diff = 0;
for (int i = 0; i < len - 1; i++) {
if (current[i] != current[i + 1]) {
diff++;
}
}
if (diff <= 2) {
cnt++;
}
return;
}
// Put '0' at the current index and make a recursive call
current[index] = '0';
getBinaryStrs(len, current, index + 1, cnt);
// Put '1' at the current index and make a recursive call
current[index] = '1';
getBinaryStrs(len, current, index + 1, cnt);
}
void countStrings(int len) {
string current(len, '0'); // String initialized with all '0's
int cnt = 0;
getBinaryStrs(len, current, 0, cnt);
cout << "The number of ways to create a string of size N according to the given conditions is " << cnt;
}
int main() {
int N = 3;
countStrings(N);
return 0;
}
輸出
The number of ways to create a string of size N according to the given conditions is 8
時間複雜度 - O(N*2N)，用於生成所有二進位制字串並遍歷每個字串。
空間複雜度 - O(N)，用於儲存長度為 N 的二進位制字串。
方法二
在這種方法中，我們將計算長度為 N 的二進位制字串的數量，這些字串最多包含 0、1 和 2 個相鄰的不同對。我們將使用一些數學公式來獲得輸出。
包含不同字元的 0 個相鄰對
我們可以構造僅包含兩個不包含不同相鄰值的二進位制字串。第一個包含所有零，第二個包含所有 1。
包含不同字元的 1 個相鄰對
對於包含不同字元的 1 個相鄰對，我們只能在結果字串中有一個 01 或 10 對。因此，對於長度為 N 的字串，我們可以有 2*(N - 1) 個選項。
這裡，2 代表 10 和 01 對，(N - 1) 代表字串中 1 和 0 的不同數量。對於 N = 4，我們可以構造 0111、0011、0001 共 3 (4 - 1) 個包含 '01' 對的字串。此外，我們還可以構造另外 3 個僅包含一次 '10' 對的字串。
包含不同字元的 2 個相鄰對
對於包含不同字元的 2 個相鄰對的字串，我們可以有 010 或 101 模式。
對於 '101' 模式，我們總是需要開頭和結尾各有一個 1。因此，我們可以有 (N - 2) 種方法將中間的零放入字串中。例如，從 2 到 N - 1、2 到 N - 2、2 到 N - 3，依此類推。
這樣，我們可以從第 3 個索引開始放置 0，並且有 (N - 3) 種方法將零放在中間。
因此，將零放入 101 模式的總方法數為 (N - 2) + (N - 3) + (N - 4) + … + 2 + 1，等於 (N - 2) * (N - 1) /2。在這裡，我們使用了 1 + 2 + 3 + … + (a - 1) + a 級數的 (a) * (a + 1)/2 公式。
我們還需要計算包含 010 模式的字串。因此，所需二進位制字串的總數為 2*(N - 2)*(N - 1)/2，等於 (N - 1)*(N - 2)。
我們最終獲得所有有效子字串的公式如下所示。
2 + 2 * (len - 1) + (len - 2) * (len - 1)
示例
在這個例子中，我們使用上述公式來計算二進位制字串，該字串最多具有 2 個具有不同值的相鄰對。
#include <bits/stdc++.h>
using namespace std;
long long countStrings(long long len){
// Sum results of all cases
return 2 + 2 * (len - 1) + (len - 2) * (len - 1);
}
int main(){
int N = 3;
cout << "The number of ways to create a string of size N according to the given conditions is " << countStrings(N);
return 0;
}
輸出
The number of ways to create a string of size N according to the given conditions is 8
時間複雜度 - O(1)，因為我們使用數學公式來獲得答案。
空間複雜度 - O(1)，因為我們不使用任何額外的空間。
第二種方法是透過執行字串長度的乘法和求和來查詢二進位制字串計數的最佳方法之一。我們根據問題陳述中的條件觀察到了模式，並制定了一個公式。
120 次檢視
