在這個問題中,我們將計算頻率和位置具有相同奇偶校驗的字元的數量,並列印該數字的計數為奇數或偶數。
為了解決這個問題,我們可以找到字串中每個字元的頻率,並統計頻率和位置具有相同奇偶校驗的字元總數。之後,我們可以根據計數列印奇數或偶數答案。
問題陳述 - 我們給了一個只包含小寫英文字母字元的字串 alpha。我們需要檢查字母位置和頻率相同的字元數量是奇數還是偶數。
如果任何字元滿足以下任何條件,則該字元具有相同的頻率和字母位置奇偶性。
如果字串中的字元頻率為奇數,且字母位置也為奇數。
如果字串中的字元頻率是偶數,且字母位置也是偶數。
範例
輸入
alpha = "dbbabcdc"
輸出
Even
說明
#a的出現頻率為1,位置也是1,因此奇偶校驗相同,計數變成1。
d的頻率為2,位置為4。因此,由於奇偶校驗位相同,因此計數變為2。
計數值為 2,為偶數。
輸入
alpha = "ppqqr"
輸出
Odd
說明 – 只有『p』的奇偶校驗相同。因此,計數為 1,答案為奇數。
輸入
alpha = "pqqqqrrr";
輸出
Even
說明 - 任何字元的奇偶校驗都不相同。因此,由於計數值為零,它會列印“Even”。
在這種方法中,我們將使用映射資料結構來儲存每個字串字元的頻率。之後,我們將統計字母位置和頻率中具有相同奇偶性的字元的數量。
第 1 步 - 定義長度為 27 的 count[] 陣列並以 0 初始化。此外,用 0 初始化「奇偶校驗」。
第 2 步驟 - 將字元頻率儲存在 count[] 陣列中。
第 3 步 - 進行 26 次迭代以遍歷每個小寫字母字元。
步驟4 - 如果count[p]大於0,檢查字元頻率和位置是否有相同的奇偶校驗。如果是,則將「奇偶校驗」值增加 1。
第 5 步 - 最後,如果奇偶校驗可被 2 整除,則回傳「Even」。否則,返回“奇數”。
#include <bits/stdc++.h> using namespace std; string getParity(string alpha) { // To store the count of characters int count[27] = {0}; int parity = 0; // Count frequency of each character for (int p = 0; p < alpha.size(); p++) { count[alpha[p] - 'a' + 1]++; } for (int p = 1; p <= 26; p++) { if (count[p] != 0) { // Increment parity for valid odd and even parity if (p % 2 == 0 && count[p] % 2 == 0 || p % 2 == 1 && count[p] % 2 == 1) parity++; } } // Return value based on final parity count if (parity % 2 == 1) return "ODD"; else return "EVEN"; } int main() { string alpha = "dbbabcdc"; cout << "The parity of given string's character's is " << getParity(alpha); return 0; }
The parity of given string's character's is EVEN
時間複雜度 - O(N) 用於計算字元的頻率。
空間複雜度 - O(26) ~ O(1) 來儲存字母字元的頻率。
在這種方法中,我們將對給定的字串進行排序。之後,每當我們得到不同的相鄰字元時,我們都會檢查前一個字元的頻率和位置的奇偶性。
第 1 步 - 將「奇偶校驗」初始化為 0。
第 2 步 - sort() 方法用於對給定字串進行排序。
第3步 - 開始遍歷字串,並將‘charCnt’初始化為0以儲存目前字元的頻率。
步驟 4 - 如果目前字元與下一個字元不同,請檢查「charCnt」的奇偶校驗和字元位置是否相符。如果是,則將「奇偶校驗」增加 1。
第 5 步 - 如果目前字元與前一個字元相同,則將「charCnt」增加 1。
第 6 步 - 最後,如果「奇偶校驗」值為偶數,則傳回「Even」。否則,返回“奇數”。
#include <bits/stdc++.h> using namespace std; string getParity(string alpha) { int parity = 0; // Sort the string sort(alpha.begin(), alpha.end()); // Traverse the string for (int p = 0; p < alpha.size(); p++) { int charCnt = 0; // When we get different adjacent characters if (alpha[p] != alpha[p + 1]) { // Validating the odd and even parties if (charCnt % 2 == 1 && (alpha[p] - 'a' + 1) % 2 == 1 || charCnt % 2 == 0 && (alpha[p] - 'a' + 1) % 2 == 0) parity++; } else { charCnt++; } } if (parity % 2 == 1) return "ODD"; else return "EVEN"; } int main() { string alpha = "abbbccdd"; cout << "The parity of given string's character's is " << getParity(alpha); return 0; }
The parity of given string's character's is EVEN
時間複雜度 - O(NlogN) 用於對字串進行排序。
空間複雜度 - O(N) 對字串進行排序。
第一種方法採用常數空間,而第二種方法則採用動態空間對給定字串進行排序。另外,第二種方法的時間成本較高,因此建議使用第一種方法以獲得更好的效能。
以上是字母位置和頻率奇偶相同的字母數量的奇偶性的詳細內容。更多資訊請關注PHP中文網其他相關文章!