資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最小化將兩個給定字串轉換為彼此的排列所需的給定操作次數
在本文中，我們將討論如何最小化將兩個給定字串轉換為彼此的排列所需的給定操作次數。我們將採用循序漸進的方法並提供程式碼實現。我們還將包含一個示例測試用例，以幫助理解問題和解決方案。
問題陳述
給定兩個字串 s1 和 s2，我們需要找到使 s1 和 s2 成為彼此排列所需的最小操作次數。我們可以執行兩個操作：交換 s1 的任意兩個字元，或交換 s2 的任意兩個字元。
方法和實現
為了解決這個問題，我們需要計算不在兩個字串中都存在的字元數量，即兩個字串中字元頻率的差異。使兩個字串成為彼此排列所需的最小交換次數等於此計數的一半，因為我們可以在任一字串中交換字元以使它們相等。
首先，我們將使用兩個陣列計算兩個字串中字元的頻率。然後，我們將遍歷這兩個陣列並將字元頻率之間的絕對差新增到一個變數中。此變數將儲存不在兩個字串中都存在的字元的數量。
計算完計數後，我們將返回其一半作為使兩個字串成為彼此排列所需的最小交換次數。
示例
以下是上述方法的相關程式：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int countMinSwaps(char* s1, char* s2) {
int freq1[26] = {0}, freq2[26] = {0}, count = 0;
// Calculate the frequency of characters in the first string (s1)
for (int i = 0; s1[i] != '\0'; i++) {
freq1[s1[i] - 'a']++;
}
// Calculate the frequency of characters in the second string (s2)
for (int i = 0; s2[i] != '\0'; i++) {
freq2[s2[i] - 'a']++;
}
// Calculate the absolute difference in character frequencies between s1 and s2
for (int i = 0; i < 26; i++) {
count += abs(freq1[i] - freq2[i]);
}
return count / 2; // Divide by 2 since we are counting swaps (one swap will fix two characters)
}
int main() {
char s1[] = "hello";
char s2[] = "world";
int minSwaps = countMinSwaps(s1, s2);
printf("Minimum number of swaps required: %d\n", minSwaps);
return 0;
}
輸出
Minimum number of swaps required: 3
#include<bits/stdc++.h>
using namespace std;
int countMinSwaps(string s1, string s2) {
int freq1[26] = {0}, freq2[26] = {0}, count = 0;
for (char c : s1) {
freq1[c - 'a']++;
}
for (char c : s2) {
freq2[c - 'a']++;
}
for (int i = 0; i < 26; i++) {
count += abs(freq1[i] - freq2[i]);
}
return count / 2;
}
int main() {
string s1 = "hello";
string s2 = "world";
int minSwaps = countMinSwaps(s1, s2);
cout << "Minimum number of swaps required: " << minSwaps << endl;
return 0;
}
輸出
Minimum number of swaps required: 3
import java.util.Scanner;
public class Main {
public static int countMinSwaps(String s1, String s2) {
int[] freq1 = new int[26];
int[] freq2 = new int[26];
int count = 0;
// Calculate the frequency of characters in the first string (s1)
for (char c : s1.toCharArray()) {
freq1[c - 'a']++;
}
// Calculate the frequency of characters in the second string (s2)
for (char c : s2.toCharArray()) {
freq2[c - 'a']++;
}
// Calculate the absolute difference in character frequencies between s1 and s2
for (int i = 0; i < 26; i++) {
count += Math.abs(freq1[i] - freq2[i]);
}
return count / 2; // Divide by 2 since we are counting swaps (one swap will fix two characters)
}
public static void main(String[] args) {
String s1 = "hello";
String s2 = "world";
int minSwaps = countMinSwaps(s1, s2);
System.out.println("Minimum number of swaps required: " + minSwaps);
}
}
輸出
Minimum number of swaps required: 3
def count_min_swaps(s1, s2):
freq1 = [0] * 26
freq2 = [0] * 26
count = 0
# Calculate the frequency of characters in the first string (s1)
for c in s1:
freq1[ord(c) - ord('a')] += 1
# Calculate the frequency of characters in the second string (s2)
for c in s2:
freq2[ord(c) - ord('a')] += 1
# Calculate the absolute difference in character frequencies between s1 and s2
for i in range(26):
count += abs(freq1[i] - freq2[i])
return count // 2 # Divide by 2 since we are counting swaps (one swap will fix two characters)
def main():
s1 = "hello"
s2 = "world"
min_swaps = count_min_swaps(s1, s2)
print("Minimum number of swaps required:", min_swaps)
if __name__ == "__main__":
main()
輸出
Minimum number of swaps required: 3
示例測試用例
讓我們考慮此測試用例中的示例字串“hello”和“world”。
兩個字串的頻率陣列如下：
freq1 = {0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
freq2 = {0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}
我們可以看到，字元“l”在 s1 中的頻率為 2，但在 s2 中僅為 1，而字元“r”在 s2 中的頻率為 1，但在 s1 中不存在。因此，不在兩個字串中都存在的字元的數量為 3。
因此，使兩個字串成為彼此排列所需的最小交換次數為 1。我們可以將 s1 中的“l”與 s2 中的“r”交換以獲得字串“herlo”和“wolld”，它們是彼此的排列。
結論
在本文中，我們討論瞭如何最小化將兩個給定字串轉換為彼此的排列所需的給定操作次數。我們採用循序漸進的方法，並提供了 C++ 中的程式碼實現。我們還包含一個示例測試用例，以幫助理解問題和解決方案。此問題可以在 O(n) 時間複雜度和 O(1) 空間複雜度內解決。
更新於：2023-10-23
112 次檢視
廣告