数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使所有字符串相等的最小移动次数的Java程序
在本文中，我们将学习如何解决一个问题，在这个问题中，我们得到一个包含字符串的数组，我们需要通过旋转它们来使所有字符串相等。这可以通过对字符串执行左旋转来完成。我们需要计算执行此操作所需的最小操作数。如果无法使字符串相等，则输出应为-1。
问题陈述
我们得到了一个包含n个字符串的数组。所有字符串都是彼此的排列。我们需要计算通过对字符串进行左旋转来使所有字符串相等所需的最小操作总数。
输入1
array[] = { "abcd", "abcd", "dabc", "bcda" }
输出1
4
输入2
array = {‘pq’, ‘pq’, ‘pq’}
输出2
0
不同的方法
基于队列的旋转比较方法
在这种方法中，我们将遍历字符串数组。我们将选择一个字符串，并通过旋转它们使所有字符串等于该特定字符串。此外，我们计算每个字符串的操作次数并取最小操作次数。
使用基于队列的旋转比较方法的步骤
以下是使用基于队列的旋转比较方法的步骤：
- 将“output”初始化为最大值，并遍历数组，使用“curr_operations”跟踪使字符串匹配所需的旋转次数。
- 使用嵌套循环遍历数组并执行isRotation() 函数，将array[p]和array[q]传递给该函数以计算所需的旋转次数。
- 在isRotation()函数中，检查字符串长度是否不相等（返回-1）或相等（返回0）。使用队列旋转字符并进行比较，直到找到匹配项。
- 如果isRotation() 函数返回-1，则返回-1。否则，将索引值添加到“curr_operations”。
- 使用Math.min()更新“output”，使其为output和curr_operations之间较小的值，并返回最终的output值。
示例
以下是使用基于队列的旋转比较方法的示例：
import java.util.*;
public class Main {
// function to find total number of operations to get alpha string from alpha2
public static int isRotation(String alpha, String alpha2) {
// base case
if (alpha.length() != alpha2.length())
return -1;
if (alpha.equals(alpha2))
return 0;
Queue<Character> alpha2Queue = new LinkedList<>();
// push all characters of alpha2 to queue
for (int i = 0; i < alpha2.length(); i++) {
alpha2Queue.add(alpha2.charAt(i));
}
// Push all characters of alpha to queue
Queue<Character> alpha1Queue = new LinkedList<>();
for (int i = 0; i < alpha.length(); i++) {
alpha1Queue.add(alpha.charAt(i));
}
int k = 0;
while (k < alpha.length()) {
k++;
char ch = alpha1Queue.peek();
alpha1Queue.remove(); // deque
alpha1Queue.add(ch); // enque
// queue matching
if (alpha1Queue.equals(alpha2Queue))
return k;
}
return -1;
}
static int minOperations(String array[], int len) {
int output = Integer.MAX_VALUE; // to store minimum operations
for (int p = 0; p < len; p++) {
// to store operations for the current iteration
int curr_operations = 0;
// total number of rotations required to make all strings of the array equal to
// str[i]
String temp = "";
for (int q = 0; q < len; q++) {
int index = isRotation(array[p], array[q]);
// return -1, if array[q] is not a rotation of array[p]
if (index == -1)
return -1;
// update curr_operations
curr_operations += index;
}
// get minimum operations
output = Math.min(curr_operations, output);
}
return output;
}
// Driver code
public static void main(String args[]) {
String array[] = { "abcd", "abcd", "dabc", "bcda" };
int len = array.length;
System.out.println(
"The minimum operations required to make all strings of the array equal is "
+ minOperations(array, len));
}
}
输出
The minimum operations required to make all strings of the array equal is 4
时间复杂度- O(N*N*K)，其中O(N*N)用于遍历数组，O(K)用于遍历字符串。
空间复杂度- O(K)，因为我们使用队列来存储字符串字符。
字符串连接和子串搜索方法
在这种方法中，我们将使用“+”运算符合并字符串。之后，我们将使用index() 方法在合并后的字符串中查找目标字符串的索引。
使用字符串连接和子串搜索方法的步骤
以下是使用字符串连接和子串搜索方法的步骤：
- 将“output”变量初始化为最大值，并开始遍历数组。
- 将“curr_operations”初始化为零，并使用另一个嵌套循环遍历数组。
- 在temp字符串中，存储array[q] + array[q]的值。
- 使用indexOf() 方法查找array[p]在“temp”字符串中的索引。
- 如果索引等于temp字符串的长度，则返回-1。
- 将索引值添加到“curr_operations”。
- 将output和curr_operations中的最小值存储到output中。
- 返回output。
示例
以下是使用字符串连接和子串搜索方法的示例：
import java.util.*;
public class Main {
static int minOperations(String array[], int len) {
// to store minimum operations
int output = Integer.MAX_VALUE;
for (int p = 0; p < len; p++) {
// to store operations for the current iteration
int curr_operations = 0;
// total number of rotations required to make all strings of the array equal to
// str[i]
String temp = "";
for (int q = 0; q < len; q++) {
// Concatenating string to itself to check whether it is a rotation of arr[i]
temp = array[q] + array[q];
// find index of array[p] in temp
int index = temp.indexOf(array[p]);
// return -1, if array[q] is not a rotation of array[p]
if (index == array[p].length())
return -1;
// update curr_operations
curr_operations += index;
}
// get minimum operations
output = Math.min(curr_operations, output);
}
return output;
}
public static void main(String args[]) {
String array[] = { "abcd", "abcd", "dabc", "bcda" };
int len = array.length;
System.out.println(
"The minimum operations required to make all strings of the array equal is " + minOperations(array, len));
}
}
输出
The minimum operations required to make all strings of the array equal is 4
时间复杂度- O(N*N*K)，因为我们在两个嵌套循环中使用了indexOf()方法。
空间复杂度- O(1)，因为我们没有使用额外的空间。
第二种方法比第一种方法更节省空间。此外，第二种方法的代码比第一种方法更易读。程序员也可以使用其他方法来使旋转字符串相同以解决问题。
更新于：2024年11月14日
浏览量：128
广告