题目详细思路和解法来自于:代码随想录 (programmercarl.com)
LeetCode T20 有效的括号
题目思路
这道题分为三种情况
1.左括号多了 ([{}]()
2.括号不匹配 [{(]}]
3.右括号多了 []{}())))
处理思路:我们在遇到左括号的时候,直接入栈其对应的右括号即可,然后在遇到右括号的时候直接与栈顶元素比较,注意一点,如果在遇到右括号时栈为空,那么就是不符合题意的,如果栈顶元素还和目前右括号不同,也是错误的,但是如果相同我们就进行弹栈,遍历完字符串之后查看栈是否为空,为空则已经完成.
题目代码
class Solution { public boolean isValid(String s) { int len = s.length(); char[] chars = s.toCharArray(); Stack<Character> stack = new Stack<>(); for(int i = 0;i<len;i++) { if(chars[i] == '(') { stack.push(')'); } else if(chars[i] == '{') { stack.push('}'); } else if(chars[i] == '[') { stack.push(']'); } else if(stack.isEmpty() || stack.peek() != chars[i]) { return false; } else { stack.pop(); } } return stack.isEmpty(); } }
LeetCode T1047 删除字符串中所有相邻重复项
题目思路
使用栈结构,遍历该字符串,如果是空栈就进行压栈操作,如果不是空栈就用当前元素和栈顶元素进行比较,如果相同就进行弹栈操作,不同则继续压栈,遍历完将栈的元素放入字符串后进行一次反转字符串即可.(由于从栈冲取出元素顺序时反的)
优化:可以使用字符串来模拟栈的结构,可以节省栈来转字符串操作.
思路2:双指针
定义快慢指针,快指针负责遍历整个字符串,慢指针负责寻找不重复位置的结束位置,利用覆盖来保证原地修改而不用创建新的字符串,处理过程如下
1.while循环快指针到字符串末尾为结束条件,首先将快指针指向的元素赋给慢指针的元素
2.判断慢指针是否大于0,大于0则和前面的一个元素作比较,相等就回退,其实也是意义上消除了一对相同的字母
3.如果不相同就继续向前走,循环往复,最后从0到slow指针的位置形成的字符串就是题目所求
题目代码
//利用栈操作 class Solution { public String removeDuplicates(String s) { char[] chars = s.toCharArray(); Stack<Character> stack = new Stack<>(); for(int i = 0;i<s.length();i++) { if(stack.isEmpty()) { stack.push(chars[i]); } else if(chars[i] == stack.peek()) { stack.pop(); } else if(chars[i] != stack.peek()) { stack.push(chars[i]); } } StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { sb.append(stack.pop()); } return sb.reverse().toString(); } } //利用双指针写法 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 T150 逆波兰表达式求值
逆波兰表达式解释
是一种后缀表达式，所谓后缀就是指运算符写在后面,这样方便计算机的读取
比如我们平常使用的算式就是中缀表达式,需要考虑优先级
有人到这里还不理解,我们这里举个例子
中缀表达式 ( 1 + 2 ) * ( 3 + 4 )
转换为后缀表达式
( ( 1 2 + ) ( 3 4 + ) * )
优点:
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果.
- 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中.
- 本质:二叉树的中序遍历转换成了后序遍历
题目思路
这里我们遇到数字就直接入栈,遇到+-*/等操作符就从栈中取出两个元素做操作,然后重新入栈,依次往复,最后答案就在栈中.(注:本题不考虑异常情况,所有的逆波兰表达式均合法)
注:栈中取出元素的时候记得对减法和除法处理,因为减法和除法的两个操作数顺序与答案所求顺序相反.
题目代码
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); int num1,num2; 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("*")) { stack.push(stack.pop()*stack.pop()); } else if(s.equals("/")) { int tmp1 = stack.pop(); int tmp2 = stack.pop(); stack.push(tmp2/tmp1); } else { stack.push(Integer.valueOf(s)); } } return stack.pop(); } }
