LeetCode 299 Bulls and Cows 解題詳解：哈希表計數與雙遍歷策略

題目重述

給定祕密數字 secret 與猜測數字 guess（等長、僅含數字），回傳提示 xAyB：

• Bulls (A)：位置與數字皆正確的位數。
• Cows (B)：數字存在但位置錯誤的位數（不重複計算已匹配的 Bulls）。

範例：secret="1807", guess="7810" → "1A3B" (Bull: 8; Cows: 0,1,7)。
secret="1123", guess="0111" → "1A1B" (第 1 個 1 是 Bull，第 2/3 個 1 中有一個是 Cow)。

核心思路：哈希表計數 + 雙遍歷

1. 第一遍遍歷： 統計 secret 中各數字出現次數至 Map<Character, Integer>；同時比對同位置字元，若相同 → bull++，並將該數字計數 -1（避免被後續 Cows 重複計算），標記該位置已匹配。
2. 第二遍遍歷： 掃描 guess，跳過已標記為 Bull 的位置；若該字元在 Map 中計數 > 0 → cow++，計數 -1。
3. 最終組合 bull + "A" + cow + "B"。

Java 實作（優化版）

public class BullsAndCows {
    public static String getHint(String secret, String guess) {
        int[] cnt = new int[10]; // 數字 0-9，陣列比 HashMap 更快
        int bull = 0, cow = 0;
        int n = secret.length();
        boolean[] matched = new boolean[n];

        // 統計 secret 各數字頻次
        for (char c : secret.toCharArray()) cnt[c - '0']++;

        // 第一遍：找 Bulls，並扣減計數
        for (int i = 0; i < n; i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                bull++;
                cnt[guess.charAt(i) - '0']--; // 扣除已匹配位
                matched[i] = true;
            }
        }

        // 第二遍：找 Cows
        for (int i = 0; i < n; i++) {
            if (!matched[i]) {
                int d = guess.charAt(i) - '0';
                if (cnt[d] > 0) {
                    cow++;
                    cnt[d]--;
                }
            }
        }
        return bull + "A" + cow + "B";
    }

    public static void main(String[] args) {
        System.out.println(getHint("1122", "1222")); // 3A0B
        System.out.println(getHint("1807", "7810")); // 1A3B
        System.out.println(getHint("1123", "0111")); // 1A1B
    }
}

複雜度分析

• 時間： O(n)，兩次線性遍歷。
• 空間： O(1)，固定大小 10 的陣列 + n 的布林陣列（可進一步優化為位運算或原地修改字元陣列）。

常見陷阱與注意點

• 重複數字處理：必須先扣除 Bulls 對應的計數，否則 Cows 會重複計算。
• 輸入長度相等、僅含數字，無需額外驗證。
• 若使用 HashMap 需注意 getOrDefault、merge 等 API 簡化代碼；陣列效能更優。