[Leetcode][299. 猜数字游戏] 从遍历2次优化到遍历1次

By Long Luo

Leetcode 299. 猜数字游戏

方法一:HashMap --> Array

思路与算法:

首先,Bulls最好计算,遍历,如果相同,那么Bulls+1。但是Cows如何计算呢?

  1. 首先想到的是使用HashMap来记录数字及其出现次数,因为可能会出现多个数字,所以出现位置是没有办法记录的;
  2. 遇到Cows,则2个HashMap都减去相应数字;
  3. 最后遍历0 - 9,如果2个HashMap都大于0,那么把较小数相加即得到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
28
public 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";
}

上述代码其实可以优化,因为map中的key只有09,所以我们可以用数组取代map以节省空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public 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)O(N),其中NN是字符串的长度。
  • 空间复杂度:O(C)O(C),需要常数个空间统计字符出现次数,由于我们统计的是数字字符,C=10C=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)O(N),其中NN是字符串的长度。
  • 空间复杂度:O(C)O(C),需要常数个空间统计字符出现次数,由于我们统计的是数字字符,C=10C=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. 😉😃💗