猜数字游戏
难度:
标签:
题目描述
你在和朋友一起玩 猜数字（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 <= 1000secret.length == guess.lengthsecret和guess仅由数字组成
代码结果
运行时间: 24 ms, 内存: 0.0 MB
/*
* 思路：
* 1. 使用Java Stream统计Bulls（公牛）的数量。
* 2. 使用Map统计secret和guess中每个字符的频率，计算Cows（奶牛）的数量。
*/
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class SolutionStream {
public String getHint(String secret, String guess) {
// 统计Bulls数量
long bulls = IntStream.range(0, secret.length())
.filter(i -> secret.charAt(i) == guess.charAt(i))
.count();
// 统计字符频率
Map<Character, Long> countSecret = secret.chars()
.boxed()
.collect(Collectors.groupingBy(ch -> (char) ch.intValue(), Collectors.counting()));
Map<Character, Long> countGuess = guess.chars()
.boxed()
.collect(Collectors.groupingBy(ch -> (char) ch.intValue(), Collectors.counting()));
// 计算Cows数量
long cows = countSecret.entrySet().stream()
.mapToLong(e -> Math.min(e.getValue(), countGuess.getOrDefault(e.getKey(), 0L)))
.sum();
cows -= bulls; // 去掉Bulls部分
return bulls + "A" + cows + "B";
}
}解释
方法:
此题解采用了两个主要步骤来解决猜数字游戏问题。首先，遍历秘密数字和猜测数字的每一位，比较对应位置的数字。如果数字相同，则这是一个公牛（Bull），计数器count_a增加。如果不同，将秘密数字和猜测数字的这一位分别记录到两个字典中，用来记录各数字出现的次数。在第一次遍历完成后，再次遍历记录的猜测数字的字典，对于字典中的每一个数字，检查它在秘密数字字典中的数量，以此来确定奶牛（Cow）的数量。奶牛的数量是由猜对的数字但位置不对的次数决定的，计算方法为两个字典中对应数字的最小出现次数之和。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中，为什么在第一次遍历时直接增加公牛计数而将不匹配的数字存储在两个字典中？这种方法有什么特别的优势吗？
▷🦆
如何确保在计算奶牛数量时不会重复计算已经作为公牛计数过的数字？
▷🦆
为什么选用defaultdict进行字典初始化？使用普通字典和defaultdict在这种情况下有什么本质的区别？
▷🦆
在计算奶牛数量时，为什么要比较`secret_dict[k]`和`guess_dict[k]`的大小，然后取较小值作为奶牛的数量？这样的逻辑是基于什么规则？
▷