文字列のデコードに Go Java アルゴリズムを使用するにはどうすればよいですか?-＆＃＆チュートリアル-php.cn

文字列のデコードに Go Java アルゴリズムを使用するにはどうすればよいですか?

WBOY

リリース： 2023-04-25 23:52:06

転載

1257 人が閲覧しました

文字列のデコード

エンコードされた文字列を指定すると、そのデコードされた文字列を返します。

エンコードルールは、k[encoded_string] です。これは、角括弧内の encoded_string が k 回繰り返されることを意味します。 k は正の整数であることが保証されていることに注意してください。

入力文字列は常に有効であると想定できます。入力文字列には余分なスペースはなく、入力角括弧は常に形式要件を満たしています。

また、元のデータには数字が含まれていないと考えることができます。すべての数字は繰り返し回数 k を表すだけです。たとえば、3a や 2[4] などの入力はありません。

例 1:

入力: s = "3[a]2[bc]"

出力: "aaabcbc"

例 2:

入力: s = "3[a2[c]] "

出力:"accaccacc"

例 3:

入力: s = " 2[abc]3[cd]ef"

出力: "abcabccdcdcdef"

例 4:

入力: s = "abc3[cd]xyz"

出力: "abccdcdcdxyz"

方法 1: スタック (Java)

参照時期ブラケットのマッチングに関して言えば、最初に考えるべきことは、問題を解決するためにスタックを使用することです。

まず第一に、数値には複数の桁が含まれる可能性があるため、わかりやすく便利にするために 2 つのスタックを使用できます。1 つは数値を格納し、もう 1 つは文字を格納します。 ] 以外の文字が見つかった場合は、最初に文字スタックに入れられます。数字が見つかった場合は、完全な数字が変換されて番号スタックに入れられます。] 以外の文字が見つかった場合、[ までの文字が文字スタックから飛び出します。数値スタックの最上位要素は、一時文字列をその回数繰り返してから文字スタックに戻します。

元の文字列が左から右にトラバースされると、スタック内の要素が最終的な答えになります

具体的な方法のアイデア: スタックをトラバースする

現在の文字が数字の場合は、数値 (連続する複数の数字) を解析してスタックにプッシュします。
現在の文字が文字または左括弧の場合は、それをプッシュしますスタックに直接
現在の文字が右括弧の場合、左括弧がポップされるまでスタックからポップし始めます。ポップシーケンスは反転され、文字列に結合されます。このとき、スタックの一番上の数字が取り出され、この文字列が現れるはずですが、この数字と文字列を元に新しい文字列を構築し、スタックにプッシュします

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();
    }
}

ログイン後にコピー

時間計算量: O(N)

空間計算量: O (N)

方法 2: 再帰 (Go)

上記の方法では、スタックなので、再帰を使用してそれを完了することを考えることができます。再帰的な具体的なアイデアについては、以下を参照してください。

複数の括弧間の入れ子の問題を解決する必要があります。つまり、部分問題が重なっているということです。スタックまたは再帰を使用して問題を解決できます。

1. まず、右括弧が終了する位置を特定します。
2. 左括弧に遭遇した場合、i 1 が次回に渡されます
3. 左括弧の操作を終了しますそして製品の数をゼロに設定します。i=右ブラケットが最後に接触した位置。右括弧の外側に残りの文字を追加し続けます。

具体的なアイデア: 文字列を左から右に解析します:

現在の位置が数字の場合、角括弧が含まれている必要があります。これは、k[...]:
で表される文字列の場合です。最初に数値を解析し、次に左括弧を解析し、次のコンテンツを再帰的に解析します。 , 対応する右括弧に遭遇すると返されます。この時点で、解析された数値 x と括弧内の解析された文字列 s' に基づいて、新しい文字列 X * s′
## を構築できます。

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

ログイン後にコピー

時間計算量: O(N)

空間計算量: O(N)

以上が文字列のデコードに Go Java アルゴリズムを使用するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。