資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究執行給定操作後查找出現次數最多的字元
在本文中，我們將探討在執行給定的一組操作後查詢字串中出現次數最多的字元的概念。此問題通常出現在程式設計挑戰和麵試中，掌握解決方案有助於增強您的字串操作和演算法技能。我們將解釋問題陳述，討論使用的演算法，提供實現，並提供一個測試用例示例來演示解決方案。
問題陳述
給定一個字串 s 和一組操作，在執行所有操作後查找出現次數最多的字元。每個操作都由一對 (i, j) 組成，表示我們應該交換字串中位置 i 和 j 處的字元。
演算法
建立一個頻率陣列來儲存字串中每個字元的出現次數。
遍歷操作，交換指定位置的字元。
每次交換後更新頻率陣列。
遍歷頻率陣列以查找出現次數最多的字元。
實現
示例
以下是上述演算法的程式：
#include <stdio.h>
#include <string.h>
char maxOccurringChar(const char *s, const int operations[][2], int numOperations) {
int frequency[26] = {0};
char modifiedString[100];
strcpy(modifiedString, s);
// Initialize the frequency array with the original string's character occurrences
for (int i = 0; modifiedString[i] != '\0'; i++) {
frequency[modifiedString[i] - 'a']++;
}
for (int op = 0; op < numOperations; op++) {
int i = operations[op][0];
int j = operations[op][1];
// Decrement the frequency of the characters being swapped
frequency[modifiedString[i] - 'a']--;
frequency[modifiedString[j] - 'a']--;
// Perform the swap
char temp = modifiedString[i];
modifiedString[i] = modifiedString[j];
modifiedString[j] = temp;
// 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() {
const char *s = "aabcbdb";
int operations[][2] = { {1, 4}, {2, 5} };
int numOperations = sizeof(operations) / sizeof(operations[0]);
char maxChar = maxOccurringChar(s, operations, numOperations);
printf("The maximum occurring character after performing the operations is: %c\n", maxChar);
return 0;
}
輸出
The maximum occurring character after performing the operations is: b
#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
import java.util.Arrays;
public class MaxOccurringChar {
public static char maxOccurringChar(String s, int[][] operations) {
int[] frequency = new int[26];
char[] modifiedString = s.toCharArray();
// Initialize the frequency array with the original string's character occurrences
for (char c : modifiedString) {
frequency[c - 'a']++;
}
for (int[] op : operations) {
int i = op[0];
int j = op[1];
// Decrement the frequency of the characters being swapped
frequency[modifiedString[i] - 'a']--;
frequency[modifiedString[j] - 'a']--;
// Perform the swap
char temp = modifiedString[i];
modifiedString[i] = modifiedString[j];
modifiedString[j] = temp;
// 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 = (char) ('a' + i);
}
}
return maxChar;
}
public static void main(String[] args) {
String s = "aabcbdb";
int[][] operations = { {1, 4}, {2, 5} };
char maxChar = maxOccurringChar(s, operations);
System.out.println("The maximum occurring character after performing the operations is: " + maxChar);
}
}
輸出
The maximum occurring character after performing the operations is: b
def max_occuring_char(s, operations):
frequency = [0] * 26
modified_string = list(s)
# Initialize the frequency array with the original string's character occurrences
for c in modified_string:
frequency[ord(c) - ord('a')] += 1
for op in operations:
i, j = op
# Decrement the frequency of the characters being swapped
frequency[ord(modified_string[i]) - ord('a')] -= 1
frequency[ord(modified_string[j]) - ord('a')] -= 1
# Perform the swap
modified_string[i], modified_string[j] = modified_string[j], modified_string[i]
# Increment the frequency of the swapped characters
frequency[ord(modified_string[i]) - ord('a')] += 1
frequency[ord(modified_string[j]) - ord('a')] += 1
# Find the character with the maximum occurrence
max_frequency = 0
max_char = 'a'
for i in range(26):
if frequency[i] > max_frequency:
max_frequency = frequency[i]
max_char = chr(ord('a') + i)
return max_char
s = "aabcbdb"
operations = [(1, 4), (2, 5)]
max_char = max_occuring_char(s, operations)
print("The maximum occurring character after performing the operations is:", max_char)
輸出
The maximum occurring character after performing the operations is: b
測試用例示例
讓我們考慮以下示例：
字串：“aabcbdb”
操作：{ {1, 4}, {2, 5} }
執行第一個操作 (1, 4)：“abacbdb”
執行第二個操作 (2, 5)：“abcabdb”
執行完操作後，字串變為“abcabdb”。修改後的字串中出現次數最多的字元是 'b'，出現了三次。
結論
在本文中，我們探討了在執行給定的一組操作後查詢字串中出現次數最多的字元的問題。我們討論了演算法，提供了正確的實現，並提供了一個測試用例示例來演示解決方案。掌握此類問題有助於增強您的字串操作和演算法技能，這些技能對於程式設計挑戰和麵試至關重要。請記住，根據需要仔細初始化和更新頻率陣列以確保結果準確。
更新於： 2023年10月20日
534 次瀏覽
廣告