夯实算法-猜数字游戏

妖狐艹你老母 2023-10-03 21:55 3阅读 0赞

### 题目：[LeetCode][] ###

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

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

猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛）， 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。 给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

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

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

**提示1**

输入：secret = "1807", guess = "7810"
    输出："1A3B"
    解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
    "1807"
      |
    "7810"
    复制代码

**示例 2：**

输入：secret = "1123", guess = "0111"
    输出："1A1B"
    解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
    "1123"        "1123"
      |      or     |
    "0111"        "0111"
    注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。
    复制代码

**提示：**

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

### 解题思路 ###

遍历的过程找到“公牛”和“奶牛”的数量，但是需要注意的是，只有当一个数字即与相同下标的另一个数字不同，且后面出现的相同数字不是“公牛”的时候，它才是“奶牛”。即，“12342”和“53389”，第二个‘3’不是“奶牛”也不是“公牛”，因为guess第三个‘3’是“公牛”，相当于消耗了secret的第三个‘3’，所以第二个‘3’没有对应的数字。

所以，当第一次遍历的时候，如果一个数字不是“公牛”，不能以secret后面出现了它判断它是“奶牛”，因为后面的可能是“公牛”。因此，分两次遍历，第一次找出所有的公牛，第二次找出剩下的奶牛。

### 代码实现 ###

public String getHint(String secret, String guess) {
        int bulls = 0, cows = 0;
        int[] map = new int[10];
        for (char c : secret.toCharArray()) {
            map[c - '0']++;
        }
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s == g) {
                bulls++;
                map[s - '0']--;
            } 
        }
        for (int i = 0; i < secret.length(); i++) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s != g) {
                if (map[g - '0'] > 0) {
                    cows++;
                    map[g - '0']--;
                }
            } 
        }
        return bulls + "A" + cows + "B";
    }
    复制代码

### 复杂度分析 ###

*  空间复杂度：O(1)O(1)O(1)
 *  时间复杂度：O(N)O(N)O(N)

在[掘金(JUEJIN)][JUEJIN] 一起分享知识, Keep Learning!

[LeetCode]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fbulls-and-cows%2F
[JUEJIN]: https://juejin.cn/user/3051900007626103