資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
