数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学通过交换相邻字符串中的字符，使所有字符串都成为回文串
在这个问题中，我们将通过交换相邻字符串的字符，使给定数组中的所有字符串都成为回文串。
为了解决这个问题，我们将尝试使所有字符串在 p 索引和 str_len - p - 1 索引处的字符相同，只有当 p 索引和 (str_len - p - 1) 索引处的字符总数相同才有可能。
问题陈述 - 我们得到一个包含多个相同长度（等于 N）字符串的数组 arr。我们需要计算使数组中所有字符串都成为回文串所需的最小操作次数。我们可以在一次操作中交换任意两个相邻字符串的第 p 个字符。如果不可能使所有字符串都成为回文串，则打印 -1。
示例
输入
arr = {"57", "65", "76"};
输出
2
解释
我们需要交换 '13' 和 '21' 的第二个字符。所以，字符串将变成 {“55”, “67”, “76”}
接下来，交换第二个和第三个字符串的第一个字符。所以，最终的字符串将是 {'55', '77', '66'}。
所有最终字符串都是回文串。
输入
arr = {"aba", "ppp", "sss"}
输出
0
解释 - 由于所有字符串都是回文串，因此我们需要执行 0 次操作。
输入
arr = {"nnn", "pqr", "rqt"}
输出
-1
解释 - 通过交换相邻字符不可能使所有字符串都成为回文串。
方法 1
为了使任何字符串成为回文串，该字符串在 p 索引和 (str_len - p - 1) 索引处应该具有相同的字符。
这里，我们只能交换相邻字符串中相同索引处的字符。因此，我们可以取每个字符串的第 p 个字符并构成一个列表。同样，我们可以取字符串中 (str_len - p - 1) 索引处的字符并构成一个列表。
之后，我们可以交换第二个列表的相邻字符，以使两个列表相同。如果我们无法使任何列表相同，我们就无法使所有字符串都成为回文串。
例如，输入数组为 {"57", "65", "76"}。
因此，列表将是 p = 0，而 str_len - p - 1 = 1 索引等于 {5, 6, 7} 和 {7, 5, 6}。
在这里，我们可以交换第二个列表的字符以使列表等于第一个列表。
通过这种方式，我们需要计算从 0 到 len/2 的所有列表所需的移动次数，并将它们加起来以获得最终输出。
算法
步骤 1 - 将 'cnt' 变量初始化为 0 以存储最终结果。
步骤 2 - 从第 0 个索引到 len/2 索引遍历字符串。
步骤 3 - 在 temp1 列表中，获取所有第 p 个索引的字符，在 temp2 字符串中，通过执行 getColumnChars() 函数获取所有 (str_len - p - 1) 索引的字符。
步骤 3.1 - 在 getColumnChars() 函数中，初始化 'chars' 列表。
步骤 3.2 - 遍历数组的所有字符串，访问从参数作为参数传递的索引处的字符，并将其推送到 'chars' 列表中。
步骤 3.3 - 返回 chars 列表。
步骤 4 - 如果 temp1 和 temp2 列表相同，则我们不需要对当前列表执行任何操作。
步骤 5 - 现在，执行 isSwapPossible() 函数以检查是否可以通过交换字符来使两个列表相同。
步骤 5.1 - 在 isSwapPossible() 函数中，定义 'freq' 映射以存储列表字符的频率。
步骤 5.2 - 遍历 temp1 列表，并为 freq 映射中的 'ch' 键的值加 1。
步骤 5.3 - 遍历 temp2 列表，并为 freq 映射中的 'ch' 键的值减 1。
步骤 5.4 - 遍历映射，如果任何键的值不为零，则返回 false，因为两个列表不包含相同的字符。
步骤 5.5 - 返回 true。
步骤 6 - 如果 isSwapPossible() 函数返回 false，则将 cnt 更新为 -1，并中断循环。
步骤 7 - 否则，执行 countSwaps() 函数来计算通过交换相邻字符使两个列表相同所需的移动次数，并将它的返回值添加到 'cnt' 变量中。
步骤 7.1 - 在 countSwaps() 函数中，将 'sps' 初始化为 0，并开始遍历第一个列表。
步骤 7.2 - 如果两个列表中 p 索引处的字符不同，则执行以下步骤。否则，移动到下一个索引。
步骤 7.3 - 如果 p 是最后一个索引，则交换 p - 1 和 p 索引处的字符。否则，交换 p 和 p + 1 索引处的字符。
步骤 7.4 - 将 'sps' 加 1，并将 p 重新初始化为 0。
步骤 7.5 - 返回 'sps' 值。
步骤 8 - 在主函数中返回 cnt 值。
示例
以下是各种编程语言中此操作的实现：
#include <stdio.h>
#include <string.h>
// Function to get character from the ind index of all strings
void getColumnChars(char arr[][100], int rows, int ind, char chars[]) {
for (int i = 0; i < rows; i++) {
chars[i] = arr[i][ind];
}
}
// Function to check if it's possible to swap and make both lists the same
int isSwapPossible(char temp1[], char temp2[], int rows) {
int freq[256] = {0};
// Store frequency of characters of temp1
for (int i = 0; i < rows; i++) {
freq[temp1[i]]++;
}
// Subtract frequency of characters of temp2
for (int i = 0; i < rows; i++) {
freq[temp2[i]]--;
}
for (int i = 0; i < 256; i++) {
// When characters are not the same in both rows, return 0.
if (freq[i] != 0) {
return 0;
}
}
return 1;
}
// Function to count swaps required to make both lists the same
int countSwaps(char temp1[], char temp2[], int rows) {
int sps = 0;
int p = 0;
while (p != rows) {
if (temp1[p] != temp2[p]) {
if (p == rows - 1) {
// For the last character
char temp = temp2[p - 1];
temp2[p - 1] = temp2[p];
temp2[p] = temp;
} else {
// For other characters
char temp = temp2[p];
temp2[p] = temp2[p + 1];
temp2[p + 1] = temp;
}
// Increment number of swaps
sps += 1;
p = 0;
} else {
p += 1;
}
}
return sps;
}
int numberOfSwaps(char arr[][100], int rows, int cols) {
int cnt = 0;
int str_len = cols;
for (int p = 0; p < str_len / 2; p++) {
char temp1[100];
char temp2[100];
getColumnChars(arr, rows, p, temp1);
getColumnChars(arr, rows, str_len - p - 1, temp2);
// When each string contains the same character at p and str_len - p - 1 index
if (memcmp(temp1, temp2, rows) == 0) {
continue;
}
// Check whether possible to make temp1 and temp2 equal by swapping characters
if (!isSwapPossible(temp1, temp2, rows)) {
cnt = -1;
break;
} else {
cnt += countSwaps(temp1, temp2, rows);
}
}
return cnt;
}
int main() {
char arr[][100] = {"57", "65", "76"};
int rows = 3;
int cols = 2;
int result = numberOfSwaps(arr, rows, cols);
printf("The minimum number of swaps required to make all strings palindromic is %d\n", result);
return 0;
}
输出
The minimum number of swaps required to make all strings palindromic is 2
#include <bits/stdc++.h>
using namespace std;
// Get character from the ind index of all strings
vector<char> getColumnChars(vector<string> arr, int ind) {
vector<char> chars;
for (auto it : arr) {
chars.push_back(it[ind]);
}
return chars;
}
bool isSwapPossible(vector<char> temp1, vector<char> temp2) {
map<char, int> freq;
// Store frequency of characters of temp1
for (auto ch : temp1)
freq[ch]++;
// Subtract frequency of characters of temp2
for (auto ch : temp2)
freq[ch]--;
for (auto ch : freq) {
// When characters are not the same in both rows, return 0.
if (ch.second != 0)
return 0;
}
return 1;
}
int countSwaps(vector<char> temp1, vector<char> temp2) {
int sps = 0;
int p = 0;
while (p != temp1.size()) {
if (temp1[p] != temp2[p]) {
if (p == temp1.size() - 1) {
// For the last character
swap(temp2[p - 1], temp2[p]);
} else {
// For other characters
swap(temp2[p], temp2[p + 1]);
}
// Increment number of swaps
sps += 1;
p = 0;
}
else
p += 1;
}
return sps;
}
int numberOfSwaps(vector<string> arr) {
int cnt = 0;
int str_len = arr[0].size();
for (int p = 0; p < str_len / 2; p++) {
vector<char> temp1 = getColumnChars(arr, p);
vector<char> temp2 = getColumnChars(arr, str_len - p - 1);
// When each string contains the same character at p and str_len - p - 1 index
if (temp1 == temp2) {
continue;
}
// Check whether possible to make temp1 and temp2 equal by swapping characters
if (!isSwapPossible(temp1, temp2)) {
cnt = -1;
break;
} else {
cnt += countSwaps(temp1, temp2);
}
}
return cnt;
}
int main() {
vector<string> arr{"57", "65", "76"};
cout << "The minimum number of swaps required to make all strings palindromic is " << numberOfSwaps(arr) << endl;
}
输出
The minimum number of swaps required to make all strings palindromic is 2
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Main {
// Function to get character from the ind index of all strings
static char[] getColumnChars(String[] arr, int ind) {
char[] chars = new char[arr.length];
for (int i = 0; i < arr.length; i++) {
chars[i] = arr[i].charAt(ind);
}
return chars;
}
// Function to check if it's possible to swap and make both lists the same
static boolean isSwapPossible(char[] temp1, char[] temp2) {
Map<Character, Integer> freq = new HashMap<>();
// Store frequency of characters of temp1
for (char ch : temp1) {
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
// Subtract frequency of characters of temp2
for (char ch : temp2) {
freq.put(ch, freq.getOrDefault(ch, 0) - 1);
}
for (int value : freq.values()) {
// When characters are not the same in both rows, return false.
if (value != 0) {
return false;
}
}
return true;
}
// Function to count swaps required to make both lists the same
static int countSwaps(char[] temp1, char[] temp2) {
int sps = 0;
int p = 0;
while (p != temp1.length) {
if (temp1[p] != temp2[p]) {
if (p == temp1.length - 1) {
// For the last character
char temp = temp2[p - 1];
temp2[p - 1] = temp2[p];
temp2[p] = temp;
} else {
// For other characters
char temp = temp2[p];
temp2[p] = temp2[p + 1];
temp2[p + 1] = temp;
}
// Increment number of swaps
sps += 1;
p = 0;
} else {
p += 1;
}
}
return sps;
}
static int numberOfSwaps(String[] arr) {
int cnt = 0;
int str_len = arr[0].length();
for (int p = 0; p < str_len / 2; p++) {
char[] temp1 = getColumnChars(arr, p);
char[] temp2 = getColumnChars(arr, str_len - p - 1);
// When each string contains the same character at p and str_len - p - 1 index
if (Arrays.equals(temp1, temp2)) {
continue;
}
// Check whether possible to make temp1 and temp2 equal by swapping characters
if (!isSwapPossible(temp1, temp2)) {
cnt = -1;
break;
} else {
cnt += countSwaps(temp1, temp2);
}
}
return cnt;
}
public static void main(String[] args) {
String[] arr = {"57", "65", "76"};
int result = numberOfSwaps(arr);
System.out.println("The minimum number of swaps required to make all strings palindromic is " + result);
}
}
输出
The minimum number of swaps required to make all strings palindromic is 2
# Function to get character from the ind index of all strings
def get_column_chars(arr, ind):
chars = []
for s in arr:
chars.append(s[ind])
return chars
# Function to check if it's possible to swap and make both lists the same
def is_swap_possible(temp1, temp2):
freq = {}
# Store frequency of characters of temp1
for ch in temp1:
freq[ch] = freq.get(ch, 0) + 1
# Subtract frequency of characters of temp2
for ch in temp2:
freq[ch] = freq.get(ch, 0) - 1
# When characters are not the same in both rows, return false.
for value in freq.values():
if value != 0:
return False
return True
# Function to count swaps required to make both lists the same
def count_swaps(temp1, temp2):
sps = 0
p = 0
while p != len(temp1):
if temp1[p] != temp2[p]:
if p == len(temp1) - 1:
temp2[p - 1], temp2[p] = temp2[p], temp2[p - 1]
else:
temp2[p], temp2[p + 1] = temp2[p + 1], temp2[p]
sps += 1
p = 0
else:
p += 1
return sps
def number_of_swaps(arr):
cnt = 0
str_len = len(arr[0])
for p in range(str_len // 2):
temp1 = get_column_chars(arr, p)
# When each string contains the same character at p and str_len - p - 1 index
temp2 = get_column_chars(arr, str_len - p - 1)
if temp1 == temp2:
continue
if not is_swap_possible(temp1, temp2):
cnt = -1
break
else:
cnt += count_swaps(temp1, temp2)
return cnt
if __name__ == "__main__":
arr = ["57", "65", "76"]
result = number_of_swaps(arr)
print(f"The minimum number of swaps required to make all strings palindromic is {result}")
输出
The minimum number of swaps required to make all strings palindromic is 2
时间复杂度 - O(M*N*N)，其中 O(M) 用于遍历数组，O(N*N) 用于使所有字符串都成为回文串。
空间复杂度 - O(N) 用于在映射中存储字符频率。
我们学习了如何计算使数组中所有字符串都成为回文串所需的交换次数。逻辑部分是准备 p 和 str_len - p - 1 索引的字符列表，并使列表相同。
519 次浏览
