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

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

By Long Luo

Leetcode 299. 猜数字游戏 。

方法一：HashMap –> Array

思路与算法：

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

  1. 首先想到的是使用 \(\texttt{HashMap}\) 来记录数字及其出现次数，因为可能会出现多个数字，所以出现位置是没有办法记录的；
  2. 遇到 \(\textit{Cows}\)，则 \(2\) 个 \(HashMap\) 都减去相应数字；
  3. 最后遍历 \(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
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";
}

上述代码其实可以优化，因为 \(\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
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)\)，其中 \(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. 😉😃💗