CY-Left

LeetCode基本功底

[leetcode]299. Bulls and Cows-猜数字

题目和简单翻译

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.
给你玩一个游戏, 猜数字: 你写下一组数字然后由你朋友来猜. 你朋友每次猜完, 你都将告诉他位置的数值都对的 bulls 猜对了几个, 数值对了, 位置不对的 cows 有几个, 持续此过程直到猜测完毕.

比如:

Secret number:  "1807"
Friend's guess: "7810"

1 个 bull, 3 cows. (The bull is 8, the cows are 01 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”.

写一个方法, 根据你朋友猜测的结果, 用 A 表示 bull, B 表示 cows. 比如上面的例子, 你应该返回 “1A3B”.

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

请注意, 你和你朋友列举的数字都可能重复, 比如:

Secret number:  "1123"
Friend's guess: "0111"

1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".

猜测结果中第二个 1 是合理猜测, A; 第三, 第四个 1 只能算作一个 B, 因为被猜数字只剩下一个没被猜中的 1.

You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

谜底,猜测数必为数字, 且谜底和猜测数长度相同.

解题思路

  1. 大家都能想到的方法, 做两个向量, 分别存谜底和猜测结果. 两个向量有重复索引值不为 0, 则 cows++;
class Solution {
public:
    string getHint(string secret, string guess) {
        int resoultA = 0;
        int resoultB = 0;
        vector<int> hintA(10,0);
        vector<int> hintB(10,0);
        for(int i=0;i<secret.length();i++){
            if(secret[i]==guess[i]) resoultA++;
            else {
                hintA[secret[i]-'0']++;
                hintB[guess[i]-'0']++;
            }
        }
        for(int i=0;i<10;i++){
            cout<<hintA[i]<<" "<<hintB[i]<<",";
            resoultB += min(hintA[i],hintB[i]);
        }
        return to_string(resoultA)+"A"+to_string(resoultB)+"B";
    }
};
  1. 发现的一个十分聪明的算法, 只需要一个向量, 谜底触发 +1, 猜测结果触发 -1 都触发结果抵消, 此时 cow++, 整个过程中, 只循环触发过的数字, 省时.
class Solution {
public:
    string getHint(string secret, string guess) {
        vector<int> num(10,0);
        int bull = 0, cow = 0;
        for (unsigned i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) ++bull;
            else {
                num[secret[i] - '0']++;
                num[guess[i] - '0']--;
                if (num[guess[i] - '0'] >= 0) ++cow;
                if ( num[secret[i] - '0'] <= 0) ++cow;
            }
        }
        return to_string(bull) + "A" + to_string(cow) + "B";
    }
};

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=378



Have any Question or Comment?

发表评论

电子邮件地址不会被公开。 必填项已用*标注