資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究需要移除的最小字元數，使得給定字串僅包含一對交替出現的字元
需要移除的最小字元數，使得給定字串僅包含一對交替出現的字元，是計算機科學中一個常見問題，在涉及字串操作的應用中經常遇到。
在本教程中，我們將使用 C++ 程式語言解決此問題。我們將首先詳細解釋問題陳述，並討論其在各種現實世界應用中的重要性。
然後，我們將提供一個逐步解決此問題的演算法，並演示其在 C++ 中的實現。最後，我們將總結我們解決方案的時間和空間複雜度的一些見解，並討論潛在的改進領域。所以讓我們開始吧！
問題陳述
該程式的目標是找到需要從給定字串 'S' 中移除的最小字元數，以便將其轉換為一個新字串，其中僅存在兩個交替出現的字元。
示例 1
輸入
String S = "abccd"
輸出
3
說明：在從原始字串中消除所有 'c' 和 'd' 的例項後，我們得到結果字串 "ab"，其特徵在於 'a' 和 'b' 交替出現。
示例 2
輸入
String S = "adebbeeaebd"
輸出
7
說明：在消除所有 'b' 和 'e' 的例項後，我們得到字串 "adad"，其特徵在於 'a' 和 'd' 交替出現。
演算法
步驟 1. 定義一個名為 ‘findLength’ 的函式，它接收三個引數：一個字串 ‘s’ 以及兩個字元 ‘i’ 和 ‘j’。
步驟 2. 在 ‘findLength’ 函式內部
初始化一個名為 required 的變數為 i。
初始化一個名為 length 的變數為 0，以跟蹤字元數。
遍歷字串 ‘s’ 中的每個字元 ‘curr’。
如果當前字元 ‘curr’ 等於所需的字元 required
將 length 加 1。
更新 required 為另一個字元 (j)，如果 required 當前為 i，或者更新為 i 如果它當前為 j。這確保了字元交替出現。
返回最終的 length。
步驟 3. 定義一個名為 ‘minimumDeletions’ 的函式，它接收一個字串 ‘S’ 作為引數。
步驟 4. 在 ‘minimumDeletions’ 函式內部
初始化一個名為 len 的變數為 0，用於儲存找到的交替字元的最大長度。
獲取字串 ‘S’ 的長度並將其儲存在變數 ‘n’ 中。
使用變數 i 遍歷從 'a' 到 'z' 的所有小寫字母。
對於每個 i，使用變數 j 遍歷從 i + 1 到 'z' 的所有後續小寫字母。
呼叫 ‘findLength’ 函式，引數為 ‘S’、‘i’ 和 ‘j’，以獲取考慮 i 和 j 時交替字元的長度。
將 len 更新為 len 和獲得的新長度之間的最大值。
透過從輸入字串長度 n 中減去 len 來計算所需的最小刪除次數。
返回最小刪除次數。
步驟 5. 在 main 函式內部
建立一個字串 S 並將其初始化為 "abccd"。
呼叫 ‘minimumDeletions’ 函式，引數為 ‘S’，並將結果儲存在一個變數中。
使用 ‘std::cout’ 輸出結果。
注意：上述演算法假設輸入字串 S 僅包含小寫英文字母。如果輸入字串包含其他字元或大寫字母，程式可能無法按預期工作。
示例
使用 C++ 實現上述演算法
以下 C++ 程式確定需要從字串中刪除的最小字元數，以便獲得僅包含兩個交替字元的字串。
‘findLength’ 函式計算給定字串內交替子字串的長度，使用兩個字元作為交替標記。
‘minimumDeletions’ 函式遍歷所有可能的字元對 ('a' 到 'z')，並使用 ‘findLength’ 函式查詢最大交替子字串長度。
程式的 ‘main’ 函式將字串 ‘S’ 初始化為 "abccd" 並呼叫 ‘minimumDeletions’ 來計算結果。然後使用 ‘cout’ 列印結果。
整個程式有效地解決了查詢獲得僅包含兩個交替字元的字串所需的最小刪除次數的問題。
#include <iostream>
#include <string>
#include <algorithm>
int findLength(std::string s, char i, char j) {
char required = i;
int length = 0;
for (char curr : s) {
if (curr == required) {
length += 1;
required = (required == i) ? j : i;
}
}
return length;
}
int minimumDeletions(std::string S) {
int len = 0;
int n = S.length();
for (char i = 'a'; i <= 'z'; i++) {
for (char j = i + 1; j <= 'z'; j++) {
int newLen = findLength(S, i, j);
len = std::max(len, newLen);
}
}
return n - len;
}
int main() {
std::string S = "abccd";
std::cout << minimumDeletions(S) << std::endl;
return 0;
}
輸出
3
結論
總而言之，提供的 C++ 程式有效地解決了確定將給定字串轉換為僅包含一對交替字元的新字串所需的最小字元移除次數的問題。透過利用 findLength 函式識別交替子字串的長度以及 minimumDeletions 函式查詢最大交替子字串長度，該程式成功地計算出所需的結果。此解決方案能夠有效地處理需要最小刪除次數才能獲得具有所需交替字元模式的字串的情況。
146 次瀏覽
