資料結構
網路
關係資料庫管理系統 (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
廣告