Medium

题目描述

你正在和朋友玩猜数字游戏。

你写下一个秘密数字，让你的朋友猜这个数字是什么。当你的朋友猜数字时，你需要给出以下提示：

  • “公牛"的数量：猜测中位置正确的数字个数。
  • “奶牛"的数量：猜测中数字正确但位置错误的数字个数。具体来说，就是猜测中的非公牛数字，这些数字可以重新排列使其变成公牛。

给定秘密数字 secret 和朋友的猜测 guess，返回对朋友猜测的提示。

提示应该格式化为 "xAyB"，其中 x 是公牛的数量，y 是奶牛的数量。注意 secret 和 guess 都可能包含重复的数字。

示例 1:

输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 公牛用 '|' 连接，奶牛用下划线标出：
"1807"
  |
"7810"

示例 2:

输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释: 公牛用 '|' 连接，奶牛用下划线标出：
"1123"        "1123"
  |      或     |
"0111"        "0111"
注意，两个不匹配的 1 中只有一个被计为奶牛，因为非公牛数字只能重新排列以允许一个 1 成为公牛。

提示:

  • 1 <= secret.length, guess.length <= 1000
  • secret.length == guess.length
  • secret 和 guess 仅由数字组成

解题思路

解题思路

这道题需要统计两种情况：

  1. 公牛（Bulls）：位置和数字都正确
  2. 奶牛（Cows）：数字正确但位置错误

方法一：两次遍历

先统计公牛数量，再分别统计每个数字在两个字符串中的出现次数，奶牛数量为每个数字的最小出现次数之和减去公牛数量。

方法二：一次遍历（推荐）

使用计数数组，遍历时：

  • 如果位置相同，公牛数量+1
  • 如果位置不同，用计数器统计：
    • 如果 secret[i] 在 guess 的计数器中有余额，说明可以配对成奶牛
    • 如果 guess[i] 在 secret 的计数器中有余额，说明可以配对成奶牛

核心思想是：对于不是公牛的位置，我们维护两个计数器分别统计 secret 和 guess 中各数字的出现次数。当发现某个数字在对方计数器中有余额时，就能形成一对奶牛。

时间复杂度：O(n)，只需要一次遍历 空间复杂度：O(1)，只使用固定大小的计数数组

代码实现

class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        vector<int> secretCount(10, 0), guessCount(10, 0);
        
        for (int i = 0; i < secret.length(); i++) {
            if (secret[i] == guess[i]) {
                bulls++;
            } else {
                if (secretCount[guess[i] - '0'] > 0) {
                    cows++;
                    secretCount[guess[i] - '0']--;
                } else {
                    guessCount[guess[i] - '0']++;
                }
                
                if (guessCount[secret[i] - '0'] > 0) {
                    cows++;
                    guessCount[secret[i] - '0']--;
                } else {
                    secretCount[secret[i] - '0']++;
                }
            }
        }
        
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = cows = 0
        secret_count = [0] * 10
        guess_count = [0] * 10
        
        for i in range(len(secret)):
            s, g = int(secret[i]), int(guess[i])
            if s == g:
                bulls += 1
            else:
                if secret_count[g] > 0:
                    cows += 1
                    secret_count[g] -= 1
                else:
                    guess_count[g] += 1
                
                if guess_count[s] > 0:
                    cows += 1
                    guess_count[s] -= 1
                else:
                    secret_count[s] += 1
        
        return f"{bulls}A{cows}B"

public class Solution {
    public string GetHint(string secret, string guess) {
        int bulls = 0, cows = 0;
        int[] secretCount = new int[10];
        int[] guessCount = new int[10];
        
        for (int i = 0; i < secret.Length; i++) {
            int s = secret[i] - '0';
            int g = guess[i] - '0';
            
            if (s == g) {
                bulls++;
            } else {
                if (secretCount[g] > 0) {
                    cows++;
                    secretCount[g]--;
                } else {
                    guessCount[g]++;
                }
                
                if (guessCount[s] > 0) {
                    cows++;
                    guessCount[s]--;
                } else {
                    secretCount[s]++;
                }
            }
        }
        
        return $"{bulls}A{cows}B";
    }
}

/**
 * @param {string} secret
 * @param {string} guess
 * @return {string}
 */
var getHint = function(secret, guess) {
    let bulls = 0;
    let cows = 0;
    let secretCount = new Array(10).fill(0);
    let guessCount = new Array(10).fill(0);
    
    for (let i = 0; i < secret.length; i++) {
        if (secret[i] === guess[i]) {
            bulls++;
        } else {
            secretCount[secret[i]]++;
            guessCount[guess[i]]++;
        }
    }
    
    for (let i = 0; i < 10; i++) {
        cows += Math.min(secretCount[i], guessCount[i]);
    }
    
    return `${bulls}A${cows}B`;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历一次字符串，n 为字符串长度
空间复杂度O(1)使用固定大小的计数数组，大小为 10

相关题目