导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二

LeetCode-299.Bulls and Cows

题目

You are playing the following Bulls and Cows (https://en.wikipedia.org/wiki/Bulls_and_Cows) game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number: “1807”
Friend’s guess: “7810”

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return “1A3B”.

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

Secret number: “1123”
Friend’s guess: “0111”

In this case, the 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return “1A1B”.
You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

翻译

你在跟你的朋友玩公牛和母牛/猜数字(http://baike.baidu.com/subview/358630/11117097.htm)游戏:你写下一个数字,并让你的朋友猜数字是什么。每次你的朋友猜一个数字,你给他提示,告诉他有多少位数跟你的数字数值和位置都一样(称作“公牛”),多少位数跟你的数字数值一样但位置不对(称作“母牛”)。你的朋友会用连续的猜测和提示,最终得到数字。
例如:
秘密数字:1807
朋友猜测:7810
提示:1个公牛和3个母牛。(公牛是8,母牛是0、1和7)
编写函数返回针对秘密数字和朋友猜测的提示,使用A来代表公牛,B来表示母牛。在上面的例子中,你的函数应该返回“1A3B”。
请注意秘密梳子和朋友的猜测可能包含重复位,例如:
秘密梳子:1123
朋友猜测:0111
在这种情况下,朋友猜测的第一个1是公牛,第2和第3个1是母牛,你的函数应该返回“1A1B”。
你可以假设秘密梳子和朋友的猜测只包含数字,并且它们的长度总是相同的。

方法一

设立两个char数组,遍历一遍,计算A,并将A的位置分别置空;
设立一个map,统计secret里剩下的字符频率;
遍历guess里剩下的字符,如果map中存在并不为0,B加1,map中的频率减1:

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
29
30
31
32
33
public class Solution {
public String getHint(String secret, String guess) {
int A = 0, B = 0;
char[] secretChar = secret.toCharArray();
char[] guessChar = guess.toCharArray();

for (int i = 0; i < secretChar.length; i++) {
if (secretChar[i] == guessChar[i]) {
A++;
secretChar[i] = ' ';
guessChar[i] = ' ';
}
}

Map<Character, Integer> secretDigits = new HashMap<Character, Integer>();
for (char c : secretChar) {
if (c != ' ') {
if (secretDigits.containsKey(c))
secretDigits.put(c, secretDigits.get(c) + 1);
else secretDigits.put(c, 1);
}
}

for (char c : guessChar) {
if (secretDigits.containsKey(c) && secretDigits.get(c) > 0) {
B++;
secretDigits.put(c, secretDigits.get(c) - 1);
}
}

return A + "A" + B + "B";
}
}

15ms

方法二

将上述解法的第二三个循环,合并到第一个循环中,因为只有0到9,所以设立一个长度为10的int数组,替代map,进行记录:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
public String getHint(String secret, String guess) {
int A = 0, B = 0;
int[] nums = new int[10];

for (int i = 0; i < secret.length(); i++) {
char s = secret.charAt(i), g = guess.charAt(i);
if (s == g) A++;
else {
nums[s - '0']++;
if (nums[s - '0'] <= 0) B++;
nums[g - '0']--;
if (nums[g - '0'] >= 0) B++;
}
}

return A + "A" + B + "B";
}
}

3ms

参考:
http://my.oschina.net/Tsybius2014/blog/524452