【算法刷题day11】Leetcode:20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

本文主要是介绍【算法刷题day11】Leetcode:20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

草稿图网站
java的Deque

Leetcode 20. 有效的括号

题目：20. 有效的括号
解析：代码随想录解析

解题思路

遍历一轮，如果空了则返回true，否则返回false

代码

class Solution {private Stack<Character> stack;private void initialStack(){stack = new Stack<>();}private boolean j(char c){if (c == '(' || c == '[' || c =='{')return true;elsereturn false;}private boolean judge(char c){if (stack.isEmpty())return false;char cStack = stack.peek();if (c == ')' && cStack == '(')return true;if (c == '}' && cStack == '{')return true;if (c == ']' && cStack == '[')return true;return false;} public boolean isValid(String s) {initialStack();int i = 0;while (i < s.length()){char c = s.charAt(i);if (j(c)){stack.push(c);i++;}else{if (judge(c)){stack.pop();i++;}else{return false;}}}return stack.isEmpty();}
}

总结

写的一坨狗屎，多学学carl哥的思路

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 == '(')stack.push(')');else if (c == '[')stack.push(']');else if (c == '{')stack.push('}');else if (!stack.isEmpty() && c == stack.peek())stack.pop();elsereturn false;}return stack.isEmpty();}
}

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

题目：1047. 删除字符串中的所有相邻重复项
解析：代码随想录解析

解题思路

使用栈来消除相同的字符。

代码

class Solution {public String removeDuplicates(String s) {ArrayDeque<Character> deque = new ArrayDeque<>();for (int i = 0; i < s.length(); i++){char c = s.charAt(i);if (!deque.isEmpty() && c == deque.peek())deque.pop();elsedeque.push(c);}String res = "";while (!deque.isEmpty())res = deque.pop() + res;return res;}
}

总结

利用stack效率有点低，直接用StringBuffer当作stack可以从136ms提升到23ms

class Solution {public String removeDuplicates(String s) {StringBuffer res = new StringBuffer();int top = -1;for (int i = 0; i < s.length(); i++){char c = s.charAt(i);if (top >= 0 && c == res.charAt(top))res.deleteCharAt(top--);else{res.append(c);top++;}}return res.toString();}
}

双指针能优化到4ms。（快指针负责遍历，慢指针代表最后输出的结果，如果有重复就回退。然后让遍历的快指针覆盖慢指针。）

class Solution {public String removeDuplicates(String s) {char[] ch = s.toCharArray();int fast = 0;int slow = 0;while(fast < s.length()){// 直接用fast指针覆盖slow指针的值ch[slow] = ch[fast];// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了if(slow > 0 && ch[slow] == ch[slow - 1]){slow--;}else{slow++;}fast++;}return new String(ch,0,slow);}
}

Leetcode 150. 逆波兰表达式求值

题目：150. 逆波兰表达式求值
解析：代码随想录解析

解题思路

利用栈

代码

class Solution {Stack<Integer> stack;private void cal(String op){int num2 = stack.pop();int num1 = stack.pop();if (op.equals("+"))stack.push(num1 + num2);else if (op.equals("-"))stack.push(num1 - num2);else if (op.equals("*"))stack.push(num1 * num2);else if (op.equals("/"))stack.push(num1 / num2);}public int evalRPN(String[] tokens) {stack = new Stack<>();for(int i = 0; i < tokens.length; i++){String s = tokens[i];try{stack.push(Integer.parseInt(s));}catch (Exception e) {cal(tokens[i]);}}return stack.peek();}
}

总结

需要优化

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String s : tokens){if ("+".equals(s))stack.push(stack.pop() + stack.pop());else if ("-".equals(s)){stack.push(-stack.pop() + stack.pop());}else if ("*".equals(s))stack.push(stack.pop() * stack.pop());else if ("/".equals(s)){int num2 = stack.pop();int num1 = stack.pop();stack.push(num1 / num2);}else{stack.push(Integer.parseInt(s));}}return stack.pop();}
}

相同的处理逻辑，减少不必要的函数，提高了速度

这篇关于【算法刷题day11】Leetcode:20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---