wordpress主题vue景德镇seo
(1) 用两个栈实现队列
链接
很简单，如果有元素进入队列，则将其进入stack1。如果要出队列，那么就需要判断stack2的情况。人与法国stack2为空，则直接把stack1的元素全放进stack2（相当于顺序反过来），然后再出栈。如果不为空，则先出stack2的内容。
import java.util.*;
import java.util.Stack;public class Solution {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {stack1.add(node);}public int pop() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.add(stack1.pop());}}return stack2.pop();}
}（2）包含min函数的栈
链接
pop和push的操作很简单，重点是在于min操作。如果直接设置一个min变量，确实可以记录最小值。但如果最小值出栈了，那么min就很难再修改。因此只有一个min是无法工作的，需要一个栈来同时记录，记录的内容为【当前元素入栈时的最小值】
例如，如：-2， 1， 3
stack1：-2 1 3
stack2：-2 -2 -2
如果-3入栈：
stack1：-2 1 3 -3
stack2：-2 -2 -2 -3
此时就可以得到当前的最小值。如果-3出栈，stack2的也进行pop操作，最小值也能被记录。时间复杂度是O(1)。
import java.util.*;
import java.util.Stack;public class Solution {Stack<Integer> s1=new Stack<>();Stack<Integer> s2=new Stack<>();int min=10001;public void push(int node) {s1.add(node);if(node<min){s2.add(node);min=node;}else{s2.add(min);}}public void pop() {s1.pop();s2.pop();min=s2.peek();}public int top() {return s1.peek();}public int min() {return s2.peek();}
}（3）有效括号序列
链接
即用栈来存储字符串的内容，并且进行判断。如果匹配则出栈，否则不用出栈，最后判断栈是否为空。这样的做法是正确的，不过仍可以优化，因为可能出现（] 这样的情况，其实可以直接退出循环。不过这样写很简洁。
public boolean isValid (String s) {// write code hereStack<Character> stack=new Stack<>();for(char ch: s.toCharArray()){if(stack.isEmpty()){stack.push(ch);}else{if(ch==')'&&stack.peek()=='(' || ch==']'&&stack.peek()=='[' ||ch=='}'&&stack.peek()=='{'){stack.pop();}else{stack.push(ch);}}}return stack.isEmpty();}
我们可以优化一下，写得更复杂，或者用hash来存储映射关系。
public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char ch : s.toCharArray()) {if (ch == '(' || ch == '[' || ch == '{') {stack.push(ch);} else if (ch == ')' && !stack.isEmpty() && stack.peek() == '(') {stack.pop();} else if (ch == ']' && !stack.isEmpty() && stack.peek() == '[') {stack.pop();} else if (ch == '}' && !stack.isEmpty() && stack.peek() == '{') {stack.pop();} else {return false;}}return stack.isEmpty();
}
// 或者这样
public boolean isValid(String s) {// 创建一个HashMap来存储括号的匹配关系Map<Character, Character> map = new HashMap<>();map.put(')', '(');map.put(']', '[');map.put('}', '{');// 创建一个栈Stack<Character> stack = new Stack<>();// 遍历字符串的每个字符for (char ch : s.toCharArray()) {// 如果字符是右括号if (map.containsKey(ch)) {// 弹出栈顶元素，如果栈为空则赋值为一个虚拟字符char topElement = stack.isEmpty() ? '#' : stack.pop();// 检查栈顶元素是否与当前字符的匹配字符相同if (topElement != map.get(ch)) {return false;}} else {// 如果字符是左括号，压入栈中stack.push(ch);}}// 如果栈为空，说明所有括号匹配return stack.isEmpty();
}
（4） 滑动窗口的最大值
链接
这题的做法其实比较固定，如果不暴力做就需要使用双端队列。
我们的队列元素大小总是非递增的，这样就可以很轻松的获取最大值。同时还要注意窗口内的元素达到3的情况。
假设数组是 [2, 3, 4, 2, 6, 2, 5, 1]，窗口大小是 3。
- 初始化双端队列为空，结果列表为空。
- 遍历数组：
- 第一个元素
2：双端队列变为[2]。 - 第二个元素
3：移除2，双端队列变为[3]。 - 第三个元素
4：移除3，双端队列变为[4]。窗口达到大小3，最大值为4。 - 第四个元素
2：双端队列变为[4, 2]。最大值仍为4。 - 第五个元素
6：移除4和2，双端队列变为[6]。最大值为6。 - 第六个元素
2：双端队列变为[6, 2]。最大值仍为6。 - 第七个元素
5：移除2，双端队列变为[6, 5]。最大值仍为6。 - 第八个元素
1：双端队列变为[6, 5, 1]。最大值为6。
- 第一个元素
最终结果列表为 [4, 4, 6, 6, 6, 5]。
public ArrayList<Integer> maxInWindows(int[] num, int size) {ArrayList<Integer> res = new ArrayList<>();if (num == null || size <= 0 || num.length < size) {return res;}Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < num.length; i++) {// 移除不在滑动窗口范围内的元素if (i >= size && !deque.isEmpty() && deque.peekFirst() == num[i - size]) {deque.pollFirst();}// 移除所有小于当前元素的元素while (!deque.isEmpty() && deque.peekLast() < num[i]) {deque.pollLast();}// 添加当前元素deque.offerLast(num[i]);// 当窗口大小达到要求时，记录当前窗口的最大值if (i >= size - 1) {res.add(deque.peekFirst());}}return res;}
（4）最小的K个数
链接
最好想的就是直接排序再切片。
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {// write code hereArrays.sort(input);ArrayList<Integer> result = new ArrayList<>();for (int i = 0; i < k; i++) {result.add(input[i]);}return result;}