How to use Go Java algorithm to implement number guessing game

Guess the number game

You are playing the Bulls and Cows game with your friends. The rules of the game are as follows:

Write a secret number and ask your friends to guess the number. how many. Each time your friend makes a guess, you give him a hint containing the following information:

Guess how many digits belong to the number and the exact position (called "Bulls"),

How many digits were guessed correctly but in incorrect positions (called "cows")? . In other words, there are several numbers in this guess that are not bull numbers, and they can be combined into bull numbers by rearranging them.

Give you a secret number secret and the number guessed by your friend. Please return a hint for your friend's guess this time.

The prompt format is "xAyB", x is the number of bulls, y is the number of cows, A represents bulls, and B represents cows.

Please note that both secret numbers and numbers guessed by friends may contain duplicate numbers.

• Example 1:

Input: secret = "1807", guess = "7810"

Output : "1A3B"

• Example 2:

Input: secret = "1123", guess = "0111"

Output: "1A1B"

Prompt:

1 <= secret.length, guess.length <= 1000

secret.length == guess.length

##secret and guess are composed only of numbers

Method 1: Traversal (Java)

According to the meaning of the question, for Bull, you need to guess both the number and the exact location correctly. We can traverse secret and \textit{guess}guess, and count the number of subscripts that satisfy secret[i]=guess[i], which is the number of bulls.

For positions with the same characters, we can directly increment a;

For positions with different characters, use a "hash table" to separately count the word frequency of secret and guess, a certain The smaller value of the number x in the two word frequencies is the number of cows corresponding to this number. The sum of the number of cows for all numbers [0,9] is b.

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int[] cntS = new int[10];
        int[] cntG = new int[10];
        for (int i = 0; i < secret.length(); ++i) {
            if (secret.charAt(i) == guess.charAt(i)) {
                ++bulls;
            } else {
                ++cntS[secret.charAt(i) - &#39;0&#39;];
                ++cntG[guess.charAt(i) - &#39;0&#39;];
            }
        }
        int cows = 0;
        for (int i = 0; i < 10; ++i) {
            cows += Math.min(cntS[i], cntG[i]);
        }
        return Integer.toString(bulls) + "A" + Integer.toString(cows) + "B";
    }
}

Time complexity O(N), N is the secret length

Space complexity O(C), C is the character set size

Method 1: Traversal (Go )

The specific method and ideas have been explained in detail above. Please see the above content for details.

When traversing, the matching ones will be directly counted as bulls. If there is no match, all numbers need to be counted, and then the cows are counted based on the number of identical numbers.

func getHint(secret string, guess string) string {
    bows, cows, cntsS, cntsG := 0, 0, map[rune]int{}, map[rune]int{}
    for i, k := range secret {
        if g := rune(guess[i]); g == k {
            bows++
        } else {
            cntsS[k]++
            cntsG[g]++
        }
    }
    for k, v := range cntsS {
        if vg := cntsG[k]; vg >= v {
            cows += v
        } else {
            cows += vg
        }
    }
    return strconv.Itoa(bows) + "A" + strconv.Itoa(cows) + "B"
}

Time complexity O(N), N is the secret length

Space complexity O(C), C is the character set size

The above is the detailed content of How to use Go Java algorithm to implement number guessing game. For more information, please follow other related articles on the PHP Chinese website!