Go Java 알고리즘 디코딩 방법 예제 코드 분석-java지도 시간-php.cn

Go Java 알고리즘 디코딩 방법 예제 코드 분석

WBOY

풀어 주다： 2023-04-28 08:22:06

앞으로

887명이 탐색했습니다.

디코딩 방법

문자 A-Z가 포함된 메시지는 다음 매핑으로 인코딩됩니다.

'A' -> "1"
'B' -> .
'Z' -> "26"
인코딩된 메시지를 디코딩하려면 위에 매핑된 방법을 기반으로 모든 숫자를 문자로 다시 매핑해야 합니다(여러 방법이 있을 수 있음). 예를 들어, "11106"은

"KJF" 로 그룹화되고, 메시지는 (11 10 6)

으로 그룹화됩니다. "6"과 "06"은 매핑에서 동일하지 않기 때문에 "06"은 "F"에 매핑될 수 없기 때문에 (1 11 06)으로 그룹화됩니다.

숫자만 포함된 비어 있지 않은 문자열 s가 있는 경우 전체 디코딩 방법 수를 계산하여 반환하세요.

질문 데이터는 답변이 32비트 정수여야 함을 보장합니다.

예 1:

입력: s = "12"

출력: 2

설명: "AB"(1 2) 또는 "L"(12)로 디코딩할 수 있습니다.

예 2:

입력: s = "226"

출력: 3

설명: "BZ"(2 26), "VF"(22 6), 또는 "BBF" (2 2 6) .

예 3:

입력: s = "0"

출력: 0

설명: 0으로 시작하는 숫자에 매핑되는 문자는 없습니다.
0을 포함하는 유효한 매핑은 'J' ->

문자가 없기 때문에 모든 숫자를 매핑해야 하므로 이를 디코딩하는 효율적인 방법이 없습니다.

팁:

1 <= s.length <= 100

에는 숫자만 포함되며 앞에 0이 포함될 수 있습니다.
방법 1: 동적 프로그래밍(Java)

주어진 문자열 s에 대해 길이를 n으로 두고 왼쪽에서 오른쪽으로 문자는 s[1], s[2],..., s[입니다. N]. 동적 프로그래밍을 사용하여 문자열의 디코딩 방법 수를 계산할 수 있습니다.

구체적으로 fi는 문자열 s의 첫 번째 i 문자 s[1..i]에 대한 디코딩 방법 수를 나타냅니다. 상태 전송을 수행할 때 s의 어떤 문자가 마지막 디코딩에 사용되었는지 고려할 수 있습니다

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != &#39;0&#39;) {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != &#39;0&#39; && ((s.charAt(i - 2) - &#39;0&#39;) * 10 + (s.charAt(i - 1) - &#39;0&#39;) <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

로그인 후 복사

시간 복잡도: o(n)

공간 복잡도: o(n)

방법 2: 동적 프로그래밍—&mdash ;최적화(go )

구체적인 방법 아이디어는 위의 설명을 참조하세요. 이 방법은 임시 변수를 사용하여 공간 복잡도를 o(n)에서 o(1)로 줄입니다.

func numDecodings(s string) int {
    n := len(s)
    // a = f[i-2], b = f[i-1], c = f[i]
    a, b, c := 0, 1, 0
    for i := 1; i <= n; i++ {
        c = 0
        if s[i-1] != &#39;0&#39; {
            c += b
        }
        if i > 1 && s[i-2] != &#39;0&#39; && ((s[i-2]-&#39;0&#39;)*10+(s[i-1]-&#39;0&#39;) <= 26) {
            c += a
        }
        a, b = b, c
    }
    return c
}

로그인 후 복사