資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中使字串相等所需的最小交換次數
假設我們有兩個長度相等的字串 s1 和 s2，它們只包含字母“x”和“y”。我們的任務是使這兩個字串彼此相等。我們可以交換屬於不同字串的任意兩個字元，這意味著 - 交換 s1[i] 和 s2[j]。我們必須找到使 s1 和 s2 相等所需的最小交換次數，或者如果不可能這樣做，則返回 -1。因此，如果字串為 s1 =“xy”和 s2 =“yx”，則輸出將為 2。如果我們交換 s1[0] 和 s2[0]，則 s1 = "yy"，s2 = "xx"。然後交換 s1[0] 和 s2[1]，s1 = "xy"，s2 = "xy"。
為了解決這個問題，我們將遵循以下步驟：
- 將 x1、x2、y1 和 y2 設定為 0
- 對於 i 從 0 到 s1 的大小
- a := s1[i] 和 b := s2[i]
- 如果 a 與 b 不相同，則
- 如果 a = 'x'，則將 x1 增加 1，否則將 y1 增加 1
- 如果 b = 'x'，則將 x2 增加 1，否則將 y2 增加 1
- 如果 (x1 + x2) 為奇數或 (y1 + y2) 為奇數，則返回 -1
- 返回 x1/2 + y1/2 + (x1 模 2) * 2
示例（C++）
讓我們看看以下實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumSwap(string s1, string s2) {
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
for(int i = 0; i < s1.size(); i++){
char a = s1[i];
char b = s2[i];
if(a != b){
if(a == 'x')x1++;
else y1++;
if(b == 'x')x2++;
else y2++;
}
}
if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
return x1/2 + y1/2 + (x1 % 2) * 2;
}
};
main(){
Solution ob;
cout <<ob.minimumSwap("xy", "yx");
}輸入
"xy" "yx"
輸出
2
更新於：2020-04-30
445 次瀏覽
廣告