Go Java kaedah penyahkodan contoh analisis kod

Kaedah penyahkodan

Mesej yang mengandungi huruf A-Z dikodkan dengan pemetaan berikut:

• 'A' -> "1"

• 'B' -> "2"

• ...

• 'Z' -> 26"

Untuk menyahkod mesej yang dikodkan, semua nombor mesti dipetakan kembali kepada huruf berdasarkan kaedah yang dipetakan di atas (mungkin terdapat berbilang kaedah). Contohnya, "11106" boleh dipetakan kepada:

"AAJF" , mengumpulkan mesej sebagai (1 1 10 6)

"KJF" , mengumpulkan mesej sebagai (11 10 6)

Perhatikan bahawa mesej tidak boleh dikumpulkan sebagai (1 11 06) kerana "06" tidak boleh dipetakan kepada "F" kerana "6" dan "06" tidak bersamaan dalam pemetaan.

Memandangkan anda rentetan bukan kosong yang mengandungi nombor sahaja, sila kira dan pulangkan jumlah kaedah penyahkodan.

Data soalan menjamin bahawa jawapan mestilah integer 32-bit.

• Contoh 1:

Input: s = "12"

Output: 2

Penjelasan: Ia boleh dinyahkodkan sebagai "AB" (1 2) atau "L" (12).

• Contoh 2:

Input: s = "226"

Output: 3

Penjelasan: Ia boleh dinyahkodkan sebagai "BZ" (2 26), "VF" (22 6), atau "BBF" (2 2 6).

• Contoh 3:

Input: s = "0"

Output: 0

Penjelasan: Tiada aksara dipetakan ke nombor bermula dengan 0.

Pemetaan sah yang mengandungi 0 ialah 'J' ->

Memandangkan tiada aksara, tiada cara yang cekap untuk menyahkod ini kerana semua nombor perlu dipetakan.

Petua:

1 <= s.panjang <= 100

s mengandungi nombor sahaja dan mungkin mengandungi sifar pendahuluan.

Kaedah 1: Pengaturcaraan Dinamik (Java)

Untuk rentetan s tertentu, biarkan panjangnya n, dan aksara di dalamnya dari kiri ke kanan ialah s[1],s [2 ],...,s[n]. Kita boleh menggunakan pengaturcaraan dinamik untuk mengira bilangan kaedah penyahkodan untuk rentetan.

Secara khusus, biarkan fi mewakili bilangan kaedah penyahkodan bagi aksara i pertama s[1..i] rentetan s. Apabila melakukan pemindahan keadaan, kita boleh mempertimbangkan aksara dalam s yang digunakan untuk penyahkodan terakhir

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];
    }
}

Kerumitan masa: o(n)

Kerumitan ruang: o(n)

Kaedah 2: Pengaturcaraan dinamik - Pengoptimuman (go)

Sila lihat penerangan di atas untuk idea kaedah khusus Kaedah ini mengoptimumkan kerumitan ruang dengan menggunakan pembolehubah sementara daripada o(n) kepada 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
}

Kerumitan masa: o(n)

Kerumitan ruang: o(1)

Atas ialah kandungan terperinci Go Java kaedah penyahkodan contoh analisis kod. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!