leetcode 299. Bulls and Cows 猜数字游戏 + 直接统计 + 很棒的做法

àì夳堔傛蜴生んèń 2022-06-08 14:37 195阅读 0赞

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.

这道题很简单，比如如正确答案为 5234，而猜的人猜 5346，则是 1A2B，其中有一个5的位置对了，记为1A，而3和4这两个数字对了，而位置没对，因此记为 2B，合起来就是 1A2B。接着猜的人再根据出题者的几A几B继续猜，直到猜中（即 4A0B）为止。

最简单的做法就是遍历 + 排序，然后遍历求解，不过比较费时。 我在网上看到了一个很不错的做法，使用一个flag计数数组来实现数字的配对，很不错。

**要学会这种统计方法，真的很棒**

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.List;
    
    /*
     * 这里是一个更好的解法，因为我们要猜的数据都是数组，所以这里设置了一个flag数组
     * 初始化为0，通过加加减减来实现配对
     * 很棒的想法
     * */
    class Solution 
    {
        public String getHint(String secret, String guess) 
        {
            if(secret==null || guess==null || secret.length()<=0 || guess.length()<=0)
                return "0A0B";
            int bull=0 , cow=0;
            int []flag=new int[10];
            Arrays.fill(flag, 0);
    
            for(int i=0;i<secret.length();i++)
            {
                int a=secret.charAt(i)-'0';
                int b=guess.charAt(i)-'0';
                if(a==b)
                    bull++;
                else 
                {
                    if(flag[a]<0)
                        cow++;
                    if(flag[b]>0)
                        cow++;
                    flag[a]++;
                    flag[b]--;
                }
            }
            return bull + "A" + cow + "B";
        }
    
        /*
         * 我这使用最傻逼的方法求解的：也即排序
         * */
        public String getHint1(String secret, String guess) 
        {
            if(secret==null || guess==null || secret.length()<=0 || guess.length()<=0)
                return "0A0B";
            int bull=0 , cow=0;
            List<Integer> ss=new ArrayList<>();
            List<Integer> gg=new ArrayList<>();
            for(int i=0;i<secret.length();i++)
            {
                if(secret.charAt(i)==guess.charAt(i))
                    bull++;
                else 
                {
                    ss.add(secret.charAt(i)-'0');
                    gg.add(guess.charAt(i)-'0');
                }
            }
    
            Collections.sort(ss);
            Collections.sort(gg);
            int i=0,j=0;
            while(i<ss.size() && j<gg.size())
            {
                if(ss.get(i)==gg.get(j))
                {
                    cow++;
                    i++;
                    j++;
                }else if(ss.get(i)<gg.get(j))
                    i++;
                else 
                    j++;
            }
            return bull+"A"+cow+"B";
        }
    }

下面是C++的做法，就是一个很简单的替换处理

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    class Solution 
    {
    public:
        string getHint(string s, string g) 
        {
            int bull = 0, row = 0;
            vector<int> flag(10,0);
            for (int i = 0; i < s.length(); i++)
            {
                int a = s[i] - '0';
                int b = g[i] - '0';
                if (a == b)
                    bull++;
                else
                {
                    if (flag[a] < 0)
                        row++;
                    if (flag[b] > 0)
                        row++;
                    flag[a]++;
                    flag[b]--;
                }
            }
    
            return to_string(bull) + "A" + to_string(row) + "B";
        }
    };