数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告