LeetCode 299 - Bulls and Cows


[LeetCode]Bulls and Cows | 书影博客
You are playing the following Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it, each time your friend guesses a number, you give a hint, the hint tells your friend how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows"), your friend will use those hints to find out 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.)
According to Wikipedia: "Bulls and Cows (also known as Cows and Bulls or Pigs and Bulls or Bulls and Cleots) is an old code-breaking mind or paper and pencil game for two or more players, predating the similar commercially marketed board game Mastermind. The numerical version of the game is usually played with 4 digits, but can also be played with 3 or any other number of digits."
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.
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.
X.
https://leetcode.com/problems/bulls-and-cows/discuss/74621/One-pass-Java-solution
int b is the count of 'cow' events. The int[] digits stores the frequency of each digit (from 0 to 9) in secret and guess. ++digits[n] means digit n is found in secret. If digits[n] was 0, now it becomes 1 denoting that n has shown up once in secret, while --digits[n] means n is found in guess. Digits[n] being smaller than 0 means n has shown up in guess before. Therefore when we find n in secret and do ++digits[n], having ++digits[n]<=0 means n was somewhere in the guess before. It is confirmed a 'cow'. Vice versa, --digits[n] >=0 means n is found in guess AND n has shown up in secret before, which makes a 'cow'.

The idea is to iterate over the numbers in secret and in guess and count all bulls right away. For cows maintain an array that stores count of the number appearances in secret and in guess. Increment cows when either number from secret was already seen in guest or vice versa.
public String getHint(String secret, String guess) {
    int bulls = 0;
    int cows = 0;
    int[] numbers = new int[10];
    for (int i = 0; i<secret.length(); i++) {
        int s = Character.getNumericValue(secret.charAt(i));
        int g = Character.getNumericValue(guess.charAt(i));
        if (s == g) bulls++;
        else {
            if (numbers[s] < 0) cows++;
            if (numbers[g] > 0) cows++;
            numbers[s] ++;
            numbers[g] --;
        }
    }
    return bulls + "A" + cows + "B";
}
A slightly more concise version:
public String getHint(String secret, String guess) {
    int bulls = 0;
    int cows = 0;
    int[] numbers = new int[10];
    for (int i = 0; i<secret.length(); i++) {
        if (secret.charAt(i) == guess.charAt(i)) bulls++;
        else {
            if (numbers[secret.charAt(i)-'0']++ < 0) cows++;
            if (numbers[guess.charAt(i)-'0']-- > 0) cows++;
        }
    }
    return bulls + "A" + cows + "B";
}
http://www.cnblogs.com/grandyang/p/4929139.html
这道题提出了一个叫公牛母牛的游戏,其实就是之前文曲星上有的猜数字的游戏,有一个四位数字,你猜一个结果,然后根据你猜的结果和真实结果做对比,提示有多少个数字和位置都正确的叫做bulls,还提示有多少数字正确但位置不对的叫做cows,根据这些信息来引导我们继续猜测正确的数字。这道题并没有让我们实现整个游戏,而只用实现一次比较即可。给出两个字符串,让我们找出分别几个bulls和cows。这题需要用哈希表,来建立数字和其出现次数的映射。我最开始想的方法是用两次遍历,第一次遍历找出所有位置相同且值相同的数字,即bulls,并且记录secret中不是bulls的数字出现的次数。然后第二次遍历我们针对guess中不是bulls的位置,如果在哈希表中存在,cows自增1,然后映射值减1
    string getHint(string secret, string guess) {
        int m[256] = {0}, bulls = 0, cows = 0;
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) ++bulls;
            else ++m[secret[i]];
        }
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] != guess[i] && m[guess[i]]) {
                ++cows;
                --m[guess[i]];
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
我们其实可以用一次循环就搞定的,在处理不是bulls的位置时,我们看如果secret当前位置数字的映射值小于0,则表示其在guess中出现过,cows自增1,然后映射值加1,如果guess当前位置的数字的映射值大于0,则表示其在secret中出现过,cows自增1,然后映射值减1
    string getHint(string secret, string guess) {
        int m[256] = {0}, bulls = 0, cows = 0;
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) ++bulls;
            else {
                if (m[secret[i]]++ < 0) ++cows;
                if (m[guess[i]]-- > 0) ++ cows;
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
最后我们还可以稍作修改写的更简洁一些,a是bulls的值,b是bulls和cows之和
    string getHint(string secret, string guess) {
        int m[256] = {0}, a = 0, b = 0, i = 0;
        for (char s : secret) {
            char g = guess[i++];
            a += s == g;
            b += (m[s]++ < 0) + (m[g]-- > 0);
        }
        return to_string(a) + "A" + to_string(b - a) + "B";
    }

http://likemyblogger.blogspot.com/2015/10/leetcode-299-bulls-and-cows.html
    string getHint(string secret, string guess) {
        int a = 0, b = 0, ns = secret.size(), ng = guess.size();
        if(ns!=ng || ns==0) return "0A0B";
         
        int s[10] = {0};
        int g[10] = {0};
        for(int i=0; i<ns; ++i){
            if(secret[i]==guess[i]){
                a++;
            }else{
                s[secret[i]-'0']++;
                g[guess[i]-'0']++;
            }
        }
        for(int i=0; i<10; ++i){
            b += min(s[i], g[i]);
        }
        return to_string(a)+"A"+to_string(b)+"B";
    }
http://storypku.com/2015/11/leetcode-question-299-bows-and-cows/
    string getHint(string secret, string guess) {
        int size = secret.size();
        int  *secret_dict = new int[10]();
        int  *guess_dict = new int[10]();
        int A = 0, B = 0;
        for(int i = 0; i < size; i++) {
            int s = secret[i] - '0', g = guess[i]- '0';
            if (s == g) {
                A++;
            } else {
                if (secret_dict[g] > 0) {
                    secret_dict[g] --;
                    B++;
                } else {
                    guess_dict[g]++;
                }
                if (guess_dict[s] > 0) {
                    guess_dict[s]--;
                    B++;
                } else {
                    secret_dict[s]++;
                }
                
            }
        }
        delete []secret_dict;
        delete []guess_dict;
        ostringstream oss;
        oss << A << 'A' << B << 'B';
        return oss.str();
    }
Best X. http://my.oschina.net/Tsybius2014/blog/524452
创建一个包含10个元素的数组,分别用于记录遇到的每个数字的情况。这个方法只需要遍历一次数组
    public String getHint(String secret, String guess) {
         
        if (secret == null || guess == null || secret.length() != guess.length()) {
            return "";
        }
         
        int countA = 0;
        int countB = 0;
        int[] count = new int[10];
         
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                countA++;
            else {
                count[secret.charAt(i) - '0']++;
                if (count[secret.charAt(i) - '0'] <= 0) {
                    countB++;
                }
                count[guess.charAt(i)- '0']--;
                if (count[guess.charAt(i)- '0'] >= 0) {
                    countB++;
                }
            }
        }
         
        return String.valueOf(countA) + "A" + String.valueOf(countB) + "B";
    }
X. 按照0-9分别统计
https://leetcode.com/discuss/68660/java-solution-with-two-buckets
https://leetcode.com/discuss/67016/3-lines-in-python?show=67016
def getHint(self, secret, guess):
    bulls = sum(map(operator.eq, secret, guess))
    both = sum(min(secret.count(x), guess.count(x)) for x in '0123456789')

    return '%dA%dB' % (bulls, both - bulls)
 3     string getHint(string secret, string guess) {
 4         int bull = 0, both = 0, n = secret.length();
 5         for (int i = 0; i < n; i++)
 6             bull += (secret[i] == guess[i]);
 7         for (char c = '0'; c <= '9'; c++)
 8             both += min(count(secret.begin(), secret.end(), c), 
 9                         count(guess.begin(), guess.end(), c));
10         return to_string(bull) + "A" + to_string(both - bull) + "B";
11     }
12 };
https://leetcode.com/discuss/79935/easy-java-solution
public String getHint(String secret, String guess) {
    int bull = 0, cow = 0;
    int[] array = new int[10];

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

}
https://leetcode.com/discuss/67031/one-pass-java-solution
The idea is to iterate over the numbers in secret and in guess and count all bulls right away. For cows maintain an array that stores count of the number appearances in secret and inguess. Increment cows when either number from secret was already seen in guest or vice versa.
https://leetcode.com/discuss/68660/java-solution-with-two-buckets
https://leetcode.com/discuss/89261/my-3ms-java-solution-may-help-u
public String getHint(String secret, String guess) { int bull = 0, cow = 0; int[] sarr = new int[10]; int[] garr = new int[10]; for(int i = 0; i < secret.length(); i++){ if(secret.charAt(i) != guess.charAt(i)){ sarr[secret.charAt(i)-'0']++; garr[guess.charAt(i)-'0']++; }else{ bull++; } } for(int i = 0; i <= 9; i++){ cow += Math.min(sarr[i], garr[i]); } return (bull + "A" + cow + "B"); }
http://my.oschina.net/Tsybius2014/blog/524452
做这道题还需要注意,一般的猜数字游戏中,被猜的数字有四个且互不相同,但在本题中,可以有任意多个数字,且数字有可能存在同一数字重复多次出现的情况。
一开始我想了一个比较笨的办法,即分别求出A和B的数量,暴力破解
    public String getHint(String secret, String guess) {
         
        if (secret == null || guess == null || secret.length() != guess.length()) {
            return "";
        }
         
        int countA = 0;
        int countB = 0;
         
        char[] arrA = secret.toCharArray();
        char[] arrB = guess.toCharArray();
         
        //求A的数量
        for (int i = 0; i < arrA.length; i++) {
            for (int j = 0; j < arrB.length; j++) {
                if (arrA[i] == ' ' || arrB[j] == ' ') {
                    continue;
                else if (arrA[i] == arrB[j]) {
                    if (i == j) {
                        countA++;
                        arrA[i] = ' ';
                        arrB[j] = ' ';
                    }
                }
            }
        }
        //求B的数量
        for (int i = 0; i < arrA.length; i++) {
            for (int j = 0; j < arrB.length; j++) {
                if (arrA[i] == ' ' || arrB[j] == ' ') {
                    continue;
                else if (arrA[i] == arrB[j]) {
                    countB++;
                    arrA[i] = ' ';
                    arrB[j] = ' ';
                }
            }
        }
         
        return String.valueOf(countA) + "A" + String.valueOf(countB) + "B";
    }

https://www.cnblogs.com/grandyang/p/5420262.html

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts