By Long Luo
Leetcode 299. 猜数字游戏 。
方法一:HashMap --> Array
思路与算法:
首先,Bulls 最好计算,遍历,如果相同,那么 Bulls+1。但是 Cows 如何计算呢?
- 首先想到的是使用 HashMap 来记录数字及其出现次数,因为可能会出现多个数字,所以出现位置是没有办法记录的;
- 遇到 Cows,则 2 个 HashMap 都减去相应数字;
- 最后遍历 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 只有 0→9,所以我们可以用数组取代 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
| 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 { if (cnt[s] < 0) { cows++; } if (cnt[g] > 0) { cows++; } cnt[s]++; 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. 😉😃💗