Go Java 알고리즘을 사용하여 숫자 추측 게임을 구현하는 방법

숫자 맞추기 게임

친구들과 함께 Bulls and Cows 게임을 하고 있습니다. 게임 규칙은 다음과 같습니다.

비밀번호를 쓰고 친구들에게 숫자가 무엇인지 추측해 보세요. 친구가 추측할 때마다 다음 정보가 포함된 힌트를 제공합니다.

숫자에 속하는 자릿수와 정확한 위치가 올바른지 맞춰보세요("황소"라고 함),

몇 자릿수가 있나요? 추측했지만 잘못된 위치("소"라고 함)에 있습니까? . 즉, 이 추측에는 황소 숫자가 아닌 숫자가 여러 개 있으며, 이를 재배열하여 황소 숫자로 결합할 수 있습니다.

비밀번호와 친구가 추측한 숫자를 이번에는 친구가 추측한 힌트를 돌려주세요.

프롬프트의 형식은 "xAyB"입니다. x는 황소 수, y는 소 수, A는 황소, B는 소를 나타냅니다.

비밀번호와 친구가 추측한 숫자 모두 중복된 숫자가 있을 수 있으니 주의하세요.

• 예 1:

입력: secret = "1807", 추측 = "7810"

출력: "1A3B"

• 예 2:

입력: sec ret = " 1123", 추측 = "0111"

출력: "1A1B"

힌트:

1 <= secret.length, 추측.길이 <= 1000

secret.length ==.length

비밀과 추측은 숫자로만 구성됩니다

방법 1: 순회(Java)

질문의 의미에 따라 Bull의 경우 숫자와 정확한 위치를 모두 올바르게 추측해야 합니다. 우리는 secret과 textit{guess}guess를 순회할 수 있고, secret[i]=guess[i]를 만족하는 첨자의 수, 즉 황소의 수를 셀 수 있습니다.

동일한 위치에 있는 문자의 경우 a를 직접 증가시킬 수 있습니다.

다른 위치에 있는 문자의 경우 "해시 테이블"을 사용하여 비밀 및 추측의 단어 빈도와 두 단어 빈도의 특정 숫자 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!