299. 猜数字游戏

🟠   🔖  哈希表 字符串 计数  🔗 力扣 LeetCode

题目

You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

• The number of "bulls", which are digits in the guess that are in the correct position.
• The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number secret and your friend's guess guess, return the hint for your friend 's guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Example 1:

Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: Bulls are connected with a '|' and cows are underlined:

"1807" -> "7 8 10 "

Example 2:

Input: secret = "1123", guess = "0111"

Output: "1A1B"

Explanation: Bulls are connected with a '|' and cows are underlined:

"1123" -> "01 1 1" or "1123" -> "011 1"

Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.

Constraints:

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret and guess consist of digits only.

题目大意

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

• 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
• 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1：

输入： secret = "1807", guess = "7810"

输出： "1A3B"

解释： 数字猜对位置不对（奶牛）的采用斜体加粗标识。

"1807" -> "7 8 10 "

示例 2：

输入： secret = "1123", guess = "0111"

输出： "1A1B"

解释： 数字猜对位置不对（奶牛）的采用斜体加粗标识。

"1123" -> "01 1 1" or "1123" -> "011 1 "

注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

提示：

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

解题思路

1. 初始化

   • 创建一个长度为 10 的数组 count，每个位置表示数字 0 到 9 的计数，初始化为 0。
   • 变量 bulls 用于统计完全匹配的个数。

2. 遍历字符串

   • 如果 secret[i] === guess[i]，说明这个位置是 bulls，计数器加 1。
   • 更新 count 数组：
     • 对 secret[i] 的计数加 1，因为它可能贡献了一个 cow。
     • 对 guess[i] 的计数减 1，因为它可能减少一个 cow。

3. 计算cows

   • 遍历 count 数组中所有正值的和，表示这些数字没有完全匹配的部分。
   • 总的未匹配部分为 n - bulls，用它减去上述正值和，即为 cows。

4. 返回结果

   • 拼接结果为 "{bulls}A{cows}B"。

复杂度分析

• 时间复杂度：O(n)，遍历字符串一次。
• 空间复杂度：O(1)，使用一个固定大小的数组 count。

代码

/**
 * @param {string} secret
 * @param {string} guess
 * @return {string}
 */
var getHint = function (secret, guess) {
	const n = secret.length;
	let count = new Array(10).fill(0);
	let bulls = 0;

	for (let i = 0; i < n; i++) {
		if (secret[i] === guess[i]) {
			bulls++;
		}
		count[Number(secret[i])]++;
		count[Number(guess[i])]--;
	}

	const cows = n - bulls - count.reduce((a, b) => a + (b > 0 ? b : 0), 0);

	return `${bulls}A${cows}B`;
};

相关题目

题号	标题	题解	标签	难度	力扣
2531	使字符串中不同字符的数目相等		哈希表 字符串 计数	🟠	🀄️ 🔗