LeetCode299-猜数字游戏

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/bulls-and-cows/

中文链接：https://leetcode-cn.com/problems/bulls-and-cows/

题目详述

你正在和你的朋友玩 猜数字（Bulls and Cows）游戏：你写下一个数字让你的朋友猜。每次他猜测后，你给他一个提示，告诉他有多少位数字和确切位置都猜对了（称为“Bulls”, 公牛），有多少位数字猜对了但是位置不对（称为“Cows”, 奶牛）。你的朋友将会根据提示继续猜，直到猜出秘密数字。

请写出一个根据秘密数字和朋友的猜测数返回提示的函数，用 A 表示公牛，用 B 表示奶牛。

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

示例 1:

1
2
3
4
5
输入: secret = "1807", guess = "7810"

输出: "1A3B"

解释: 1 公牛和 3 奶牛。公牛是 8，奶牛是 0, 1 和 7。

示例 2:

1
2
3
4
5
输入: secret = "1123", guess = "0111"

输出: "1A1B"

解释: 朋友猜测数中的第一个 1 是公牛，第二个或第三个 1 可被视为奶牛。

说明: 你可以假设秘密数字和朋友的猜测数都只包含数字，并且它们的长度永远相等。

题目详解

  • 遍历两个字符串，运用哈希表对每个字符进行计数。
  • 在相同位置两个字符相同则属于 A，在不同位置相同的字符则属于 B（取两者计数的较小值）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LeetCode_00299 {

    public String getHint(String secret, String guess) {
        Map<Character, Integer> secretMap = new HashMap<>();
        Map<Character, Integer> guessMap = new HashMap<>();
        int a = 0, b = 0;
        int length = secret.length();
        for (int i = 0; i < length; ++i) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s == g) {
                ++a;
            } else {
                secretMap.put(s, secretMap.getOrDefault(s, 0) + 1);
                guessMap.put(g, guessMap.getOrDefault(g, 0) + 1);
            }
        }
        for (Map.Entry<Character, Integer> entry : guessMap.entrySet()) {
            Integer value = secretMap.get(entry.getKey());
            if (value != null) {
                b += Math.min(entry.getValue(), value);
            }
        }
        return a + "A" + b + "B";
    }
}
  • 由于题目保证字符串中所有字符均为数字，可以用 int 型数组充当哈希表。
  • 由于是取两者计数中的较小值，可以用一个哈希表来进行计数。
  • 对于每一个 secret 中的字符，对应哈希表中位置采取加一操作；对于每一个 guess 中的字符，对应哈希表中位置采取减一操作。
  • secret 采取加一操作后，值小于等于 0，说明之前 guess 存在这个字符，B 的计数可以加一。
  • guess 采取减一操作后，值大于等于 0，说明之前 secret 存在这个字符，B 的计数可以加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00299 {

    public String getHint(String secret, String guess) {
        int[] map = new int[10];
        int a = 0, b = 0;
        int length = secret.length();
        for (int i = 0; i < length; ++i) {
            char s = secret.charAt(i);
            char g = guess.charAt(i);
            if (s == g) {
                ++a;
            } else {
                if (++map[s - '0'] <= 0) ++b;   // 说明之前 guess 至少有一个 s
                if (--map[g - '0'] >= 0) ++b;   // 说明之前 secret 至少有一个 g
            }
        }
        return a + "A" + b + "B";
    }
}