LeetCode 299 Bulls and Cows：計算公牛與奶牛數字遊戲提示

題目大意

猜數字遊戲：密碼 secret、猜測 guess（等長數字字串）。提示格式 xAyB：

• 公牛：位置正確且數字正確的位數。
• 奶牛：數字正確但位置錯誤的位數（每個數字只能匹配一次）。

範例：secret="1807", guess="7810" → 1A3B（公牛：8；奶牛：0,1,7）。secret="1123", guess="0111" → 1A1B（第一個 1 為公牛，第二/三個 1 之一為奶牛）。

解法：單次遍歷 + 計數陣列

因為只包含數字 0-9，用大小 10 的陣列統計非公牛位置的數字頻次。

1. 第一輪遍歷：同時計算公牛數 aCnt，並對非公牛位置的 secret[i]、guess[i] 分別在 sCnt[10]、gCnt[10] 計數。
2. 第二輪：對每個數字 d=0..9，奶牛數累加 min(sCnt[d], gCnt[d])（雙方非公牛位置共同擁有的數字數量）。

C++ 完整實現

class Solution {
public:
    string getHint(string secret, string guess) {
        int aCnt = 0, bCnt = 0;
        vector<int> sCnt(10, 0), gCnt(10, 0);
        if (secret.length() != guess.length() || secret.empty()) return "0A0B";

        for (int i = 0; i < secret.length(); ++i) {
            char c1 = secret[i], c2 = guess[i];
            if (c1 == c2) {
                ++aCnt;
            } else {
                ++sCnt[c1 - '0'];
                ++gCnt[c2 - '0'];
            }
        }
        for (int i = 0; i < 10; ++i) {
            bCnt += min(sCnt[i], gCnt[i]);
        }
        return to_string(aCnt) + "A" + to_string(bCnt) + "B";
    }
};

關鍵點

• 公牛優先計算並排除，避免重複計入奶牛。
• 計數陣列大小固定 10，空間 O(1)。
• 單次遍歷 + 固定 10 次迴圈，時間 O(n)。

複雜度

• 時間：O(n)，n 為字串長度。
• 空間：O(1)（兩個大小 10 陣列）。