JZ9 用两个栈实现队列
1 /* 模拟入队 */
2 public class JZ9_1
3 {
4 public static Stack<Integer> stack1 = new Stack<Integer>();
5 public static Stack<Integer> stack2 = new Stack<Integer>();
6
7 public static void push(int node)
8 {
9 if (stack1.isEmpty())
10 {
11 while (!stack2.isEmpty())
12 stack1.push(stack2.pop());
13 stack2.push(node);
14 while (!stack1.isEmpty())
15 stack2.push(stack1.pop());
16 }
17 }
18
19 public static int pop()
20 {
21 return stack2.pop();
22 }
23 }
24
25 /* ⭐模拟出队⭐ */
26 public class JZ9_2
27 {
28 public static Stack<Integer> stack1 = new Stack<Integer>();
29 public static Stack<Integer> stack2 = new Stack<Integer>();
30
31 public static void push(int node)
32 {
33 stack1.push(node);
34 }
35
36 public static int pop()
37 {
38 if (stack2.empty())
39 while (!stack1.empty())
40 stack2.push(stack1.pop());
41 return stack2.pop();
42 }
43 }
JZ30 包含min函数的栈⭐
1 /*
2 * stack: 正常保存每一个入栈的数字
3 * minStack: 当数字入栈后，保存栈当前状态最小的数
4 * */
5 public class JZ30_1
6 {
7 public static Stack<Integer> stack = new Stack<>();
8 public static Stack<Integer> minStack = new Stack<>();
9
10 public static void push(int node)
11 {
12 stack.push(node);
13 if (minStack.isEmpty() || node < minStack.peek())
14 minStack.push(node);
15 else
16 minStack.push(minStack.peek());
17 }
18
19 public static void pop()
20 {
21 stack.pop();
22 minStack.pop();
23 }
24
25 public static int top()
26 {
27 return stack.peek();
28 }
29
30 public static int min()
31 {
32 return minStack.peek();
33 }
34 }
35
36 /*
37 * stack: 正常保存每一个入栈的数字
38 * minStack: 最小元素每一次都进栈，造成重复，所以可以优化成只有当进栈元素≤目前最小元素时，进栈元素才放入最小栈
39 * */
40 public class JZ30_2
41 {
42 public static Stack<Integer> stack = new Stack<>();
43 public static Stack<Integer> minStack = new Stack<>();
44
45 public static void push(int node)
46 {
47 stack.push(node);
48 if (minStack.isEmpty() || node <= minStack.peek())
49 minStack.push(node);
50 }
51
52 public static void pop()
53 {
54 if (stack.peek() <= minStack.peek())
55 minStack.pop();
56 stack.pop();
57 }
58
59 public static int top()
60 {
61 return stack.peek();
62 }
63
64 public static int min()
65 {
66 return minStack.peek();
67 }
68 }
JZ31 栈的压入、弹出序列
1 /* 辅助栈 */
2 public class JZ31_1
3 {
4 public static boolean IsPopOrder(int[] pushV, int[] popV)
5 {
6 Stack<Integer> sta = new Stack<>();
7 int idx = 0;
8 for (int i = 0; i < popV.length; i++)
9 {
10 while (sta.isEmpty() || sta.peek() != popV[i])
11 {
12 if (idx == pushV.length) return false;
13 sta.push(pushV[idx++]);
14 }
15 sta.pop();
16 }
17 return sta.isEmpty();
18 }
19 }
20
21 /* ⭐原地栈⭐ */
22 public class JZ31_2
23 {
24 public static boolean IsPopOrder(int[] pushV, int[] popV)
25 {
26 int stackTop = -1, idx = 0;
27 for (int i = 0; i < pushV.length; i++)
28 {
29 pushV[++stackTop] = pushV[i];
30 while (stackTop >= 0 && pushV[stackTop] == popV[idx])
31 {
32 idx++;
33 stackTop--;
34 }
35 }
36 return idx == popV.length;
37 }
38 }
JZ73 翻转单词序列
1 /* 字符串翻转 */
2 public class JZ73_1
3 {
4 public static String ReverseSentence(String str)
5 {
6 StringBuilder res = new StringBuilder();
7 String[] s = str.split(" ");
8 for (int i = s.length - 1; i >= 0; i--)
9 res.append(s[i] + (i != 0 ? " " : ""));
10 return new String(res);
11 }
12 }
13
14 /* 滑动窗口 */
15 public class JZ73_2
16 {
17 public static String ReverseSentence(String str)
18 {
19 int left = 0, right = 0;
20 StringBuilder res = new StringBuilder();
21 StringBuilder rev_str = new StringBuilder(str).reverse();
22 while (true)
23 {
24 if (right == rev_str.length() || rev_str.charAt(right) == ' ')
25 {
26 res.append(new StringBuilder(rev_str.substring(left, right)).reverse());
27 left = right + 1;
28 if (right == rev_str.length())
29 break;
30 res.append(" ");
31 }
32 right++;
33 }
34 return res.toString();
35 }
36 }
37
38 /* 栈 */
39 public class JZ73_3
40 {
41 public static String ReverseSentence(String str)
42 {
43 Stack<String> sta = new Stack<String>();
44 StringBuilder res = new StringBuilder();
45 String[] temp = str.split(" ");
46 for (int i = 0; i < temp.length; i++)
47 sta.push(temp[i] + (i == 0 ? "" : " "));
48 while (!sta.isEmpty())
49 res.append(sta.pop());
50 return res.toString();
51 }
52 }
JZ59 滑动窗口的最大值⭐
1 /* 单调队列 */
2 public class JZ59_1
3 {
4 public static ArrayList<Integer> maxInWindows(int[] num, int size)
5 {
6 ArrayList<Integer> res = new ArrayList<>();
7 Deque<Integer> deque = new LinkedList<>();
8 if (size == 0) return res;
9 for (int i = 0; i < num.length; i++)
10 {
11 while (!deque.isEmpty() && num[deque.getLast()] < num[i])
12 deque.removeLast();
13 deque.addLast(i);
14 if (i - deque.getFirst() >= size) deque.removeFirst();
15 if (i >= size - 1) res.add(num[deque.getFirst()]);
16 }
17 return res;
18 }
19 }