数据结构
网络
关系数据库管理系统 (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 次浏览
