So verwenden Sie den Go Java-Algorithmus, um ein Zahlenschätzspiel zu implementieren

Rate das Zahlenspiel

Du spielst mit deinen Freunden das Spiel „Bullen und Kühe“. Die Spielregeln lauten wie folgt:

Schreibe eine Geheimzahl und bitte deine Freunde, die Zahl zu erraten. Jedes Mal, wenn Ihr Freund rät, geben Sie ihm einen Hinweis mit den folgenden Informationen:

Raten Sie, wie viele Ziffern zu der Zahl gehören und wo sich die Zahl genau befindet (genannt „Bullen“),

Wie viele Ziffern haben Sie erraten, aber in der falsche Position (genannt „Kuh“)? . Mit anderen Worten: In dieser Vermutung gibt es mehrere Zahlen, die keine Bullenzahlen sind, und sie können durch Umordnen zu Bullenzahlen kombiniert werden.

Gib dir eine Geheimnummer und die von deinem Freund erratene Nummer. Bitte gib diesmal einen Hinweis für die Vermutung deines Freundes zurück.

Das Format der Eingabeaufforderung ist „xAyB“, x ist die Anzahl der Bullen, y ist die Anzahl der Kühe, A steht für Bullen und B steht für Kühe.

Bitte beachten Sie, dass sowohl Geheimnummern als auch von Freunden erratene Nummern doppelte Nummern enthalten können. ??

• Ausgabe: „1A1B“

Hinweis:

1 <= Secret.length, Guess.länge <= 1000

Geheime Länge == Guess.Länge

Geheimnis und Rate bestehen nur aus Zahlen

• Methode 1: Traversal (Java)

Je nach Bedeutung der Frage müssen für den Bullen sowohl die Zahl als auch die genaue Position richtig erraten werden. Wir können Secret und Textit{guess}guess durchqueren und die Anzahl der Indizes zählen, die Secret[i]=guess[i] erfüllen, was der Anzahl der Bullen entspricht.

Für Zeichen an derselben Position können wir a direkt erhöhen.

Für Zeichen an unterschiedlichen Positionen verwenden wir eine „Hash-Tabelle“, um die Worthäufigkeiten von Geheimnis und Vermutung sowie eine bestimmte Zahl x in den beiden Worthäufigkeiten getrennt zu zählen Der kleinere Wert ist die Anzahl der Kühe, die dieser Zahl entspricht. Die Summe der Anzahl der Kühe, die alle Zahlen zählen [0,9], ist 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";
    }
}

Nach dem Login kopieren

Zeitkomplexität O(N), N ist die geheime Länge

Raumkomplexität O(C), C ist die Zeichensatzgröße

Methode 1: Traversal (Go)

Die spezifische Methodenidee wurde oben detailliert beschrieben Erläuterungen finden Sie oben.

Beim Durchqueren werden die passenden direkt als Bullen gezählt. Wenn es keine Übereinstimmung gibt, müssen alle Zahlen gezählt werden, und dann werden die Kühe auf der Grundlage der Anzahl identischer Zahlen gezählt.

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

Zeitkomplexität O(N), N ist die geheime Länge

Raumkomplexität O(C), C ist die Zeichensatzgröße

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Go Java-Algorithmus, um ein Zahlenschätzspiel zu implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!