发布于 2021-06-08  25 次阅读


今天来学习学习栈,应该是数据结构中比较简单的一种,依旧是通过几道力扣的经典有关栈的题来学习。

1. 有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

这道题可谓是前三经典的关于栈的题了。我们都知道栈的最大特性:先进后出。其实只要知道这个特性这题就不难。

class Solution{
   public boolean isValid(String s) {
int n = s.length();
       //如果字符串长度为奇数,就不可能是有效括号,直接返回false
      if(n % 2 == 1) return false;
       //将三种括号分别放到map中,至于为什么右括号为键左括号为值,等会遍历的时候就会比较明显
       Map<Character,Character> map = new HashMap<Character,Character>(){{
           put(')' , '(');
           put(']', '[');
           put('}', '{');
      }};
//new一个用链表实现的栈对象
       Deque<Character> stack = new LinkedList<Character>();
       //开始遍历字符串
       for(int i = 0;i < n;i++){
           char ch = s.charAt(i);
           //如果map的键中包含当前字符,也就意味着遍历到了右括号
           if(map.containsKey(ch)){
               //如果栈为空,也就是该右括号前没有其他字符,即无法闭合,返回false
               //或者 栈顶元素不等于该右括号所对应的左括号,也无法闭合,返回false
               if(stack.isEmpty() || stack.peek() != map.get(ch)){
                   return false;
              }
               //执行到这,说明右括号与栈顶的左括号匹配,那么弹栈,将左括号弹出
               stack.pop();
               //如果遍历到的是左括号,则压栈。也就是说我们的栈只用来存放左括号,
               //每遍历到一个右括号就与距其最近的左括号进行匹配,成功则弹栈,失败则返回false
          }else{
               stack.push(ch);
          }
      }
       //遍历结束后,如果栈为空,则说明所有括号匹配,否则则说明还有左括号未闭合,返回false
       return stack.isEmpty();
  }
}

2. 字符串解码

给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: 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"

这题一开始我一直在想用单栈解决,最后还是有个小bug,可能还是我太菜了,一起来学习学习这个辅助栈(双栈)解法。(建议自己debug走一遍,除非你肉眼debug能力很强)

class Solution{
    public String decodeString(String s){
        StringBuilder res= new StringBuilder();
            //记录数字
        int mutil = 0;
            //数字放在这个栈中
        Deque<Integer> stack_multi = new LinkedList<>();
            //每解析出一组就将其结果放入此栈中
        Deque<String> stack_res = new LinkedList<>();
        //遍历字符串
        for(Character c : s.toCharArray()){
            //如果遇到'[',因为'['前一定是数字,则multi一定有值
            if(c == '['){
                        //将multi压栈
                stack_multi.addLast(multi);
                        //将前一组解析结果压栈,如果这是第一个左括号,那么压入""
                stack_res.addLast(res.toString());
                        //由于前面已将其压栈,重置multi来记录之后的数字         
                multi = 0;
                        //同理,前面已将res压栈,重置res来记录之后的字符
                res = new StringBuilder();
                //如果遇到']'
            }else if(c == ']'){
                        //每次遇到‘]’都重新new一个临时对象tmp
                StringBuilder tmp = new StringBuilder();
               //取出数字栈的栈顶元素,即离该右括号左边最近的一个数字,代表该组元素的重复次数
                int cur_multi = stack_multi.removeLast(); 
                //遍历进行重复字符串的添加,此时的res是该右括号前的一组字符串,
                        //即res被该右括号及其左边最近的左括号包围
                for(int i = 0;i < cur_multi;i++){
                    tmp.append(res);
                }
                //复制结束后,将上一组的结果与本组的结果合并,即从字符串栈中取出栈顶字符串,    
                        //与本组结果字符串相加
                res = new StringBuilder(stack_res.removeLast() + tmp);
                        //如果遇到数字,将其赋给multi
            }else if(c >= '0' && c <= '9'){
                        //防止出现两位及以上的数字
                multi = multi*10 + Integer.parseInt(c + "");
                       //如果遇到字母,则直接在添加给res
            }else{
                res.append(c);
            }
        }
        return res.toString();
    }
}