题目详细思路和解法来自于:代码随想录 (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();}
}
