文字列のデコードに Go Java アルゴリズムを使用するにはどうすればよいですか?
- WBOY転載
- 2023-04-25 23:52:061239ブラウズ
文字列のデコード
エンコードされた文字列を指定すると、そのデコードされた文字列を返します。
エンコード ルールは、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 == '[') {
// 获取一个字母并进栈
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′## を構築できます。 #k[...] を解析した後、再帰関数を再度呼び出して、右括弧の右側の内容を解析します。
- 現在の位置が文字ビット、その後、現在の文字を直接解析し、この文字の後の内容を再帰的に解析します。
-
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]-'0') } else if isLetter(s[i]) { str += string(s[i]) } else if s[i] == '[' { item, index := decode(i + 1) for num != 0 { str += item num-- } i = index } else if s[i] == ']' { end = i break } } return str, end } res, _ := decode(0) return res } func isLetter(u uint8) bool { return u >= 'A' && u <= 'Z' || u >= 'a' && u <= 'z' } func isNumber(u uint8) bool { return u >= '0' && u <= '9' }時間計算量: O(N)
空間計算量: O(N)
以上が文字列のデコードに Go Java アルゴリズムを使用するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。