数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究JavaScript 程序，最小化字符更改次数以使字符串的左旋和右旋相同
在这个问题中，我们需要确定使字符串的左旋和右旋相同的最小成本。
以下是我们用来解决问题的观察结果。
对于长度为奇数的字符串，所有字符都应该相等，才能使左旋和右旋相同。
长度为偶数的字符串应该在偶数和奇数索引处具有相同的字符。
问题陈述 – 我们有一个大小为 N 的字符串，包含不同的字符。我们需要确定通过更改给定字符串的字符来使给定字符串的左旋和右旋相同的最小成本。更改字符串中任何字符的成本为 1。
注意 – 字符串的左旋将字符串向左移动 1 个位置，并将第一个字符放在字符串的末尾。
字符串的右旋将字符串向右移动 1 个位置，并将第一个字符放在字符串的开头。
示例
输入
str = ‘tut’
输出
‘1’
解释 – 由于字符串长度为奇数，我们需要使所有字符相同。因此，我们需要更改“u”以使其等于“t”。
输入
‘gggggggggggg’
输出
0
解释 – 由于字符串的所有字符都相同，因此我们不需要更改任何字符。
输入
str = "mpmntrmnfdmn";
输出
5
解释 – 由于字符串长度为偶数，我们需要使所有字符在偶数索引和奇数索引处相等。在偶数索引处，我们可以使所有字符等于“m”，在奇数索引处，我们可以使所有字符等于“n”。
方法 1
在这种方法中，我们将使奇数长度字符串中的所有字符相等，并使偶数长度字符串的偶数和奇数索引处的字符相等。
我们可以找到奇数长度字符串中频率最高的字符，并使所有字符都等于它。此外，我们可以找到偶数和奇数位置上频率最高的字符，并相应地更改偶数和奇数索引处的字符，以用于偶数长度字符串。
算法
步骤 1 – 使用字符串长度初始化“str_size”变量。
步骤 2 – 定义“minCost”变量以存储更改字符以使左旋和右旋相等的最小成本。
步骤 3 – 如果 str_size % 2 等于零，我们需要遵循以下步骤。
步骤 3.1 – 定义大小为 128 的 evenFreq 和 oddFreq 数组变量，并将所有数组元素初始化为零。
步骤 3.2 – 遍历字符串，并使用 charCodeAt() 方法获取字符的 ASCII 值。如果当前索引为偶数，则更新 evenFreq 数组中的字符频率。否则，更新 oddFreq 数组中的字符频率。
步骤 3.3 – 获取偶数索引和奇数索引处每个字符的频率后，我们需要找到频率最高的字符。因此，声明 maxiEven 和 maxiOdd 变量。
步骤 3.4 – 从数组中查找最大值，并将它们存储在 maxiEven 和 maxiOdd 变量中。
步骤 3.5 – 从字符串长度中减去 maxiEven 和 maxiOdd，并将其分配给 minCost 变量。
步骤 4 – 对于长度为奇数的字符串，我们应该遵循以下步骤。
步骤 4.1 – 定义 charFreq 数组以存储字符串所有字符的频率。
步骤 4.2 – 遍历字符串并在数组中更新字符的频率。
步骤 4.3 – 从数组中查找最大值。
步骤 4.4 – 从字符串长度中减去 maxFreq 并将其分配给 minCost。
步骤 5 – 返回 minCost 值。
示例
function findMinCharacters(str) {
var str_size = str.length;
// Base case if all characters are different in a given string
var minCost = str_size;
// For even size of strings
if (str_size % 2 === 0) {
// Defining array to store the frequency
var evenFreq = new Array(128).fill(0);
var oddFreq = new Array(128).fill(0);
// Traverse the string
for (var p = 0; p < str_size; p++) {
if (p % 2 === 0) {
// Update character frequency in the array based on the odd or even index
evenFreq[str[p].charCodeAt(0)]++;
} else {
oddFreq[str[p].charCodeAt(0)]++;
}
}
var maxiEven = 0;
var maxiOdd = 0;
for (var c = "a".charCodeAt(0); c <= "z".charCodeAt(0); c++) {
maxiEven = Math.max(maxiEven, evenFreq[c]);
maxiOdd = Math.max(maxiOdd, oddFreq[c]);
}
// Final answer
minCost = minCost - maxiEven - maxiOdd;
}
// For the odd length of string
else {
var charFreq = new Array(128).fill(0);
// store character frequency in the array
for (var p = 0; p < str_size; p++) {
charFreq[str[p].charCodeAt(0)]++;
}
// Finding the maximum frequency of any character
var maxFreq = 0;
for (var c = "a".charCodeAt(0); c <= "z".charCodeAt(0); c++) {
maxFreq = Math.max(maxFreq, charFreq[c]);
}
// Final answer
minCost = minCost - maxFreq;
}
// returning the answer
return minCost;
}
var str = "tut";
console.log(
"The minimum number of characters we should remove to get a left and right rotation of string same is - " +
findMinCharacters(str)
);
输出
The minimum number of characters we should remove to get a left and right rotation of string same is - 1
时间复杂度 – O(N)，因为我们遍历长度为 N 的字符串。
空间复杂度 – O(N)，因为我们使用常量空间。
从这个问题的解决方案中，我们可以了解到，并非每个问题都有特定的方法来解决。有时，我们需要观察问题的输入和输出，并根据这些输入和输出来解决问题。
74 次查看
