网站可以做砍价软件吗,品牌网站制作简创网络,建设网站有哪些方法,站长之家怎么查询网站哪家做的目录
20. 有效的括号
1047. 删除字符串中的所有相邻重复项
150. 逆波兰表达式求值 20. 有效的括号
难度#xff1a;easy
类型#xff1a;栈与队列 思路#xff1a;
利用栈来做括号匹配#xff1b;
代码#xff1a;
class Solution {public boolean isValid(String…目录
20. 有效的括号
1047. 删除字符串中的所有相邻重复项
150. 逆波兰表达式求值 20. 有效的括号
难度easy
类型栈与队列 思路
利用栈来做括号匹配
代码
class Solution {public boolean isValid(String s) {DequeCharacter stack new ArrayDeque();for (int i 0; i s.length(); i) {char c s.charAt(i);if (c ( || c [ || c {) {// 将左括号入栈stack.push(c);} else if (!stack.isEmpty() stack.peek() leftOf(c)) {// 栈不为空并且右括号和栈顶元素匹配时栈顶元素出栈stack.pop();} else {// 当出现右括号并且栈为空时括号无效或者栈不为空右括号不匹配括号无效return false;}}return stack.isEmpty();}// 返回右括号对应的左括号public char leftOf(char c) {if (c )) {return (;} else if (c ]) {return [;} else if (c }) {return {;}return f;}
}
复杂度分析
时间复杂度: O(n)空间复杂度: O(n) 1047. 删除字符串中的所有相邻重复项
难度easy
类型栈与队列 思路 用栈来消去重复元素当新元素与栈顶元素相同时则pop反之则push需要注意的是将栈中的元素拼接成字符串时要注意元素顺序。
代码
class Solution {public String removeDuplicates(String s) {DequeCharacter stack new ArrayDeque(); for (int i 0; i s.length(); i) {char c s.charAt(i);if (stack.isEmpty() || c ! stack.peek()) {stack.push(c);} else if (c stack.peek()) {stack.pop();}}// 1.利用StringBuilder的insert方法// StringBuilder sb new StringBuilder();// while (!stack.isEmpty()) {// sb.insert(0, stack.pop());// }// return sb.toString();// 2.利用DequeString str ;while (!stack.isEmpty()) {str stack.pollLast();}return str;}
}
复杂度分析
时间复杂度: O(n)空间复杂度: O(n) 150. 逆波兰表达式求值
难度medium
类型栈与队列 思路 逆波兰表达式也叫后缀表达式后序遍历用它来处理算数表达式不需要考虑优先级 遇到数字则入栈遇到运算符则将两个元素出栈进行运算注意两个元素的出栈顺序和计算顺序例如除法运算中先出栈的元素为除数后出战的元素为被除数被除数/除数再将运算结果入栈。
代码
class Solution {public int evalRPN(String[] tokens) {DequeInteger stack new ArrayDeque();for (int i 0; i tokens.length; i) {// 字符串对比内容使用equals方法对比引用地址使用对象的赋值是改变引用if (tokens[i].equals()) {int a stack.pop();int b stack.pop();// b在前a在后因为栈是先进后出stack.push(b a);} else if (tokens[i].equals(-)) {int a stack.pop();int b stack.pop();stack.push(b - a);} else if (tokens[i].equals(*)) {int a stack.pop();int b stack.pop();stack.push(b * a);} else if (tokens[i].equals(/)) {int a stack.pop();int b stack.pop();stack.push(b / a);} else {stack.push(Integer.valueOf(tokens[i]));}}return stack.pop();}
}
复杂度分析
时间复杂度: O(n)空间复杂度: O(n)
