資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究生成連續的 0 和 1 子字串所需的最小翻轉次數
連續字元序列，稱為 0 和 1 的子字串，可以透過以任何順序從原始字串中選擇零個或多個字元來建立，而無需跳過任何字元。
例如，字串“0101”。遵循此文字的子字串為：0，“”、1、“01”、“10”、“010”、“101”和“0101”。
空字串也是所有字串的子字串，因為它可以透過從原始字串中精確選擇 0 個字元來建立。
因此，在本例中，“”也是“0101”的子字串。
方法
使用動態規劃
使用貪心演算法
方法 1：使用動態規劃
動態規劃是一種有效的方法，可以確定生成連續的 0 和 1 子字串所需的最小翻轉次數。動態規劃方法將問題分解成更小的子問題，並自下而上構建解決方案。
我們必須確定獲得此類子字串所需的最小翻轉次數。
語法
min (k5):
l8 [0][0] = 0
if k5 [0] == '0'
else 1
l8 [0][1] = 0
if k5 [0] == '1'
else 1
l8[i][0] = l8[i-1][1] + (0 if k5[i] == '0' else 1)
l8[i][1] = l8[i-1][0] + (0 if k5[i] == '1' else 1)
// Returning the minimum required
return minimum among(l8[n-1][0], l8[n-1][1])
演算法
計算每個配對字串中生成連續的 0 和 1 子字串所需的翻轉次數的演算法 -
步驟 1 − 初始化兩個變數，flip_zero 和 flip_one 為 0。
步驟 2 − 通常建議仔細閱讀字串中的每個字元以確保重複。
如果當前字元與前一個字元不匹配，請檢視它是 '0' 還是 '1'。
如果當前字元是 '0'，則將 flip_zero 加 1。
如果當前字元是 '1'，則將 flip_one 加 1。
步驟 3 − 返回 flip_zero 和 flip_one 的最小值。
此演算法計算更改字串的 0 和 1 所需的翻轉次數。根據當前字元的值，每次遇到新字元時，flip_zero 或 flip_one 都會增加。翻轉零和一的最小值是最終結果。
示例 1
在此實現中，minFlips 函式迭代字串 s，計算相鄰字元不同的次數。此計數反映了生成連續的 0 和 1 子字串所需的翻轉頻率。此計數的最小值和包含與相鄰字元相同的字元的連續 0 或 1 子字串的數量表示無需翻轉的次數。
我們在示例主方法中使用字串“0011100”呼叫 minFlips 並列印結果，結果為 1。根據此結果，可以透過僅翻轉一次來生成輸入字串中的連續的 0 和 1 子字串。
#include <iostream>
#include <string>
#include <algorithm>
int minFlips (std::string s) {
int n = s.size();
int count = 0;
for (int i = 0; i < n - 1; i++) {
if (s[i]!= s[i+1]) {
count++;
}
}
return std::min(count, n - count - 1);
}
int main () {
std::string s = "0011100";
std::cout << "Minimum flips required: " << minFlips(s) << std::endl;
return 0;
}
輸出
Minimum flips required: 2
使用貪心演算法
為了獲得整體最優解，貪心演算法需要在每個階段做出區域性最優決策。確定生成連續的 0 和 1 子字串所需的最小翻轉次數是此技術的應用之一。
通常，問題陳述指的是具有交替的 0 和 1 子字串的二進位制字串。目標是確定將字串更改為所有 0 或所有 1 出現在另一側之前的模式所需的最小翻轉次數。
演算法
為了找到每個字串中生成連續的 0 和 1 子字串所需的最小翻轉次數，我們可以遵循以下演算法 -
步驟 1 − 我們需要設定兩個變數，它們將儲存初始值為 0。第一個變數 c1 表示為了生成序列 010101 而所需的翻轉次數。另一方面，第二個變數 c2 表示我們需要執行多少次翻轉才能建立序列 101010。
步驟 2 − 遍歷字串，對於每個字元，檢查它是否根據當前模式匹配預期字元。如果不是，則增加相應的 c 變數。
步驟 3 − 檢查當前字元後，根據當前模式翻轉預期字元。例如，如果當前模式是 010101... 並且當前字元是 1，則下一個預期字元將是 0。
步驟 4 − 如果生成相反模式所需的翻轉次數小於當前模式，則切換模式。
步驟 5 − 返回 c1 和 c2 的最小值。
步驟 6 − 此演算法採用 n（輸入字串的長度）作為輸入，並且具有 O(n) 的時間複雜度。
示例 2
在此示例中，minFlips 函式以二進位制字串 s 作為輸入，並輸出生成交替的 0 和 1 字串所需的最小翻轉次數。該函式透過計算生成每個字串所需的翻轉次數來生成兩個可能的交替字串，一個以 0 開頭，另一個以 1 開頭。然後，該函式返回這兩個數字中較小的一個。
在主函式中，我們使用二進位制字串“0101010101”呼叫 minFlips 並將結果列印到控制檯。輸出應為“所需的最小翻轉次數：0”，因為輸入字串已經是交替的 0 和 1 字串。由於輸入字串已經是交替的 0 和 1 字串，因此結果應該說“所需的最小翻轉次數：0”。
#include <iostream>
#include <string>
using namespace std;
int minFlips(string s) {
int n = s.length();
int flips1 = 0, flips2 = 0;
// Count flips required to generate string of alternating 0's and 1's
for (int i = 0; i < n; i++) {
if (i % 2 == 0 && s[i] != '0') {
flips1++;
} else if (i % 2 == 1 && s[i] != '1') {
flips1++;
}
if (i % 2 == 0 && s[i] != '1') {
flips2++;
} else if (i % 2 == 1 && s[i] != '0') {
flips2++;
}
}
// Return the minimum number of flips required
return min(flips1, flips2);
}
int main() {
string s = "0101010101";
int flips = minFlips(s);
cout << "Minimum flips required: " << flips << endl;
return 0;
}
輸出
Minimum flips required: 0
結論
確定生成連續的 0 和 1 子字串所需的最小翻轉次數的挑戰的解決方案取決於問題的限制和要求。執行此操作所需的最小翻轉次數取決於字串以及如何定義“連續”子字串。在解決問題時，通常可以採用多種方法。例如，動態規劃和貪婪演算法都是解決類似問題的可能解決方案。
具體來說，如果您需要找到問題的最佳解決方案，則動態規劃可能是您的最佳選擇。使用此技術，您可以建立一個數據庫，其中包含有關生成可行子字串直至特定點所需的翻轉次數的資訊。雖然此方法確實有其優點，但如果我們想找到此問題的最佳解決方案，則各種解決方案的缺點至關重要。
943 次檢視
