[LeetCode] 299. Bulls and Cows

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”
|
“7810”

Example 2:
Input: secret = “1123”, guess = “0111”
Output: “1A1B”
Explanation: Bulls are connected with a ‘|’ and cows are underlined:
“1123” “1123”
| or |
“0111” “0111”
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 表示奶牛。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bulls-and-cows
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题不涉及任何算法，需要用到 hashmap。用一个 for loop 遍历 secret 和 guess，当在同一位置上的数字相同时，就 bulls++，说明在同样位置找到了正确的字母；但是当同一位置上的字母不同的时候，则分别用两个数组记录 secret 和 guess 这个位置上出现的数字分别是什么。input 遍历完之后，再遍历一遍刚才的 num 数组，在数组中相同位置上的次数，取较小的那个，记为 cows。最后再把字符串按规则拼接好输出即可。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public String getHint(String secret, String guess) {
        int[] map1 = new int[10];
        int[] map2 = new int[10];
        int n = secret.length();
        int bulls = 0;
        int cows = 0;
        for (int i = 0; i < n; i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s == g) {
                bulls++;
            } else {
                map1[s - '0']++;
                map2[g - '0']++;
            }
        }

        for (int i = 0; i < 10; i++) {
            int min = Math.min(map1[i], map2[i]);
            cows += min;
        }
        String res = bulls + "A" + cows + "B";
        return res;
    }
}