Comment utiliser l'algorithme Go Java pour implémenter un jeu de devinettes numériques

Jeu devinez le numéro

Vous jouez au jeu des taureaux et des vaches avec vos amis. Les règles du jeu sont les suivantes :

Écrivez un numéro secret et demandez à vos amis de deviner quel est le numéro. Chaque fois que votre ami devinera, vous lui donnerez un indice contenant les informations suivantes :

devinez combien de chiffres appartiennent au numéro et la position exacte du numéro (appelé "Taureaux"),

combien de chiffres devinés mais dans le mauvaise position (appelée "Vache") ? . En d’autres termes, cette supposition contient plusieurs nombres qui ne sont pas des nombres de taureaux, et ils peuvent être combinés en nombres de taureaux en les réorganisant.

Donnez-vous un numéro secret et le numéro deviné par votre ami. Veuillez renvoyer un indice pour que votre ami devine cette fois.

Le format de l'invite est "xAyB", x est le nombre de taureaux, y est le nombre de vaches, A représente les taureaux et B représente les vaches.

Veuillez noter que les numéros secrets et les numéros devinés par des amis peuvent contenir des numéros en double.

• Exemple 1 :

Entrée : secret = "1807", deviner = "7810"

Sortie : "1A3B"

• Exemple 2 :

  Entrée : sec ret = " 1123", deviner = "0111"

Sortie : "1A1B"

Indice :

1 <= secret.length, deviner.longueur <= 1000

secret.length == deviner.longueur

Le secret et la supposition sont uniquement constitués de nombres

Méthode 1 : Traversée (Java)

Selon le sens de la question, pour le taureau, le nombre et la position exacte doivent être devinés correctement. Nous pouvons parcourir secret et textit{guess}guess, et compter le nombre d'indices qui satisfont secret[i]=guess[i], qui est le nombre de taureaux.

Pour les caractères à la même position, nous pouvons directement incrémenter a ;

Pour les caractères à des positions différentes, utilisez une "table de hachage" pour compter séparément les fréquences de mots de secret et de devinette, et un certain nombre x dans les deux fréquences de mots La plus petite valeur est le nombre de vaches correspondant à ce nombre. La somme du nombre de vaches en comptant tous les nombres [0,9] est 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";
    }
}

Complexité temporelle O(N), N est la longueur secrète

Complexité spatiale O(C), C est la taille du jeu de caractères

Méthode 1 : Traversée (Go)

L'idée spécifique de la méthode a été indiquée ci-dessus détaillée explication, veuillez voir ci-dessus pour plus de détails.

Lors du parcours, ceux qui correspondent seront comptés directement comme des taureaux. S'il n'y a pas de correspondance, tous les numéros doivent être comptés, puis les vaches sont comptées sur la base du nombre de numéros identiques.

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"
}

Complexité temporelle O(N), N est la longueur secrète

Complexité spatiale O(C), C est la taille du jeu de caractères

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!