中文网站建设合同,网站后台模板 jquery,怎样做信息收费网站,dede手机网站1.括号匹配问题 思路#xff1a;将左括号压入栈中#xff0c;遍历字符串#xff0c;当遇到右括号就出栈#xff0c;判断是否是匹配的一对#xff0c;不是就返回false#xff08;因为按照顺序所以当遇到右括号出栈一定要是匹配的#xff09;。使用Map来简化ifelse
clas…1.括号匹配问题 思路将左括号压入栈中遍历字符串当遇到右括号就出栈判断是否是匹配的一对不是就返回false因为按照顺序所以当遇到右括号出栈一定要是匹配的。使用Map来简化ifelse
class Solution {public boolean isValid(String s) {int len s.length();if(len%2 ! 0){return false;}MapCharacter,Character map new HashMap();map.put((,));map.put([,]);map.put({,});DequeCharacter stack new LinkedList();for(int i 0;ilen;i){char c s.charAt(i);if(map.containsKey(c)){stack.push(c);}else{if(stack.isEmpty() || c ! map.get(stack.pop())){return false;}}}return stack.isEmpty();}
} 2.最小栈 关键是使用辅助栈并且同步存取存的是最新的最小值如果最小值被弹出栈了因为同步的原因辅助栈中的最小值也将会消失。
class MinStack {DequeInteger min;DequeInteger stack;public MinStack() {stack new LinkedList();min new LinkedList();min.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);min.push(Math.min(val,min.peek()));}public void pop() {stack.pop();min.pop();}public int top() {return stack.peek();}public int getMin() {return min.peek();}
}
3.最大栈
设计一个最大栈数据结构支持查找最大元素
与最小栈一样不同的是需要实现popMax()将栈中最大元素弹出此处使用额外辅助栈将原栈中元素弹出放入辅助栈中待最大的元素找出弹出后再倒回去。注意的时两个栈同时存取
class MaxStack {StackInteger stack;StackInteger maxStack;public MaxStack() {stack new Stack();maxStack new Stack();}public void push(int x) {int max maxStack.isEmpty() ? x : maxStack.peek();maxStack.push(max x ? max : x);stack.push(x);}public int pop() {maxStack.pop();return stack.pop();}public int top() {return stack.peek();}public int peekMax() {return maxStack.peek();}public int popMax() {int max peekMax();StackInteger buffer new Stack();while (top() ! max) buffer.push(pop());pop();while (!buffer.isEmpty()) push(buffer.pop());return max;}public static void main(String[] args) {MaxStack stack new MaxStack();stack.push(2);stack.push(5);stack.push(1);System.out.println(stack.top());System.out.println(stack.popMax());System.out.println(stack.peekMax());}
}
