透過遞增子字串的所有字符，使字串回文所需的最小移動次數

在電腦科學和程式設計領域中，發現解決問題的有效演算法非常重要。一個有趣的問題是透過增加子字串中的所有字元來識別將字串轉換為回文所需的最小操作次數。本文探討了兩種使用C 程式語言處理這個問題的方法。

文法

在深入探討這些方法之前，讓我們先定義一下我們將要使用的函數的語法 −

int minMovesToMakePalindrome(string str);

演算法

• 我們的目標是在將字串轉換為回文時盡量減少移動次數-這個問題是我們的演算法透過以下關鍵階段來解決的−

• 首先，從字串的兩側分別建立兩個指標變量，左邊指標則從字串的開頭開始，右指標則從字串的結尾開始。

• Continue our process as long as configuration limits allow i.e. once either pointer surpasses the other halt −

• #每當字元值相同時，繼續將兩個指標靠攏。每當字元值不同時，在進行任何進一步操作之前，將右側的字元值增加（根據它們的差異）。這種增加與'a'和'c'之間的差異成比例，因此如果str[right]等於'c'且str[left]等於'a'，我們將str[right]增加2（因為'a '-'c'=2）。相應地更新移動計數。

• 一旦左邊大於右邊，字串就會變成回文。

方法一：暴力破解

在這個方法中，我們將考慮所有可能的子字串，並計算每個子字串所需的最小移動次數。最後，我們將傳回所有計算出的移動次數中的最小值。

Example

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int length = str.length();

   for (int i = 0; i < length / 2; i++) {
      moves += abs(str[i] - str[length - i - 1]);
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

輸出

Minimum moves to make the string palindrome: 6

Explanation

的翻譯為：

解釋

已建立一個名為 minMovesToMakePalindrome 的函數，它將輸入字串 str 轉換為所需的最小移動次數的回文。我們透過一些逐步說明來解釋它的工作原理：

我們將moves變數初始化為0，它負責追蹤所需的總移動次數。 - 由於length變數記錄了輸入字串str的長度，我們的下一步是使用for迴圈迭代一半的字串，以便對稱位置不重疊。 - 最後，在此循環內部，abs(str[i] - str[length - i - 1])計算兩端字元之間的絕對差異。

計算出的差異代表了使這些位置上的字元相等所需的移動次數。我們將這個差異添加到移動計數中。

在迭代所有必要的位置後，我們將所需的總最小移動次數儲存在moves變數中。我們傳回這個值。

在主函數中，我們用值"abcde"初始化了一個字串str。然後，我們呼叫minMovesToMakePalindrome函數，將str當作參數傳遞進去。傳回的最小移動次數儲存在minMoves變數中。最後，我們將結果列印到控制台。

方法二：最優的雙指標方法

這種方法利用兩個指標同時從字串的兩端遍歷。考慮到效率，我們採用了一種將字串轉換為回文的技術，該技術涉及從輸入的兩端逐漸增加和匹配字元。這種方法最大程度地減少了不必要的操作，並且在不影響準確性或功能性的情況下，允許更快的轉換。

Example

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int left = 0;
   int right = str.length() - 1;

   while (left <= right) {
      moves += abs(str[right] - str[left]);
      left++;
      right--;
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

輸出

Minimum moves to make the string palindrome: 6

Explanation

的翻譯為：

解釋

下面程式碼範例的目標是利用最優的雙指標方法來確定將給定字串轉換為回文所需的最小移動次數。

為了實現這一點，我們創建了一個名為minMovesToMakePalindrome的函數。該函數接受一個字串參數並傳回所需的移動總數。首先，我們將用於計算移動次數的變數設為0，並初始化左右指標：左指標從輸入字串的開頭（索引0）開始，右指標從結尾（索引str.length() - 1）開始。

我們的while迴圈在left大於等於right之前迭代，以覆寫字串中的所有元素。在每次迭代中，我們透過使用abs(str[right] - str[left])來找到left和right位置的字元之間的差異，這表示需要多少次移動才能使這兩個字元相同。我們將這個差異值加到我們的運行計數器中，以獲得總移動次數。

當我們向輸入字串的中心移動時，增加左指標並減少右指標。一旦左指標和右指標之間沒有重疊，我們就將字串轉換為回文。

At this point we return our count of total moves stored in 'moves'. In main() identical steps are followed as previously where we declare a new input string 'abcde' call minMovesToMakePal 看到value that's assigned to new variable 'minMoves' before printing this value onto the console.

結論

在以下文字中，提出了兩種替代方案，旨在提供洞察力和潛在答案，以解決透過字元操作在子字串中計算將給定字串轉換為回文所需的移動次數的障礙。一種方法稱為暴力法，包含所有可能的子字串，而另一種方法稱為最優雙指標方法，大大減少了所需的移動次數。編碼人員可以輕鬆應用這些機制來解決類似的障礙，並以此提升他們的解決方案。

以上是透過遞增子字串的所有字符，使字串回文所需的最小移動次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！