代码随想录算法训练营DAY11 | 栈与队列 (2)

一、LeetCode 20 有效的括号

题目链接：20.有效的括号https://leetcode.cn/problems/valid-parentheses/

思路：遇到左括号直接进栈；遇到右括号判断站顶是否有匹配的括号，没有就返回flase，有就将栈顶元素出栈；最后检测栈内是否有元素，栈空则说明匹配成功。

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i = 0; i < s.length(); i++){char c = s.charAt(i);if(c == '(' || c == '{' || c == '['){stack.push(c);continue;}else{if(stack.empty()){return false;}  }if(c == ')'){if(stack.peek() == '('){stack.pop();}else{return false;}}else if(c == ']'){if(stack.peek() == '['){stack.pop();}else{return false;}}else if(c == '}'){if(stack.peek() == '{'){stack.pop();}else{return false;}}} return stack.empty();}
}

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

题目链接：1047.删除字符串中的所有相邻重复项https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

思路：遍历字符串，当前元素与栈顶元素相同时，栈顶元素出栈；当前元素与栈顶元素不同或栈空时，元素入栈；最后将栈中元素逆序输出(本文使用StringBuilder类中的insert()方法)。

 

class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for(int i = 0; i < s.length(); i++){char c = s.charAt(i);if(stack.empty()){stack.push(c);}else{if(stack.peek() == c){stack.pop();}else{stack.push(c);}}}StringBuilder sb = new StringBuilder();while(!stack.empty()){sb.insert(0,stack.pop());}return sb.toString();}
}

三、LeetCode 150 逆波兰表达式求值

题目链接：150.逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/

思路：设置数字栈num_stack；遍历字符串数组，遇到数字时直接入栈；遇到符号时出栈两次，记为num1、num2，判断符号类型后进行对应操作得到结果res并压入栈中；最后返回栈内结果即为所求。

class Solution {public int evalRPN(String[] tokens) {//设置数字栈Stack<Integer> num_stack = new Stack<>();for(int i = 0; i < tokens.length; i++){int flag = judge(tokens[i]);if(flag == 0){//数字，直接入栈num_stack.push(Integer.valueOf(tokens[i]));}else{//符号，判断是什么符号，进行对应操作，得出的结果入栈int num1 = num_stack.pop();int num2 = num_stack.pop();int res = 0;if(tokens[i].equals("+")){res = num1 + num2;}else if(tokens[i].equals("-")){res = num2 - num1;}else if(tokens[i].equals("*")){res = num1 * num2;}else{res = num2 / num1;}num_stack.push(res);}}return num_stack.pop();}//judge函数用来判断字符串是数字public int judge(String s){if( s.equals("*") || s.equals("/") || s.equals("+") || s.equals("-")){return 1;}//数字，返回0return 0;}
}

四、今日小结

        提前完成算法学习任务，雪很大，出去溜达了一下，晚上也要努力学习呀~