資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Java程式：最小化字元更改次數，使字串的左旋轉和右旋轉相同
在這個問題中，我們需要更改給定字串中的最少字元，以使其左旋轉和右旋轉相同。在字串中，我們可以觀察到，只有當字串長度為奇數且所有字元都相同，或者字串長度為偶數且偶數和奇數索引處的字元相同，我們才能使字串的左旋轉和右旋轉相同。
例如，
abab – 字串的左旋轉和右旋轉分別是 baba 和 baba。
aaa – 字串的左旋轉和右旋轉分別是 aaa 和 aaa。
abc – 字串的左旋轉和右旋轉分別是 bca 和 cab。
aabb – 字串的左旋轉和右旋轉分別是 abba 和 baab。
問題陳述 – 我們給定一個包含字母字元的字串 str。字串的大小等於 N。我們需要更改最少的字元數量，以使字串的左旋轉和右旋轉相同。
示例
輸入
str = "tuto"
輸出
1
解釋 – 我們需要將 ‘u’ 更改為 ‘o’ 或將 ‘o’ 更改為 ‘u’，以使字串的左旋轉和右旋轉相同。
輸入
str = "abcde";
輸出
4
解釋 – 為了使左旋轉和右旋轉相同，我們需要使所有字元都相同，因為字串長度是奇數。
輸入
str = ‘mnmnmnmnmnmn’
輸出
0
解釋 – 字串的左旋轉和右旋轉已經相同。
方法 1
在這種方法中，我們將根據上面討論的觀察結果實現邏輯。如果字串長度為奇數，我們將計算使所有字元都相等的最小成本；如果字串長度為偶數，我們將計算使字串偶數和奇數索引處的字元都相等的最小成本。
演算法
步驟 1 – 將字串的長度儲存在 ‘len’ 變數中。此外，將 ‘min_chars’ 初始化為字串長度，因為我們假設最初字串的所有字元都不同。
步驟 2 – 如果字串長度為偶數，請執行以下步驟。
步驟 2.1 – 定義長度為 128 的 ‘evenPosFreq’ 和 ‘oddPosFreq’ 陣列，以儲存給定字串中每個字元的頻率。
步驟 2.2 – 開始遍歷字串，如果 ‘p’ 為偶數，則在 ‘evenPosFreq’ 陣列中索引等於字元的 ASCII 值的位置遞增 1。否則，在 ‘oddPosFreq’ 陣列中遞增 1。
步驟 2.3 – 現在，我們需要找到偶數和奇數位置上任何字元的最大頻率。
步驟 2.4 – 定義 ‘MaxFreqEven’ 和 ‘MaxFreqOdd’ 變數，並初始化為零。此外，開始遍歷頻率陣列，從兩個陣列中獲取最大值，並將其儲存在 ‘MaxFreqEven’ 和 ‘MaxFreqOdd’ 變數中。
步驟 2.5 – 在 min_chars 變數中，儲存從字串長度中減去 ‘MaxFreqEven’ 和 ‘MaxFreqOdd’ 的值後的結果值。
步驟 3 – 如果字串長度為奇數，請執行以下步驟。
步驟 3.1 – 定義 ‘allCharFreq’ 陣列以儲存每個字元的頻率。此外，透過遍歷字串將每個字元的頻率儲存到其中。
步驟 3.2 – 定義 maxChar 變數以儲存頻率最高的字元。遍歷陣列並在陣列中找到最大元素。
步驟 3.3 - 在 min_chars 變數中，儲存從字串長度中減去 maxChars 後的結果值。
步驟 4 – 返回 min_chars 變數的值。
示例
public class TP {
public static int findMinCharRemoval(String alpha) {
int len = alpha.length();
// Initially, let's say we need to remove all characters
int min_chars = len;
// For the odd length of the string
if (len % 2 == 0) {
// Defining array to store the frequency
int[] evenPosFreq = new int[128];
int[] oddPosFreq = new int[128];
// Traverse the string
for (int p = 0; p < len; p++) {
// Update character frequency in the array based on the odd or even index
if (p % 2 == 0) {
evenPosFreq[alpha.charAt(p)]++;
} else {
oddPosFreq[alpha.charAt(p)]++;
}
}
// to store max frequency of any character at even and odd positions
int MaxFreqEven = 0, MaxFreqOdd = 0;
// Find the maximum frequency
for (char c = 'a'; c <= 'z'; c++) {
MaxFreqEven = Math.max(MaxFreqEven, evenPosFreq[c]);
MaxFreqOdd = Math.max(MaxFreqOdd, oddPosFreq[c]);
}
// Final result
min_chars = min_chars - MaxFreqEven - MaxFreqOdd;
}
// For odd string
else {
// Get frequncy of all chars
int[] allCharFreq = new int[128];
for (int p = 0; p < len; p++) {
allCharFreq[alpha.charAt(p)]++;
}
// Finding the most occurring character
int maxChar = 0;
for (char c = 'a'; c <= 'z'; c++) {
maxChar = Math.max(maxChar, allCharFreq[c]);
}
// Final answer
min_chars = min_chars - maxChar;
}
// return final answer
return min_chars;
}
public static void main(String[] args) {
String str = "tuto";
System.out.print("The minimum numbers of character we should remove to get left and right rotation of string same is - "
+ findMinCharRemoval(str));
}
}
輸出
The minimum numbers of character we should remove to get left and right rotation of string same is - 1
時間複雜度 – O(N)，因為我們多次遍歷字串。
空間複雜度 – O(1)，因為我們使用常量空間來儲存字串字元的頻率。
我們學習瞭如何在 Java 中使字串的左旋轉和右旋轉相同。程式設計師還可以嘗試查詢給定字串的左旋轉和右旋轉，以進行更多練習。
81 次檢視
