Bagaimana untuk melaksanakan urutan penampilan algoritma Go Java

Jujukan rupa

Diberi n integer positif, keluarkan item ke-n jujukan penampilan.

"Jujukan rupa" ialah jujukan integer, bermula dari nombor 1, dan setiap item dalam jujukan ialah perihalan item sebelumnya.

Anda boleh menganggapnya sebagai jujukan rentetan angka yang ditakrifkan oleh formula rekursif:

countAndSay(1) = "1"

countAndSay(n) ialah perihalan countAndSay(n-1), yang kemudiannya ditukar kepada rentetan angka yang lain.

Lima item pertama adalah seperti berikut:

• 1, 1 —— 🎜>

  2, 11 - Terangkan item sebelumnya, nombor ini ialah 1, iaitu "a 1", direkodkan sebagai "11"

• 3, 21 -Huraikan sebelumnya item item, nombor ini ialah 11, iaitu "dua 1s", direkodkan sebagai "21"

• 4, 1211 - Terangkan item sebelumnya, nombor ini ialah 21, iaitu "satu 2" + a 1", direkodkan sebagai "1211"

• 5, 111221 - Huraikan item sebelumnya, nombor ini ialah 1211, iaitu, "a 1 + a 2 + two 1s " , direkodkan sebagai "111221"

• Kaedah 1: Penjanaan traversal (Java)

Apa yang dipanggil "jujukan rupa" sebenarnya hanya mengira nombor yang sama berturut-turut dalam rentetan.

Jujukan rentetan berangka yang ditakrifkan oleh formula rekursif yang diberikan dalam soalan adalah seperti berikut:

countAndSay(1) = "1";

countAndSay(n ) ialah Perihalan countAndSay(n-1) dan kemudian ditukar kepada rentetan angka yang lain.

Kami mentakrifkan rentetan S_{i} untuk mewakili countAndSay(i) Jika kami memerlukan S_{n}, kami perlu mencari S_{n-1} dahulu, dan kemudian ikut penerangan di atas Penjanaan kaedah, iaitu, mengimbas bilangan maksimum aksara serupa berturut-turut dalam rentetan S_{n-1} dari kiri ke kanan, kemudian menukar nombor statistik aksara kepada rentetan berangka dan menggabungkan aksara yang sepadan.

N ialah integer positif yang diberikan, M ialah panjang maksimum dalam rentetan yang dijana

class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; ++i) {
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;
            while (pos < str.length()) {
                while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                    pos++;
                }
                sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }
        return str;
    }
}

Kerumitan masa: O (N * M)

Kerumitan Ruang: O (M)

Kaedah 2: Rekursi (Go)

Analisis kaedah khusus telah dinyatakan di atas

Memandangkan data yang diperolehi setiap kali adalah sumber Berdasarkan keputusan terakhir , kita boleh menganggap bahawa kita telah memperoleh keputusan terakhir dan kemudian meneruskan operasi. Ini menggunakan rekursi.

N ialah integer positif yang diberikan, M ialah panjang maksimum dalam rentetan yang dijana

func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    s := countAndSay(n - 1)
    i, res := 0, ""
    length := len(s)
    for j := 0; j < length; j++ {
        if s[j] != s[i] {
            res += strconv.Itoa(j-i) + string(s[i])
            i = j
        }
    }
    res += strconv.Itoa(length-i) + string(s[i])
    return res
}

Kerumitan masa: O (N * M)

Kerumitan Ruang: O (M)

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan urutan penampilan algoritma Go Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!