資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究對長度為 1 到 N 的每個字首執行所述操作後，每個小寫字元的計數
在這個問題中，我們需要對每個字串字首執行給定的操作。最後，我們需要計算每個字元的頻率。
我們可以遵循貪婪演算法來解決這個問題。我們需要獲取長度為 K 的每個字首，並根據給定的條件更新其字元。我們可以使用對映來計算最終字串中字元的頻率。
問題陳述 - 我們得到了包含 N 個小寫字母字元的字串 tr。我們還得到了對映列表，其中包含總共 26 個元素。每個元素根據其值對映到小寫字元。例如，mapping[0] 對映到 'a'，mapping[1] 對映到 'b'，mapping[25] 對映到 'z'。此外，mapping 陣列包含 1 或 -1。
我們需要執行以下操作。
獲取長度為 K 的字首中的最大字元，並從 'mapping' 陣列中獲取對映值。
如果對映值為 1，則將所有字首元素增加 1。
如果對映值為 -1，則將所有字首元素減少 1。
這裡，增加元素意味著 'a' -> 'b'，'b' -> 'c'，… 'z' -> 'a'。
減少元素意味著 'a' -> 'z'，'b' -> 'a'，… 'z' -> 'y'。
我們需要對長度為 1 <= K <= N 的每個字首執行上述操作。我們需要在執行上述操作後列印每個字元的頻率。
示例
輸入
mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = ‘progress’
輸出
0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0
解釋
在長度為 1 的字首中，最大字元是 'p'，對映值為 -1。因此，更新後的字串將是 'orogress'。
在長度為 2 的字首中，最大字元是 'r'，對映值為 -1。因此，更新後的字串將是 'nqogress'。
在長度為 3 的字首中，最大字元是 'q'，對映值為 1。因此，更新後的字串是 'orpgress'。
當我們完成所有操作後，最終字串將是 'pqmfpdqr'，其中包含 1 個 'f'，2 個 'p'，2 個 'q'，1 個 'm'，1 個 'd' 和 1 個 'r'。在輸出中，我們列印了結果字串中每個字元的頻率。
輸入
mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = "ab",
輸出
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
解釋 - 執行所有操作後，最終字串為 'ac'，我們列印了每個字元的頻率。
方法 1
在這種方法中，我們將遍歷字串並將 K 的值設定為等於索引 P。之後，我們將獲取長度等於 P 的字首，找到最大字元，獲取對映值，並相應地更新所有字首字元。
演算法
步驟 1 - 定義 'max_char' 變數來儲存給定字首的最大字元。
步驟 2 - 還初始化長度為 26 的列表，其值為零，用於儲存最終字串中每個字元的頻率。
步驟 3 - 開始遍歷字串，並在迴圈內將 'max_char' 變數初始化為 96。
步驟 4 - 使用巢狀迴圈從長度為 p 的字首中找到最大字元。
步驟 5 - 透過新增 max_char 的對映值來更新字首的每個字元。
步驟 7 - 如果更新後的字元小於 'a'，則將其更新為 'z'。
步驟 8 - 如果更新後的字元大於 'z'，則將其更新為 'a'。
步驟 9 - 最後，透過遍歷更新後的字串，將每個字元的頻率儲存在列表中。
步驟 10 - 列印字元的頻率。
示例
#include <bits/stdc++.h>
using namespace std;
void performOperations(string &str, vector<int> &mapping) {
int len = str.length();
char max_char;
// array to store the final frequency of each character
int freq[26] = {0};
for (int p = 0; p < len; p++) {
max_char = 96;
// Get the maximum character from the prefix string
for (int q = 0; q <= p; q++) {
max_char = max(max_char, str[q]);
}
// Update the prefix string by adding the max character's value.
for (int q = 0; q <= p; q++) {
// adding the mapping value to the current character
str[q] += mapping[max_char - 'a'];
// If the updated value is greater than z or less than a, update it
if (str[q] < 'a') {
str[q] = 'z';
} else if (str[q] > 'z') {
str[q] = 'a';
}
}
}
// Counting frequency of each character
for (int p = 0; p < len; p++) {
freq[str[p] - 'a']++;
}
// print count of each character in the updated string
for (auto ch : freq) {
cout << ch << ' ';
}
}
int main() {
string S = "progress";
vector<int> mapping = {-1, 1, 1, -1, 1, 1, -1, -1,
-1, 1, 1, 1, -1, 1, -1, 1, -1,
1, -1, 1, 1, 1, -1, 1, 1, 1};
performOperations(S, mapping);
return 0;
}
輸出
0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0
時間複雜度 - O(N*N)，因為我們使用兩個巢狀迴圈遍歷字串。
空間複雜度 - O(1)，因為我們使用常量空間來儲存字元的頻率。
結論
我們對輸入字串執行了給定的操作，並在輸出中列印了更新後字串的字元頻率。程式設計師也可以使用 C++ 中的對映來儲存字元頻率，而不是使用列表。為了更多練習，程式設計師可以嘗試列印更新字串中每個字元的累積頻率。
54 次檢視
