資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最小化需要更改的字元數，以使字串的左旋轉和右旋轉相同
在處理字串時，經常會遇到涉及旋轉的問題，這是一個透過將一定數量的字元移動到字串的另一端來重新排列字串中字元的過程。在本文中，我們將探討一個有趣的問題：如何最小化必須更改的字元數量，以使字串的左旋轉和右旋轉相同。我們將提供一個結構良好的 C++ 解決方案，幷包含一個示例來說明測試用例。
問題陳述
給定長度為 'n' 的字串 's'，我們需要找到需要更改的最小字元數，以便在執行相同位置的左旋轉和右旋轉後，兩個結果字串相同。
演算法
建立一個名為 minCharsToChange 的函式，該函式將字串 's' 作為引數。
將變數 'minChanges' 初始化為字串的長度。
使用迴圈遍歷字串，將索引 'i' 從 0 增加到 'n'。
在每次迭代中，執行以下步驟：
執行 'i' 個位置的左旋轉，並將結果儲存在新字串 'leftRotated' 中。
執行 'i' 個位置的右旋轉，並將結果儲存在新字串 'rightRotated' 中。
計算 'leftRotated' 和 'rightRotated' 之間不同字元的數量，並將結果儲存在變數 'diffCount' 中。
將 'minChanges' 更新為 'minChanges' 和 'diffCount' 之間的最小值。
返回 'minChanges' 作為結果。
C++ 實現
示例
#include <iostream>
#include <string>
#include <algorithm>
// Function to perform left rotation
std::string leftRotate(std::string s, int d) {
std::rotate(s.begin(), s.begin() + d, s.end());
return s;
}
// Function to perform right rotation
std::string rightRotate(std::string s, int d) {
std::rotate(s.begin(), s.begin() + s.size() - d, s.end());
return s;
}
// Function to minimize characters to be changed
int minCharsToChange(std::string s) {
int n = s.length();
int minChanges = n;
for (int i = 0; i < n; ++i) {
std::string leftRotated = leftRotate(s, i);
std::string rightRotated = rightRotate(s, i);
int diffCount = 0;
for (int j = 0; j < n; ++j) {
if (leftRotated[j] != rightRotated[j]) {
++diffCount;
}
}
minChanges = std::min(minChanges, diffCount);
}
return minChanges;
}
int main() {
std::string s = "abca";
int result = minCharsToChange(s);
std::cout << "Minimum characters to be changed: " << result << std::endl;
return 0;
}
輸出
Minimum characters to be changed: 0
測試用例示例
考慮以下字串：“abca”。可能的左旋轉和右旋轉及其各自不同的字元如下：
i = 0：左旋轉 = "abca"，右旋轉 = "abca"，不同字元 = 0
i = 1：左旋轉 = "bcaa"，右旋轉 = "caab"，不同字元 = 3
i = 2：左旋轉 = "caab"，右旋轉 = "abca"，不同字元 = 2
i = 3：左旋轉 = "abca"，右旋轉 = "bcaa"，不同字元 = 3
從上面的迭代中，我們可以看到不同字元的最小數量是 0，當 i = 0 時出現。在這種情況下，不需要任何更改即可使字串的左旋轉和右旋轉相同。
結論
在本文中，我們探討了最小化需要更改的字元數量以使字串的左旋轉和右旋轉相同的問題。我們提出了一種清晰有效的 C++ 實現，該實現利用簡單的迴圈遍歷字串，執行左旋轉和右旋轉，並比較結果字串以找到所需的最小更改數量。
透過理解此演算法，您可以應用類似的概念來解決計算機科學和程式設計中的其他字串操作和旋轉問題。
118 次瀏覽
