day11 栈和队列 | 20,1047,150

LeetCode20  

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 每个右括号都有一个对应的相同类型的左括号。

* 使用栈的特征
* * 如果字符串为( => 栈中压入)
* * 如果字符串为[ => 栈中压入]
* * 如果字符串为{ => 栈中压入}

package algor.trainingcamp;import java.util.Stack;/*** @author lizhe* @version 1.0* @description: https://leetcode.cn/problems/valid-parentheses/* <p>* 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。* <p>* 有效字符串需满足：* <p>* 左括号必须用相同类型的右括号闭合。* 左括号必须以正确的顺序闭合。* 每个右括号都有一个对应的相同类型的左括号。* <p>* 来源：力扣（LeetCode）* 链接：https://leetcode.cn/problems/valid-parentheses* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。* @date 2023/4/15 17:12* <p>* 使用栈的特征* * 如果字符串为( => 栈中压入)* * 如果字符串为[ => 栈中压入]* * 如果字符串为{ => 栈中压入}* <p>* 最后 使用栈中压入的字符 和 字符串中的其他字符做对比*/public class LeetCode20 {public boolean isValid(String s) {char[] chars = s.toCharArray();Stack<Character> stack = new Stack<>();for (char c : chars) {if (c == '(') {stack.push(')');} else if (c == '[') {stack.push(']');} else if (c == '{') {stack.push('}');}else if(stack.isEmpty() || c != stack.pop()){return false;}}return stack.isEmpty();}public static void main(String[] args) {LeetCode20 demo = new LeetCode20();demo.isValid("()");}
}

LeetCode1047  删除字符串中的所有相邻重复项

* 比较栈顶元素 和 待入栈元素是否相同，如果相同直接出栈

package algor.trainingcamp;import java.util.Stack;/*** @author lizhe* @version 1.0* @description: . 删除字符串中的所有相邻重复项** https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/** 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。** 在 S 上反复执行重复项删除操作，直到无法继续删除。** 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。** 来源：力扣（LeetCode）* 链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。* @date 2023/4/15 17:37*/
public class LeetCode1047 {public String removeDuplicates(String s) {char[] chars = s.toCharArray();Stack<Character> stack = new Stack<>();for(char c : chars){if(!stack.isEmpty() && stack.peek() == c){stack.pop();}else{stack.push(c);}}int count = stack.size();char[] res = new char[count];while(!stack.isEmpty()){res[--count] = stack.pop();}return new String(res);}public static void main(String[] args) {LeetCode1047 demo = new LeetCode1047();demo.removeDuplicates("abbaca");}
}

LeetCode150 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

* 注意 除法 和 减法，除法 和 减法都是使用后出栈的值操作先出栈的值，其他都是正常顺序出栈操作

package algor.trainingcamp;import java.util.Stack;/*** @author lizhe* @version 1.0* @description:** 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。** 请你计算该表达式。返回一个表示表达式值的整数。* 注意：** 有效的算符为 '+'、'-'、'*' 和 '/' 。* 每个操作数（运算对象）都可以是一个整数或者另一个表达式。* 两个整数之间的除法总是 向零截断 。* 表达式中不含除零运算。* 输入是一个根据逆波兰表示法表示的算术表达式。* 答案及所有中间计算结果可以用 32 位 整数表示。*** 来源：力扣（LeetCode）* 链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。** @date 2023/4/15 17:50** 注: 除法 和 减法 假设ab先后入栈，是用后出栈的值 除以 或者 减去 先出栈的值*/
public class LeetCode150 {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String s : tokens){if(s.equals("+")){stack.push(stack.pop() + stack.pop());}else if(s.equals("*")){stack.push(stack.pop() * stack.pop());}else if(s.equals("/")){int num1 = stack.pop();int num2 = stack.pop();stack.push(num2 / num1);}else if(s.equals("-")){int num1 = stack.pop();int num2 = stack.pop();stack.push(num2 - num1);}else{stack.push(Integer.valueOf(s));}}return stack.pop();}public static void main(String[] args) {LeetCode150 demo = new LeetCode150();System.out.println(demo.evalRPN(new String[]{"2", "1", "+", "3", "*"}));}
}