首頁 > 後端開發 > C++ > 在執行給定操作後,找到出現次數最多的字符

在執行給定操作後,找到出現次數最多的字符

WBOY
發布: 2023-08-27 09:49:06
轉載
918 人瀏覽過

在執行給定操作後,找到出現次數最多的字符

在本文中,我們將探討在執行一組給定的操作後尋找字串中出現最多的字元的概念。這個問題經常出現在程式設計挑戰和麵試中,掌握解決方案有助於增強你的字串操作和演算法技能。我們將解釋問題陳述,討論所使用的演算法,展示 C 實現,並提供測試用例範例來演示解決方案。

問題陳述

給定一個字串 s 和一組操作,在執行所有操作後找到最大出現的字元。每個運算由一對(i, j)組成,代表我們要交換字串中i和j位置的字元。

演算法

  • 建立一個頻率陣列來儲存字串中每個字元的出現次數。

  • 迭代操作,交換指定位置的字元。

  • 每次交換後更新頻率陣列。

  • 迭代頻率陣列以尋找出現次數最多的字元。

C 實作

範例

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

char maxOccurringChar(const std::string &s, const std::vector<std::pair<int, int>> &operations) {
   std::vector<int> frequency(26, 0);
   std::string modifiedString = s;
   
   // Initialize the frequency array with the original string's character occurrences
   for (char c : modifiedString) {
      frequency[c - 'a']++;
   }
   
   for (const auto &op : operations) {
      int i = op.first;
      int j = op.second;
   
      // Decrement the frequency of the characters being swapped
      frequency[modifiedString[i] - 'a']--;
      frequency[modifiedString[j] - 'a']--;
   
      // Perform the swap
      std::swap(modifiedString[i], modifiedString[j]);
   
      // Increment the frequency of the swapped characters
      frequency[modifiedString[i] - 'a']++;
      frequency[modifiedString[j] - 'a']++;
   }

   // Find the character with the maximum occurrence
   int maxFrequency = 0;
   char maxChar = 'a';
   for (int i = 0; i < 26; i++) {
      if (frequency[i] > maxFrequency) {
         maxFrequency = frequency[i];
         maxChar = 'a' + i;
      }
   }
   
   return maxChar;
}

int main() {
   std::string s = "aabcbdb";
   std::vector<std::pair<int, int>> operations = { {1, 4}, {2, 5} };
   
   char maxChar = maxOccurringChar(s, operations);
   std::cout << "The maximum occurring character after performing the operations is: " << maxChar << std::endl;
   
   return 0;
}
登入後複製

輸出

The maximum occurring character after performing the operations is: b
登入後複製

測試案例範例

讓我們考慮以下範例 -

  • 字串:「aabcbdb」

  • 操作:{ {1, 4}, {2, 5} }

  • 執行第一個動作(1、4):「abacbdb」

  • 執行第二個動作(2、5):「abcabdb」

執行操作後,字串變成「abcabdb」。修改後的字串中最多出現的字元是 'b',出現了 3 次。

結論

在本文中,我們探討了在執行一組給定的操作後查找字串中出現次數最多的字元的問題。我們討論了該演算法,提出了修正後的 C 實現,並提供了一個測試用例範例來演示該解決方案。掌握此類問題有助於增強您的字串操作和演算法技能,這對於程式設計挑戰和麵試至關重要。請記住根據需要仔細初始化和更新頻率數組,以確保結果準確。

以上是在執行給定操作後,找到出現次數最多的字符的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板