数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究反转字符串所需的最少相邻交换次数
给定一个字符串 str，我们只能交换相邻字符来使字符串反转。我们必须找到仅通过交换相邻字符使字符串反转所需的最小移动次数。我们将实现两种方法来找到所需的解决方案，并附带代码的解释和实现。
示例
Input1: string str1 = “shkej”
Output: 10
解释
首先，我们将最后一个字符移动到第一个位置，这需要 4 次交换，然后字符串将变为“jshke”。然后我们将 'e' 移动到第二个位置，这需要 3 次交换。类似地，对于 'k'，我们需要 2 次交换，对于 'h' 仅需要 1 次交换，最终答案是 10。
Input2: string str1 = “abace”
Output: 6
解释
首先，我们将交换第 2 个索引处的字符以将其移动到最后一个索引，这将花费 2 次交换，字符串将变为“abcea”。然后我们将交换 'b' 和 'e'，这将花费 2 次交换，字符串将变为“aceba”。然后再进行 2 次交换以获得最终的反转字符串，总共 6 次交换。
朴素方法
我们已经看到了上面的例子，现在让我们转向实现正确代码所需的步骤。
首先，我们将创建一个函数，该函数将给定的字符串作为参数，并返回所需的最小步数作为返回值。
在函数中，我们将创建一个字符串的副本，然后将其反转以与原始字符串进行比较。
我们将创建三个变量，前两个用于遍历字符串，最后一个用于存储所需的步数。
使用 while 循环，我们将遍历给定的字符串，并继续跳过当前索引值与反转字符串相同的迭代次数。
然后，我们将使用 while 循环交换相邻字符，直到 'j' 达到 'i'，并在每次交换时增加计数。
最后，我们将返回计数的值，并在主函数中打印它。
示例
#include <bits/stdc++.h>
using namespace std;
// function to get the minimum number of swaps
int minSwaps(string str){
string temp = str;
reverse(temp.begin(), temp.end()); // reversing the string
int i = 0, j = 0;
int ans = 0;
int len = str.size();
while (i <len) {
j = i;
// find the character that is equal to the current element
while (str[j] != temp[i]) {
j++;
}
// iterating util the current i is equal to j
while (i < j) {
char tempc = str[j];
str[j] = str[j - 1];
str[j - 1] = tempc;
j--;
ans++;
}
i++;
}
return ans;
}
int main(){
string str = "efabc"; // given string
// calling the function to find the minimum number of steps required
cout<<"The minimum number of steps required to reverse the given string by swapping the adjacent characters is "<<minSwaps(str)<<endl;
return 0;
}
输出
The minimum number of steps required to reverse the given string by swapping the adjacent characters is 10
时间和空间复杂度
上面代码的时间复杂度为 O(N^2)，其中 N 是给定字符串的长度。我们使用嵌套的 while 循环，这使得迭代次数为 N 的因子。
上面代码的空间复杂度为 O(N)，因为我们创建了一个额外的字符串来存储给定字符串的反转。
注意 - 这里可以实现另一种方法，但它使用了非常高级的数据结构。该方法背后的概念是，我们可以从最后一个字符开始，并检查直到第一个字符相遇。然后，从理论上讲，我们可以将该字符移动到最后一个位置，并将该位置标记为已实现，并将该值存储在高级数据结构中。
然后，对于每个字符，我们将找到从后面出现的相同字符（未标记），然后将计数增加其后面的总元素数减去已标记元素数。
结论
在本教程中，我们实现了查找仅通过交换相邻字符反转给定字符串所需的最小步数的代码。我们使用了嵌套的 while 循环并反转了给定字符串的副本以找到解决方案。上面代码的时间复杂度为 O(N^2)，其中 N 是字符串的大小，空间复杂度为 O(N)。
440 次浏览
