leetcode299.Bulls and Cows

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
You are playing the following 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.

Bulls and Cows游戏简单来说就是你随手写下一个n位数，并让你同学猜这个数字是什么。假设你的朋友也会猜测一个n位数，他每猜一个数字，你就需要告诉他，猜测的数字中位置正确且值正确的数字(bulls)有几个，位置不正确但是值不正确的数字(cows)有几个。

思路与代码

最开始的时候我通过两圈遍历，第一次用一个数组存储每个数字出现的次数。第二次再在此基础上计算重合的值和没有重合的值的个数。但是还有更好的方法，只需要一圈遍历就可以完成这个过程。

在一圈遍历中，每当遇到重合值，则bulls的数字加一，否则我们将secret number中的数字计数加1，guess number中的数字计数减一。这样的话，如果下一次遇到重复但是位置不同的值，我们可以知道它是否已经在secret中或是guess中出现过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String getHint(String secret, String guess){
    int bulls=0,cows=0;
    int[] counter = new int[10];
    int n=secret.length();
    for(int i =0; i<n; i++){
        int s = secret.charAt(i)-'0';
        int g = guess.charAt(i)-'0';
        if(s==g)
            bulls++;
        else{
            if(counter[g]>0) cows++;
            if(counter[s]<0) cows++;
            counter[s]++;
            counter[g]--;
        }   
    }    
    return bulls + "A" + cows + "B";
}