首頁  >  文章  >  後端開發  >  字母位置和頻率奇偶相同的字母數量的奇偶性

字母位置和頻率奇偶相同的字母數量的奇偶性

WBOY
WBOY轉載
2023-09-14 15:41:061341瀏覽

字母位置和頻率奇偶相同的字母數量的奇偶性

在這個問題中,我們將計算頻率和位置具有相同奇偶校驗的字元的數量,並列印該數字的計數為奇數或偶數。

為了解決這個問題,我們可以找到字串中每個字元的頻率,並統計頻率和位置具有相同奇偶校驗的字元總數。之後,我們可以根據計數列印奇數或偶數答案。

問題陳述 - 我們給了一個只包含小寫英文字母字元的字串 alpha。我們需要檢查字母位置和頻率相同的字元數量是奇數還是偶數。

如果任何字元滿足以下任何條件,則該字元具有相同的頻率和字母位置奇偶性。

  • 如果字串中的字元頻率為奇數,且字母位置也為奇數。

  • 如果字串中的字元頻率是偶數,且字母位置也是偶數。

範例

輸入

alpha = "dbbabcdc"

輸出

Even

說明 

  • #a的出現頻率為1,位置也是1,因此奇偶校驗相同,計數變成1。

  • d的頻率為2,位置為4。因此,由於奇偶校驗位相同,因此計數變為2。

計數值為 2,為偶數。

輸入

alpha = "ppqqr"

輸出

Odd

說明 – 只有『p』的奇偶校驗相同。因此,計數為 1,答案為奇數。

輸入

alpha = "pqqqqrrr";

輸出

Even

說明 - 任何字元的奇偶校驗都不相同。因此,由於計數值為零,它會列印“Even”。

方法 1

在這種方法中,我們將使用映射資料結構來儲存每個字串字元的頻率。之後,我們將統計字母位置和頻率中具有相同奇偶性的字元的數量。

演算法

第 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) 來儲存字母字元的頻率。

方法2

在這種方法中,我們將對給定的字串進行排序。之後,每當我們得到不同的相鄰字元時,我們都會檢查前一個字元的頻率和位置的奇偶性。

演算法

第 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中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除