Bagaimana untuk menggunakan algoritma Go Java untuk penyahkodan rentetan?

Penyahkodan Rentetan

Memandangkan rentetan yang dikodkan, kembalikan rentetan yang dinyahkodnya.

Peraturan pengekodan ialah: k[encoded_string], yang bermaksud bahawa encoded_string di dalam kurungan segi empat sama diulang k kali. Ambil perhatian bahawa k dijamin sebagai integer positif.

Anda boleh menganggap bahawa rentetan input sentiasa sah; tiada ruang tambahan dalam rentetan input dan kurungan segi empat sama input sentiasa memenuhi keperluan format.

Selain itu, anda boleh berfikir bahawa data asal tidak mengandungi nombor Semua nombor hanya mewakili bilangan ulangan k. Sebagai contoh, tidak akan ada input seperti 3a atau 2[4].

• Contoh 1:

Input: s = "3[a]2[bc]"

Output: "aaabcbc"

• Contoh 2:

Input: s = "3[a2[c]] "

Output: "accaccacc"

• Contoh 3:

Input: s = " 2[abc]3[cd]ef"

Output: "abcabccdcdcdef"

• Contoh 4:

Input: s = "abc3[cd]xyz"

Output: "abccdcdcdxyz"

Kaedah 1: Tindanan (Java)

Lihat Bila ia datang kepada padanan kurungan, perkara pertama yang perlu anda fikirkan ialah menggunakan tindanan untuk menyelesaikan masalah.

Pertama sekali, kerana nombor itu mungkin mempunyai lebih daripada satu digit, dua tindanan boleh digunakan untuk kejelasan dan kemudahan, satu untuk menyimpan nombor dan satu untuk menyimpan aksara. Apabila aksara selain daripada ] ditemui, ia mula-mula dimasukkan ke dalam timbunan aksara Apabila nombor ditemui, nombor lengkap ditukar dan dimasukkan ke dalam timbunan nombor Apabila ] ditemui, aksara sehingga [ muncul daripada timbunan aksara untuk membentuk rentetan sementara dan muncul keluar Elemen teratas tindanan nombor, ulang rentetan sementara beberapa kali dan kemudian masukkan semula ke dalam tindanan aksara.

Selepas melintasi rentetan asal dari kiri ke kanan, elemen dalam timbunan ialah jawapan muktamad

Idea kaedah khusus: Lintas timbunan ini

• Jika aksara semasa ialah digit, huraikan nombor (berbilang digit berturut-turut) dan tolakkannya pada tindanan

• Jika aksara semasa ialah huruf atau kurungan kiri, tolaknya ke atas timbunan secara langsung

• Jika aksara semasa ialah kurungan kanan, mulakan ia muncul dari timbunan sehingga kurungan kiri terpampang diterbalikkan dan disambungkan ke dalam rentetan kali ini, nombor di bahagian atas tindanan dikeluarkan, dan rentetan ini akan muncul beberapa kali, kami membina rentetan baharu berdasarkan nombor ini dan rentetan dan menolaknya ke dalam tindanan

class Solution {
    int ptr;
    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;
        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == &#39;[&#39;) {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }
        return getString(stk);
    }
    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }
    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}

Kerumitan masa: O(N)

Kerumitan ruang :O(N)

Kaedah 2: Rekursi (Go)

Kaedah yang dinyatakan di atas menggunakan timbunan, jadi kita kemudian boleh berfikir untuk menggunakan rekursi untuk menyelesaikannya. Untuk idea rekursif khusus, sila lihat di bawah.

Perlu menyelesaikan masalah bersarang antara berbilang kurungan. Iaitu, submasalah bertindih. Anda boleh menggunakan timbunan atau rekursi untuk menyelesaikan masalah.

• 1. Mula-mula kenal pasti kedudukan di mana kurungan kanan berakhir.

• 2 Apabila menghadapi kurungan kiri, i+1 diteruskan ke kali seterusnya

• 3 dan tetapkan bilangan produk kepada sifar , i=kedudukan di mana kurungan kanan terakhir disentuh. Teruskan menambah aksara yang tinggal di luar kurungan kanan.

Idea khusus: Parsing rentetan dari kiri ke kanan:

• Jika kedudukan semasa ialah digit, maka ia mesti termasuk kurungan segi empat sama selepas itu Ini adalah kes untuk rentetan yang diwakili oleh: k[...]:

• Kita boleh menghuraikan nombor dahulu, kemudian menghuraikan kurungan kiri, dan menghuraikan yang berikut secara rekursif Kandungan dikembalikan apabila kurungan kanan yang sepadan ditemui Pada masa ini, kita boleh membina rentetan X * s′

• Selepas kami menghuraikan k[...], kami memanggil fungsi rekursif sekali lagi untuk menghuraikan kandungan di sebelah kanan kurungan kanan

• Jika kedudukan semasa ialah bit huruf, kemudian kami menghuraikannya secara langsung Huruf semasa, dan kemudian menghuraikan kandungan secara rekursif selepas surat ini.

func decodeString(s string) string {
	var decode func(start int) (string, int)
	decode = func(start int) (str string, end int) {
		num:= 0
		for i := start; i < len(s); i++ {
			if isNumber(s[i]) {
				num = num*10 + int(s[i]-&#39;0&#39;)
			} else if isLetter(s[i]) {
				str += string(s[i])
			} else if s[i] == &#39;[&#39; {
				item, index := decode(i + 1)
				for num != 0 {
					str += item
					num--
				}
				i = index
			} else if s[i] == &#39;]&#39; {
				end = i
				break
			}
		}
		return str, end
	}
	res, _ := decode(0)
	return res
}
func isLetter(u uint8) bool {
	return u >= &#39;A&#39; && u <= &#39;Z&#39; || u >= &#39;a&#39; && u <= &#39;z&#39;
}
func isNumber(u uint8) bool {
	return u >= &#39;0&#39; && u <= &#39;9&#39;
}

Kerumitan masa: O(N)

Kerumitan ruang: O(N)

Atas ialah kandungan terperinci Bagaimana untuk menggunakan algoritma Go Java untuk penyahkodan rentetan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!