Dx's Tech Notes

3.字符串解码

6 min read

  • 2.14
    • 如果 第一个stack 选为 pop push，需要在最后结果返回时反转。所以推荐使用 addLast 和 removeLast
    • 判断数字和单词的 API 为 Character 的
    • 第四次做知道大体的思路了
class Solution {
    int cur=0;
    Deque<String> stack = new LinkedList<>();
    public String decodeString(String s) {
        while(cur!=s.length()){
            char ch = s.charAt(cur);
            if(Character.isDigit(ch)){
                String digits = getDigits(s);
                stack.push(digits);
            }else if(Character.isLetter(ch)||ch=='['){
                stack.push(String.valueOf(s.charAt(cur++)));
            }else{
                cur++;
                LinkedList<String> list = new LinkedList<>();
                while(!"[".equals(stack.peek())){
                    list.addLast(stack.pop());
                }
                Collections.reverse(list);
                stack.pop();
                StringBuffer sb = new StringBuffer();
                int times = Integer.valueOf(stack.pop());
                String string = getString(list);
                while(times-- >0){
                    sb.append(string);
                }
                stack.push(sb.toString());
            }
        }
        StringBuffer sb = new StringBuffer();
        while(!stack.isEmpty()){
            sb.append(stack.pollLast());
        }
        return sb.toString();
    }
    public String getDigits(String s){
        StringBuffer sb = new StringBuffer();
        while(Character.isDigit(s.charAt(cur))){
            sb.append(s.charAt(cur++));
        }
        return sb.toString();
    }
    public String getString(Deque<String> stack){
        StringBuffer sb = new StringBuffer();
        for(String s:stack){
            sb.append(s);
        }
        return sb.toString();
    }
}
class Solution {
    public String decodeString(String s) {
        int cur=0;
        Deque<Character> stack = new LinkedList<>();
        while(cur!=s.length()){
            char ch = s.charAt(cur);
            if(ch.isDigit()){
                String digits = getDigits(ch);
                stack.push(digits.toCharArray());
            }else if(ch.isLetter()||ch=='['){
                stack.push(ch);
            }else{
                stack.pop();
                LinkedList<Character> list = new LinkedList<>();
                while(stack.peek()!='['){
                    list.addLast(stack.pop());
                }
                Collections.reverse(list);
                StringBuffer sb = new StringBuffer();
                int o = Integer.valueOf(stack.pop());
                String l = getString(stack.pop());
                while(o--){
                    sb.append(l);
                }
            }
            return stack.toString();
        }
    }
}
  • 2.1
    • 判断是否是数字或者字母是 Character 内的方法，取数字用 Integer 的方法
    • 用 tempStack 暂存 string 字符，并记得返回去
    • getDigit 内指针会移动
    • getString for 取出栈中的 string

“用一个栈从左到右扫描：数字入栈、字母和 [ 入栈；遇到 ] 时弹出到最近的 [，得到子串，再取出前面的重复次数，重复拼接后入栈。最后把栈中所有片段拼起来就是答案。时间空间都是 O(n)。”

  • 11.18

    • 上面说的没错
    • Character有判断数字和字母的api
    • 判断是数字,用自创函数取出完整数字放入总resStack
    • 如果是字母或左括号,string化后放入总resStack
    • 最后如果是右括号,匹配完成
      • 弹出到左括号到新LinkedList,反转后,在弹出数字
      • LinkedList里用自创函数得到完整String,然后数字×Stirng存入resStack
    • 自创函数处理resStack

  • 11.21

    • 取数字时,传进去的是整个字符(ptr是全局变量)
    • 取字母时,就地addlast(valueOf)
    • 需要一个getString的方法来处理栈中零散的String
    • !"[".equals(stk.peekLast())这里是String的比较所以是双引号
class Solution {
    int ptr;
    public String decodeString(String s) {
        Deque<String> stk = new LinkedList<>();
        ptr = 0;
		//1.注意ptr拼写
        while(ptr<s.length()){
            char ch = s.charAt(ptr);
            //2.Character.isDigir()的API
            if(Character.isDigit(ch)){
            //3.getDigits:取出完整的数字而不是单个数字
                String digits = getDigits(s);
                stk.addLast(digits);
                //4.Character.isLetter()API
            }else if(Character.isLetter(ch)||ch=='['){
            //5.String.valueOf()API
                stk.addLast(String.valueOf(s.charAt(ptr++)));
            }else{//匹配到了]?
            //6.ptr只是一个全局游标指针,告诉前面已经处理了
                ptr++;
                LinkedList<String> sub = new LinkedList<>();
                while(!"[".equals(stk.peekLast())){
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                stk.removeLast();
                //7.转换为Int的Integer.parseInt()API
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer sb = new StringBuffer();
                String o = getString(sub);
                while(repTime-- >0){
                    sb.append(o);
                }
                stk.addLast(sb.toString());
            }
            
        }
        return getString(stk);
    }
 
    public String getDigits(String s){
        StringBuffer sb = new StringBuffer();
        while(Character.isDigit(s.charAt(ptr))){
            sb.append(s.charAt(ptr++));
        }
        return sb.toString();
    }
    public String getString(Deque<String> stk){
        StringBuffer sb = new StringBuffer();
        for(String s:stk){
            sb.append(s);
        }
        return sb.toString();
    }
}

用到的 Java API 清单

字符/字符串处理 • s.charAt(ptr)：读取当前位置字符 • s.length()：边界判断 • Character.isDigit(ch)：判断是否数字 • Character.isLetter(ch)：判断是否字母 • String.valueOf(ch)：把 char 转为 String • （推荐）StringBuilder / （你代码里）StringBuffer：高效拼接字符串 • append(…)、toString()

1.	从左到右扫描字符串，用一个栈暂存“数字 / 左括号 / 普通字母 / 已展开片段”。
2.	遇到：
•	数字：把连续的数字读完（可能多位），入栈。
•	字母或**[**：直接入栈。
•	]：开始出栈还原最近一段：
•	弹出直到遇到"["的所有字符串，拼成一个子串 o（注意顺序）。
•	弹出左括号 "["。
•	再弹出其前面的重复次数 repTime。
•	构造 repTime 次 o 的重复，压回栈。
3.	扫描结束后，把栈里剩余内容按顺序拼接就是结果。

关键点 • 多位数：12[a] 必须一次性读成 “12”；不能只取当前字符。 • 顺序：从栈里往外弹出的子串是逆序的，记得反转或用 addFirst 还原。 • 指针移动：读到 ] 时需要 ptr++ 跳过它，继续往右走。 • 时间复杂度：O(n)；空间复杂度：O(n)（栈存中间结果）。

Deque stk = new LinkedList<>(); • addLast(x)：当作“压栈” • removeLast()：当作“弹栈” • peekLast()：看栈顶 反转与容器 • Collections.reverse(List<?> list)：反转列表（参数必须是 List，如 LinkedList） • 如果用 Deque 暂存子串，可改成 addFirst 避免反转。

Graph View

Backlinks