Go Java アルゴリズムを使用して数字当てゲームを実装する方法

数字を推測するゲーム

あなたは友達と牛と牛のゲームをプレイしています。ゲームのルールは次のとおりです:

秘密の数字を書いて友達に推測してもらいます数、いくつ。友達が推測するたびに、次の情報を含むヒントを彼に与えます:

その数字と正確な位置 (「ブル」と呼ばれる) に属する桁数を推測します。

方法多くの数字は正しく推測されましたが、位置が間違っていましたか (「牛」と呼ばれます)。 。つまり、この推測にはブルナンバーではない数字がいくつかあり、それらを並べ替えることでブルナンバーに組み合わせることができます。

秘密の数字と友達が推測した数字を教えてください。今度は友達が推測したヒントを返してください。

プロンプト形式は「xAyB」です。x は雄牛の数、y は牛の数、A は雄牛、B は牛を表します。

秘密の番号と友人が推測した番号には重複する番号が含まれる可能性があることに注意してください。

• 例 1:

入力: シークレット = "1807"、推測 = "7810"

出力: "1A3B"

• 例 2:

入力: シークレット = "1123"、推測 = "0111"

出力: "1A1B"

プロンプト:

1

secret.length ==guess.length

##secret とguess は数字のみで構成されています

方法 1: トラバーサル (Java)

の意味によると問題は、ブルの場合、番号と正確な位置の両方を正確に推測する必要があります。 Secret と \textit{guess}guess をたどって、secret[i]=guess[i] を満たす添字の数、つまり雄牛の数を数えることができます。

同じ文字の位置については、a を直接インクリメントできます;

異なる文字の位置については、「ハッシュ テーブル」を使用して、秘密と推測の単語頻度を個別にカウントします。 2 つの単語の頻度のうち、数値 x の小さい方の値が、この数値に対応する牛の数であり、すべての数値 [0,9] の牛の数の合計は 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";
    }
}

時間計算量 O(N)、N は秘密の長さです。

空間計算量 O(C)、C は文字セットのサイズです

方法 1: トラバーサル (Go) )

具体的な方法や考え方については上記で詳しく解説していますので、詳しくは上記の内容をご覧ください。

トラバースする場合、一致するものは直接雄牛としてカウントされます。一致するものがなかった場合は、すべての番号を数えてから、同じ番号の数に基づいて牛を数えます。

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

時間計算量 O(N)、N は秘密の長さです

空間計算量 O(C)、C は文字セットのサイズ

以上がGo Java アルゴリズムを使用して数字当てゲームを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。