荣成网站建设,阿里云注销网站,遵义百度推广公司,做老师一些好的网站20. 有效的括号
题目详细#xff1a;LeetCode.20
由题可知#xff0c;有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
那么#xff0c;我们可以利用栈后进先出的特点#x…20. 有效的括号
题目详细LeetCode.20
由题可知有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
那么我们可以利用栈后进先出的特点
当遍历到左括号时将左括号字符依次进栈当遍历到右括号时将栈顶的左括号字符出栈 左括号如果与闭括号属于相同类型则为有效括号继续遍历下一个字符左括号如果与闭括号属于不同类型则为无效括号栈内剩余的左括号也无法以正确的顺序闭合返回false如果栈为空则说明不存在与之匹配的左括号返回false 当遍历完输入的字符串后注意需要判断栈是否为空进而来判断字符串内的括号是否已完全匹配
Java解法栈
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();for(char a: s.toCharArray()){if(a ( || a { || a [){stack.push(a);}else if(stack.isEmpty()){return false;}else{char b stack.pop();// 在ASCII码中左括号和右括号的差值 2// 所以这里直接用 Math.abs(a-b) 来判断左右括号是否匹配if(Math.abs(a-b) 2){return false;}}}return stack.isEmpty();}
}1047. 删除字符串中的所有相邻重复项
题目详细LeetCode.1047
这道题的实现方式不同但解决思路是殊途同归的都是利用栈后进先出的存储特点来解题
字符串中的字符依zg次进栈这样就保证了出栈的字符一定与下一个字符是相邻的那么只需要比较栈顶元素和即将进栈的元素是否重复 如果重复则弹出栈顶元素如果不重复则将遍历到字符进栈 最后只需要将栈内的字符重新组成字符串即为无重复项的字符串。
Java解法栈
class Solution {public String removeDuplicates(String s) {StackCharacter stack new Stack();for(char a : s.toCharArray()){if(stack.isEmpty()){stack.push(a);}else{char b stack.pop();if(a ! b){stack.push(b);stack.push(a);}}}StringBuffer sb new StringBuffer();while(!stack.isEmpty()){sb.insert(0, stack.pop());}return sb.toString();}
}无独有偶我们也可以用同样具备后进先出特点的双向队列来解决这道问题
Java解法双向队列
class Solution {public String removeDuplicates(String s) {DequeCharacter deque new LinkedList();for(char a : s.toCharArray()){if(deque.isEmpty()){deque.add(a);}else{char b deque.pollLast();if(a ! b){deque.add(b);deque.add(a);}}}StringBuffer sb new StringBuffer();while(!deque.isEmpty()){sb.append(deque.poll());}return sb.toString();}
}还有更为效率的方法就是将字符串转为字符数组后通过双指针来模拟栈进栈和压栈时栈顶指针的移动以及对重复字符的替换的过程来解决这一问题
Java解法双指针/模拟栈
class Solution {public String removeDuplicates(String s) {char[] ch s.toCharArray();int top 0;int next 0;while(next s.length()){ch[top] ch[next];if(top 0 ch[top] ch[top - 1]){top--;}else{top;}next;}return new String(ch,0,top);}
}150. 逆波兰表达式求值
题目详细LeetCode.150
波兰表达式其实就是将表达式用二叉树的形式表示后中序遍历二叉树得到的序列而逆波兰表达式就是后序遍历二叉树得到的序列。
观察逆波兰表达式的数组可以发现
利用栈先进后出的特点能够保证两个数值计算的前后顺序当遇到一个算术符号时则在栈中弹出最近的两个数将这两个数按照算术符号进行相应的术式计算出结果然后将计算结果再次压入栈中保证后续数值计算的前后顺序直到表达式遍历完栈中仅剩的计算结果即为最终结果
Java解法双指针/模拟栈
class Solution {public int evalRPN(String[] tokens) {DequeInteger deque new LinkedList();for(String t: tokens){if(t.equals() || t.equals(-) || t.equals(*) || t.equals(/)){int a 0, b 0, c 0;a deque.pollLast();b deque.pollLast();switch(t){case :c b a;break;case -:c b - a;break;case *:c b * a;break;case /:c b / a;break;}deque.add(c);}else{deque.add(Integer.parseInt(t));}}return deque.poll();}
}
