[LeetCode][299. 猜数字游戏] 从遍历2次优化到遍历1次
By Long Luo
方法一:HashMap –> Array
思路与算法:
首先,\(\textit{Bulls}\) 最好计算,遍历,如果相同,那么 \(Bulls+1\)。但是 \(\textit{Cows}\) 如何计算呢?
- 首先想到的是使用 \(\texttt{HashMap}\) 来记录数字及其出现次数,因为可能会出现多个数字,所以出现位置是没有办法记录的;
- 遇到 \(\textit{Cows}\),则 \(2\) 个 \(HashMap\) 都减去相应数字;
- 最后遍历 \(0 \to 9\),如果 \(2\) 个 \(\texttt{HashMap}\) 都大于 \(0\) ,那么把较小数相加即得到 \(\textit{Cows}\)。
代码如下所示: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
27
28public String getHint(String secret, String guess) {
int len = secret.length();
int bulls = 0;
int cows = 0;
Map<Integer, Integer> secretMap = new HashMap<>();
Map<Integer, Integer> guessMap = new HashMap<>();
for (int i = 0; i < len; i++) {
int secVal = secret.charAt(i) - '0';
int guessVal = guess.charAt(i) - '0';
secretMap.put(secVal, secretMap.getOrDefault(secVal, 0) + 1);
guessMap.put(guessVal, guessMap.getOrDefault(guessVal, 0) + 1);
if (secVal == guessVal) {
bulls++;
secretMap.put(secVal, secretMap.getOrDefault(secVal, 0) - 1);
guessMap.put(guessVal, guessMap.getOrDefault(guessVal, 0) - 1);
}
}
for (int i = 0; i <= 9; i++) {
int secFreq = secretMap.getOrDefault(i, 0);
int guessFreq = guessMap.getOrDefault(i, 0);
if (secFreq > 0 && guessFreq > 0) {
cows += Math.min(secFreq, guessFreq);
}
}
return bulls + "A" + cows + "B";
}
上述代码其实可以优化,因为 \(\textit{map}\) 中的 \(\textit{key}\) 只有 \(0 \to 9\),所以我们可以用数组取代 \(\textit{map}\) 以节省空间。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public String getHint(String secret, String guess) {
int len = secret.length();
int bulls = 0;
int cows = 0;
int[] secNums = new int[10];
int[] gusNums = new int[10];
for (int i = 0; i < len; i++) {
int secVal = secret.charAt(i) - '0';
int guessVal = guess.charAt(i) - '0';
secNums[secVal]++;
gusNums[guessVal]++;
if (secVal == guessVal) {
bulls++;
secNums[secVal]--;
gusNums[guessVal]--;
}
}
for (int i = 0; i <= 9; i++) {
cows += Math.min(secNums[i], gusNums[i]);
}
return bulls + "A" + cows + "B";
}
复杂度分析
- 时间复杂度:\(O(N)\),其中 \(N\) 是字符串的长度。
- 空间复杂度:\(O(C)\),需要常数个空间统计字符出现次数,由于我们统计的是数字字符,\(C=10\)。
方法二:一次遍历
方法一依旧有两个 \(for\) 循环,分享 这里 只有一个循环的代码。
比较巧妙,相对于解法一难理解些,可以结合下边的注释理解一下。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
27
28// Opt
public static String getHint_opt(String secret, String guess) {
int bulls = 0;
int cows = 0;
int[] cnt = new int[10];
for (int i = 0; i < secret.length(); i++) {
int s = secret.charAt(i) - '0';
int g = guess.charAt(i) - '0';
if (s == g) {
bulls++;
} else {
//当前数小于 0, 说明之前在 guess 中出现过, 和 secret 当前的数匹配
if (cnt[s] < 0) {
cows++;
}
//当前数大于 0, 说明之前在 secret 中出现过, 和 guess 当前的数匹配
if (cnt[g] > 0) {
cows++;
}
//secret 中的数, 计数加 1
cnt[s]++;
//guess 中的数, 计数减 1
cnt[g]--;
}
}
return bulls + "A" + cows + "B";
}
复杂度分析
- 时间复杂度:\(O(N)\),其中 \(N\) 是字符串的长度。
- 空间复杂度:\(O(C)\),需要常数个空间统计字符出现次数,由于我们统计的是数字字符,\(C=10\)。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗