代码随想录算法训练营day11 | leetcode 20. 有效的括号 1047. 删除字符串中的所有相邻重复项 150. 逆波兰表达式求值

基础知识

String StringBuilder 操作

public class StringOperation {
        int startIndex;
        int endIndex;
    {
        //初始容量为16个字符 主要做增删查改 索引包头不包尾
        StringBuilder sb = new StringBuilder();

        sb.append("str");
        // 把原来index上的元素挪到新添加的元素位置后
        sb.insert(1, "str");

        sb.deleteCharAt(1);
        sb.delete(1, 2);

        sb.length();
        sb.capacity();
        sb.charAt(1);
        // 找不到返回-1
        sb.indexOf("char");
        sb.indexOf("char", 1);
        sb.lastIndexOf("str");
        sb.lastIndexOf("str", 1);
        sb.substring(1);
        sb.substring(1,3);

        sb.setCharAt(1,'c');
        sb.reverse(); // String是final的，肯定没有reverse方法
        sb.replace(1, 2, "str");
        sb.toString();

    }

    {
        // 做替换、大小写变换、分割、清除空格、字符数组互换
        String str= new String();
        String string= new String();

        str.trim();
        str.toLowerCase();
        str.toUpperCase();
        str.compareTo(string);
        str.split(" ");
        str.replace("old", "new");
        str.replaceAll("%d","123");
        str.substring(startIndex,endIndex);
        str.substring(1);

        List<Character> list = str.chars().mapToObj(c -> (char) c).collect(Collectors.toList());
        str.chars().mapToObj(c -> (char) c).forEach(System.out::println);
        Collections.frequency(list, 'a');

        // 对字符串升序排列
        char[] ar = str.toCharArray();
        Arrays.sort(ar);
        String str11 = String.valueOf(ar);

    }
}

LeetCode 20. 有效的括号

分析1.0

三种括号，22匹配，遇到左括号入栈，遇到右括号出栈

class Solution {
    public boolean isValid(String s) {
        HashMap map = new HashMap();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        ArrayDeque<Character> stack = new ArrayDeque();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i)==('(') || s.charAt(i)==('{') || s.charAt(i)==('[')){
                stack.push(s.charAt(i));
            }else if(s.charAt(i)==(')') || s.charAt(i)==('}') || s.charAt(i)==(']')){
                if(stack.isEmpty()){
                    return false;
                }else{
                    if(map.get(s.charAt(i)).equals(stack.pop())){
                        continue;
                    }else{
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty() ? true : false;
    }
}

失误

Map、Stack这种容器里存放的都是封装类，比较相等时要使用equals，基本数据类型的比较使用==

return stack.isEmpty() ? true : false; 直接返回stack.isEmpty()就行

LeetCode 1047. 删除字符串中的所有相邻重复项

分析1.0

删除相邻重复项，删除之后索引总长度会改变

失误

我的思路是想再原来的String上操作，但这样是错误的，最后的结果应该是在Stack里头

class Solution {
    public String removeDuplicates(String s) {
        if(s == null || s.length() < 2){
            return s;
        }
        //StringBuilder sb = new StringBuilder(s);
        ArrayDeque<Character> stack = new ArrayDeque();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(stack.isEmpty()){
                stack.push(ch);
                continue;
            }         
            if(ch == stack.peek()){
                stack.pop();
                //sb.deleteCharAt(i); // delete后sb长度改变
            }else{
                stack.push(ch);
            }
        }
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()){
            res.append(stack.pop());
        }
        return res.reverse().toString();
    }
}

这种拼接还挺有意思的 省了reverse

while (!deque.isEmpty()) {
     str = deque.pop() + str;
}

LeetCode 150. 逆波兰表达式求值

分析1.0

逆波兰表达式（后缀表达式）主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

思路

① 如何识别算符和数字 ② 延伸 0-9的ascll字符如何比较大小、实现 char 与 int 转换（这种时候可以打印日志 | 判断元素类型）③ 单个字符如何实现String 与 char 转换 charAt() toCharArray()

失误

// char ch = tokens[i].charAt(0); 两位数就完犊子了 数字字符可能有多位，而算符只能是一位

分析2.0

class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque<Integer> stack = new ArrayDeque();
        for(int i = 0; i < tokens.length; i++){
            // char ch = tokens[i].charAt(0); 两位数就完犊子了
            String str = tokens[i];
            if(str.equals("+")){
                stack.push(stack.pop() + stack.pop());
            }else if(str.equals("-")){
                stack.push(0 - stack.pop() + stack.pop());
            }else if(str.equals("*")){
                stack.push(stack.pop() * stack.pop());
            }else if(str.equals("/")){
                int a = stack.pop();
                stack.push(stack.pop() / a);
            }else{
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }
}

总结

1. Map、Stack这种容器里存放的都是封装类，比较相等时要使用equals，基本数据类型的比较使用==
2. 22成对出现且涉及查找等相关操作时，注意使用Map或栈
3. 匹配问题——栈、Map
4. 栈能保存上一个访问过的元素
5. String.charAt(i)是一个char 不是一个String
6. char ch = tokens[i].charAt(0); 两位数就完犊子了 数字字符可能有多位，而算符只能是一位
7. ASCLL 字符阿拉伯数组的int值 int val = '9' - '0'
8. Integer.parseInt(s)是把字符串解析成int基本类型，Integer.valueOf(s)是把字符串解析成Integer对象类型。jdk规定，每次要创建一个value值在-128~127之间的Integer对象时，直接从缓存中拿到这个对象，所以value值相同的Integer对象都是对应缓存中同一个对象。-128~127之外的整数值用的不是太频繁，每次创建value值相同的Integer对象时，都是重新创建一个对象

常用变量名增量更新

size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch