重新排列字串中的字符，使得任意兩個相鄰字符不相同，使用C++實現

我們給定了一個字串，假設為str，長度可以是任意值。任務是重新排列給定的字串，使得在結果字串中不會有相同的相鄰字元排在一起。

讓我們來看看各種輸入輸出場景：

輸入 − 字串str = "itinn"

輸出  − 重新排列字串中的字符，使得相鄰的兩個字符不相同，結果為：initn。

解釋 − 我們給定了一個字串類型的變量，假設為str。現在我們將重新排列輸入字串的字符，使得沒有兩個相同的字符出現在同一個位置，即將'nn'移動到不相鄰的位置。所以最終的結果是 字串將會是'initn'.

輸入 − 字串str = "abbaabbaa"

輸出 − 字串中字元重新排列，使得相鄰的字元不相同: ababababa

解釋 − 我們給定了一個字串類型的變量，假設為str。現在我們將重新排列輸入字串的字符，使得沒有兩個相同的字符出現在同一個位置，即移動'bb', 'aa', 'bb', 'aa'，因為它們是相同的並且相鄰。所以最終的字串將會是 ‘ababababa’。

下面程式中使用的方法如下

• 輸入字串類型的變量，假設為str，併計算字串的大小並將其儲存在一個名為length 的變數中。

• 檢查如果 length 為 0，則回傳。

• 將資料傳遞給函數 Rearrangement(str, length)。

• 在函數 Rearrangement(arr, length) 內部

  • 設定字串的大小為 (length 1)/2。

  • 宣告一個向量類型的變數 vec(26, 0)，它將儲存整數類型的數據，以及字串類型的指標 ptr(length, ‘ ‘)。也宣告一個臨時變數 temp，類型為整數，值為 0。

  • 開始迴圈 FOR 來迭代 str。在循環內部，設定 vec[it - ‘a’] 。

  • 建立一個字元類型的變數 ch，並將其設定為呼叫 maximum(vec) 函數的結果。

  • 宣告一個整數型別的變數 total，並將其設為 vec[ch - ‘a’]。

  • 檢查如果 total 大於 size，則回傳。

  • 開始循環 WHILE total，然後將 ptr[temp] 設為 ch，將 temp 設定為 temp 2，並將 total 減 1。

  • 將 vec[ch - 'a'] 設為 0。開始循環 FOR，從 i 到 0，直到 i 小於 26。在循環內部，開始while 循環，當vec[i] 大於0 時，將temp 設為(temp >= length) ? 1 : temp，將ptr[temp] 設定為'a' i，將temp 設定為temp 2，並將vec[i] 減1。

  • 返回ptr

• #在函數char maximum(const vector& vec) 內部

  • 宣告一個整數類型的變數high，並將其設為0，以及一個字元類型的變數c。

  • 開始迴圈 FOR，從 i 到 0，直到 i 小於 26。在循環內部，檢查如果 vec[i] 小於 high，則將 high 設為 vec[i]，將 c 設為 'a' i。

  • 傳回 c

• #列印結果。

範例

#include <bits/stdc++.h>
using namespace std;
char maximum(const vector<int>& vec){
   int high = 0;
   char c;
   for(int i = 0; i < 26; i++){
      if(vec[i] > high){
         high = vec[i];
         c = &#39;a&#39; + i;
      }
   }
   return c;
}
string Rearrangement(string str, int length){
   int size = (length + 1) / 2;
   vector<int> vec(26, 0);
   string ptr(length, &#39; &#39;);
   int temp = 0;
   for(auto it : str){
      vec[it - &#39;a&#39;]++;
   }
   char ch = maximum(vec);
   int total = vec[ch - &#39;a&#39;];
   if(total > size){
      return "";
   }
   while(total){
      ptr[temp] = ch;
      temp = temp + 2;
      total--;
   }
   vec[ch - &#39;a&#39;] = 0;
   for(int i = 0; i < 26; i++){
      while (vec[i] > 0){
         temp = (temp >= length) ? 1 : temp;
         ptr[temp] = &#39;a&#39; + i;
         temp = temp + 2;
         vec[i]--;
      }
   }
   return ptr;
}
int main(){
   string str = "itinn";
   int length = str.length();
   if(length == 0){
      cout<<"Please enter a valid string";
   }
   string count = Rearrangement(str, length);
   if(count == ""){
      cout<<"Please enter a valid string";
   }
   else{
      cout<<"Rearrangement of characters in a string such that no two adjacent are same is: "<<count;
   }
   return 0;
}

輸出

如果我們執行上述程式碼，將會產生以下輸出

Rearrangement of characters in a string such that no two adjacent are same is: initn

#

以上是重新排列字串中的字符，使得任意兩個相鄰字符不相同，使用C++實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！