数据结构
网络
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 次查看
