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

发表于 更新于 分类于 阅读次数： 本文字数： 2.9k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 299. 猜数字游戏 。

方法一：HashMap --> Array

思路与算法：

首先，Bulls\textit{Bulls} 最好计算，遍历，如果相同，那么 Bulls+1Bulls+1。但是 Cows\textit{Cows} 如何计算呢？

  1. 首先想到的是使用 HashMap\texttt{HashMap} 来记录数字及其出现次数，因为可能会出现多个数字，所以出现位置是没有办法记录的；
  2. 遇到 Cows\textit{Cows}，则 22 个 HashMapHashMap 都减去相应数字；
  3. 最后遍历 0→90 \to 9，如果 22 个 HashMap\texttt{HashMap} 都大于 00 ，那么把较小数相加即得到 Cows\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
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\textit{map} 中的 key\textit{key} 只有 0→90 \to 9，所以我们可以用数组取代 map\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
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。

方法二：一次遍历

方法一依旧有两个 forfor 循环，分享 这里 只有一个循环的代码。

比较巧妙，相对于解法一难理解些，可以结合下边的注释理解一下。

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. 😉😃💗