資料結構
網路
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 次瀏覽
