1.括号匹配

2.14
- 如果遇到右括号，直接进入判断头部是不是符合是否 pop，如果遇到左括号直接 push

class Solution {
    public boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        Deque<Character> stack = new LinkedList<>();
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                if(stack.isEmpty()||stack.peek()!=map.get(ch)){
                    return false;
                }
                stack.pop();
            }else{
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

1.31
- 怎么还跟之前的思路不一样了

class Solution {
    public boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
 
        Deque<Character> stack = new LinkedList<>();
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)&&map.get(ch)==stack.peek()){
                stack.pop();
            }else{
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

1.20
- 简单！！！！！
- 但是我这个思路不符合快速失败原则，如果都是左括号，空间复杂度就on 了，不过自己想的没毛病

class Solution {
    public boolean isValid(String s) {
        if(s.length()%2==1) return false;
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
 
        Deque<Character> stack = new LinkedList<>();
 
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(!map.containsKey(ch)||stack.peek()!=map.get(ch)){
                stack.push(ch);
            }else{
                stack.poll();
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
        
    }
}

api

11.18
- map初始化{{put(’)’,’(’)}}
- put存放时,右边为key,左边为val,在判断时,看取出的字符是不是待匹配(右边)的符号
  - 是的话:判断直接失败还是弹出匹配
  - 不是的话,直接存入

class Solution {
    public boolean isValid(String s) {
        if(s.length()%2==1){
            return false;
        }
        Map<Character,Character> pair = new HashMap<>(){
            {
                put(')','(');
                put('}','{');
                put(']','[');
            }
        };
        
        Deque<Character> stack = new LinkedList<>();
 
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(pair.containsKey(ch)){
                if(stack.isEmpty()||stack.peek()!=pair.get(ch)){
                    return false;
                }
                stack.pop();
            }else{
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

类型	写法	说明
数组	`a.length`	语言级属性，无方法
String	`s.length()`	对象方法
集合	`list.size()`	对象方法，惯例叫 size

只有数组是原生的,用length就行
Map类型的阔号对声明

Map<Character,Character> pairs = new HashMap<>() 
  {{put(')', '(');
    put(']', '[');
    put('}', '{');}};

栈的声明

Deque<Character> stack = new LinkedList<>();

取string中的字符串

	char ch = s.charAt(i);

判断map中是否存在一个key(contains加s)

pair.containsKey(key)

判断map是否存在某个value

pair.get(value)

pop()里不用放东西

Dx's Tech Notes

Explorer

1.括号匹配

Graph View

Backlinks