Catalogue of series articles
I Array type problem solving method 1: dichotomy
II Array type problem solving method 2: Double finger needle method
III Array type problem solving method 3: sliding window
IV Array type problem solving method 4: simulation
V The basic operation and classic topics of the linked list
Vi Classic title of hash table
VII Classic title of string
VIII KMP of string
IX Solution: double pointer
preface
The question brushing route comes from: Code Capriccio
Simple use of stacks and queues
Stack: first in, last out
// Stack Stack<Integer> stack = new Stack<>(); // Push stack.push(1); // Return stack element stack.add(2); // Return boolean type // Stack out, return element stack.pop(); // Return stack top element stack.peek();
Queue: first in first out
// queue Queue<Integer> queue = new LinkedList<>(); // Queue queue.offer(1); // Return boolean type queue.add(2); // Return boolean type // Out of queue, return out of queue element queue.poll(); // Return queue header element queue.peek();
Double ended queue: the double ended queue can return the elements of the head and tail of the queue, and both ends can be out of the queue and in the queue
// Double ended queue Deque<Integer> deque = new ArrayDeque<>(); Deque<Integer> deque1 = new LinkedList<>(); // Enter the queue and return boolean type deque.addFirst(1); // Head insert deque.addLast(1); // Tail entry // Out of queue deque.pollFirst(); // Team leader deque.pollLast(); // Team tail // Returns the header and footer elements deque.peekFirst(); // Team leader deque.peekLast(); // Team tail
Priority queue (heap): the default is small root heap (the queue head is the largest or smallest element, which will be adjusted when joining the queue)
// Priority queue
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// The method is the same as that of Queue
...
// Creation of piles
PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new Comparator<Integer>(){
@Override
public int compare(Integer o1,Integer o2){
return o2-o1;
}
});
Inscription
232. Implement queue with stack
Leetcode link
Please use only two stacks to implement the first in first out queue. The queue should support all operations supported by the general queue (push, pop, peek, empty):
Implement MyQueue class:
void push(int x) pushes element X to the end of the queue
int pop() removes the element from the beginning of the queue and returns it
int peek() returns the element at the beginning of the queue
boolean empty() returns true if the queue is empty; Otherwise, false is returned
explain:
You can only use standard stack operations -- that is, only push to top, peek/pop from top, size, and is empty operations are legal.
Your language may not support stacks. You can use list or deque (double ended queue) to simulate a stack, as long as it is a standard stack operation.
Example 1:
Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 1, 1, false]
Explanation:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Solution:
The queue is first in first out, while the stack is first in first out, so the stack is used to simulate the queue. When the simulated queue is out of the queue, the elements in the stack need to be out of the stack in order and put out of the stack again to ensure first in first out. That is, putting the elements in one stack into another stack will change the order.
class MyQueue {
// Responsible for entering the stack
Stack<Integer> stackIn = null;
// Be responsible for getting out of the stack
Stack<Integer> stackOut = null;
public MyQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
// Simulated queue
public void push(int x) {
stackIn.push(x);
}
// Simulated queue
public int pop() {
// 1.stackOut is empty: put all the elements in stackIn on the stack in the order of being out of the stack
// 2. Right element in stackout, directly out of the stack
if (stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
return stackOut.pop();
}
// Return queue header element
public int peek() {
// It's the same as simulating the queue
if (stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
// Finally, the stackOut stack top element is returned
return stackOut.peek();
}
// Is the queue empty
public boolean empty() {
// The queue is empty only when both stackIn and stackOut are empty
return stackIn.isEmpty() && stackOut.isEmpty();
}
}
225. Implement stack with queue
Leetcode link
Please use only two queues to implement a last in first out (LIFO) stack, and support all four operations of the ordinary stack (push, top, pop and empty).
Implement MyStack class:
void push(int x) pushes element X to the top of the stack.
int pop() removes and returns the top of stack element.
int top() returns the top element of the stack.
boolean empty() returns true if the stack is empty; Otherwise, false is returned.
be careful:
You can only use the basic operations of the queue -- that is, push to back, peek/pop from front, size and is empty.
Your language may not support queues. You can use list or deque to simulate a queue, as long as it is a standard queue operation.
Example:
Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 2, 2, false]
Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // Return 2
myStack.pop(); // Return 2
myStack.empty(); // Return False
Solution:
If you want to use an input queue and an output queue like the above question, you can't. Because the data in the queue is imported into another queue, the order of the data does not change. Here, a queue is used. When simulating the stack, move the element from the head of the queue to the end of the queue until the element at the end of the original queue is the current head of the queue.
class MyStack {
// Queue for simulation stack
Queue<Integer> queue = null;
public MyStack() {
queue = new LinkedList<>();
}
// Push
public void push(int x) {
queue.add(x);
}
// Out of stack
public int pop() {
// Move n times, and the tail element moves to the head of the team
int n = queue.size() - 1;
while (n-- > 0) {
queue.add(queue.poll());
}
// At this time, the queue head element is the original queue tail element, which goes out of the queue and returns
return queue.poll();
}
// Return stack top element
public int top() {
// The same as the stack, you can finally get the original team tail element and then add it to the team tail
int n = queue.size() - 1;
while (n-- > 0) {
queue.add(queue.poll());
}
int res = queue.peek();
queue.add(queue.poll());
return res;
}
// Returns whether the stack is empty
public boolean empty() {
return queue.isEmpty();
}
}
20. Valid brackets
Leetcode link
Given a string s that only includes' (',') ',' {','} ',' [','] ', judge whether the string is valid.
Valid strings must meet:
The left parenthesis must be closed with the same type of right parenthesis.
The left parentheses must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "() [] {}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true
Solution:
Use the stack to simulate the matching process, traverse s, and put it on the stack if it is an open bracket. If it is a right bracket, if it matches the top bracket of the stack, the top element of the stack will pop up; If there is no match or the remaining sum is not enough, it means that false cannot be returned on all matches.
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(' || ch == '[' || ch == '{') {
// It's an open parenthesis. Put it on the stack
stack.push(ch);
} else {
// Right parenthesis to determine whether it matches the top element of the stack
if (!stack.isEmpty() && isMate(stack.peek(), ch)) {
// Do not match, pop up stack top element
stack.pop();
} else {
// If no left parenthesis matches it, false is returned
return false;
}
}
}
// If the left parenthesis is left, the stack is not empty, and fasle is returned; If all matches are successful, the stack is empty and returns true
return stack.isEmpty();
}
// Determine whether the two parentheses match
public boolean isMate(char l, char r) {
if (l == '(' && r == ')') return true;
if (l == '{' && r == '}') return true;
if (l == '[' && r == ']') return true;
return false;
}
}
Optimization: if it is a left bracket, you can use the right bracket matching the universe to enter the stack. In this way, you only need to judge whether the two right brackets are the same when judging whether they match the elements at the top of the stack
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') stack.push(')');
else if (ch == '{') stack.push('}');
else if (ch == '[') stack.push(']');
else if (!stack.isEmpty() && ch == stack.peek()) {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
}
1047. Delete all adjacent duplicates in the string
Leetcode link
Given the string S composed of lowercase letters, the duplicate deletion operation will select two adjacent and identical letters and delete them. Repeat the duplicate deletion operation on S until the deletion cannot continue. Returns the final string after all deduplication operations are completed. The answer is guaranteed to be unique.
Example:
Enter: "abbaca"
Output: "ca"
Explanation: for example, in "abbaca", we can delete "bb". Because the two letters are adjacent and the same, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca", in which only "aa" can perform duplicate deletion, so the final string is "ca".
Solution:
Xiaole: traverse s, the stack is empty or the character is different from the top element of the stack, and enter the stack; If the stack is not empty and the characters are the same as the top element, the top element will pop up
class Solution {
public String removeDuplicates(String s) {
Stack<Character> stack = new Stack<>();
// Traversal s
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!stack.isEmpty() && ch == stack.peek()) {
// If the stack is not empty and is the same as the stack top element, pop up the stack top element
stack.pop();
} else {
// The stack is empty or different from the top element of the stack
stack.push(ch);
}
}
// Splice the remaining characters in the stack and return
StringBuilder sb = new StringBuilder();
for (char ch : stack) {
sb.append(ch);
}
return String.valueOf(sb);
}
}
Optimization: StringBuilder can act as a stack. StringBuilder has deleteCharAt to delete the specified subscript element
class Solution {
public String removeDuplicates(String s) {
StringBuilder sb = new StringBuilder();
// The stack top element pointer always points to the stack top element, which needs to be maintained dynamically when entering and exiting the stack
int top = -1;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (top >= 0 && ch == sb.charAt(top)) {
sb.deleteCharAt(top);
top--;
} else {
sb.append(ch);
top++;
}
}
return sb.toString();
}
}
Double finger Needling: out of the stack and in the stack are replaced by the coverage of the elements in the array. The slow pointer points to the elements at the top of the stack, and the fast pointer traverses the characters
public String removeDuplicates(String s) {
char[] arr = s.toCharArray();
int slow = 0;
for (int fast = 1; fast < s.length(); fast++) {
if (slow >= 0 && arr[fast] == arr[slow]) {
// When the stack is the same, the pointer at the top of the stack will slow--
slow--;
} else {
// If not, it should be put on the stack. The stack entry position is behind the stack top position, so slow + +, and then overwrite
slow++;
arr[slow] = arr[fast];
}
}
return String.valueOf(arr).substring(0, slow + 1);
}
150. Evaluation of inverse Polish expression
Leetcode link
Find the value of the expression according to the inverse Polish representation. Valid operators include +, -, *, /. Each operand can be an integer or another inverse Polish expression.
Note that the division between two integers only retains the integer part. It can be guaranteed that the given inverse Polish expression is always valid. In other words, an expression always yields a valid value and there is no case where the divisor is 0.
Example 1:
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: this formula is transformed into a common infix arithmetic expression: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Explanation: this formula is transformed into a common infix arithmetic expression: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10", "6", "9", "3", "+", "- 11", "", "/", "" 17 "," + "," 5 "," + "]
Output: 22
Explanation: this expression is transformed into a common infix arithmetic expression:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
Solution:
Traversing tokens, the first time you encounter an operator, you can combine the first two number operations. What if you encounter two operators serialized together?
You need to solve the first operator and update the first two numbers, so that there are still two numbers in front of the second operator. Here, use the stack to maintain
- If it is an operator, pop up the two number operations at the top of the stack and put the operation results on the stack;
- It is not an operator, but a number is put on the stack
- Return stack top result
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String str = tokens[i];
// 1. If it is an operator, pop up the two number operations at the top of the stack and put the operation results on the stack
if (str.equals("+")) {
stack.push(stack.pop() + stack.pop());
} else if (str.equals("-")) {
int num = stack.pop();
stack.push(stack.pop() - num);
} else if (str.equals("*")) {
stack.push(stack.pop() * stack.pop());
} else if (str.equals("/")) {
int num = stack.pop();
stack.push(stack.pop() / num);
} else {
// 2. It is not an operator, but a number into the stack
stack.push(Integer.valueOf(str));
}
}
// 3. Return stack top result
return stack.pop();
}
}
239. Maximum value of sliding window
Leetcode link
Give you an integer array nums, with a sliding window of size k moving from the leftmost side of the array to the rightmost side of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time. Returns the maximum value in the sliding window.
Example 1:
Input: num = [1,3, - 1, - 3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Position of sliding window | maximum
[1 3 -1] -3 5 3 6 7 | 3
1 [3 -1 -3] 5 3 6 7 | 3
1 3 [-1 -3 5] 3 6 7 | 5
1 3 -1 [-3 5 3] 6 7 | 5
1 3 -1 -3 [5 3 6] 7 | 6
1 3 -1 -3 5 [3 6 7] | 7
Example 2:
Input: num = [1], k = 1
Output: [1]
Solution: [....] Represents the value in the window. The number of some intervals in the window cannot be the largest number in the window. Let's analyze it first
-
Do not use the front 123 in [1,2,3,4,3,2,1], because 4 in [1,2,3,4] on the left makes it impossible for the maximum value to appear in 123 less than 4, so [4,3,2,1] is reserved in the window;
-
Is the 321 behind the 4 still useful? Useful because [4,3,2,1] when 4 moves out of the window, 3 becomes the largest number
-
[4,3,2,1] here comes a 5. Only [6,5] in [6,3,2,1,5] is useful, because as long as 321 is on the left of 5 and exists at the same time as 5, as part of the left side of the window, the maximum value can only appear in the window on the right of 5 or 5.
So let's maintain the useful number in a queue save window to ensure that the number in the queue is from left to right and from large to small, that is, a monotonous queue. For example, in the window [5,1,2,3], a new number of 4 should be saved in the monotonic queue [5,4]. The left side of the monotone queue is the maximum number in the window
Then, when k = 5, the window moves to the right and 5 will be out of the queue. How to judge whether the queue head element should be out of the queue?
The subscript should be saved in the queue. For example, the subscript of 5 is 2 and the subscript of the new number is 7. Judge whether the queue head element needs to be out of the queue through the subscript difference.
Why use double ended queues?
Window [5,1,2,3,4], 4 is a new -- > queue [5,4], which needs to be compared with the new 4 and the tail element, because 4 is larger than the tail element, and the tail element comes out of the queue in turn
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
// Double ended queue
Deque<Integer> deque = new ArrayDeque<>();
// Traversal array
for (int i = 0; i < nums.length; i++) {
// Queue is not empty, deque Peekfirst() = = I - K (after the window is moved to the right, the subscript of the team head element is outside the window)
if (!deque.isEmpty() && deque.peekFirst() == i - k) {
// Mark the queue under the queue header element
deque.pollFirst();
}
// The window is not empty. The new nums[i] is larger than the end of the queue element. The end of the queue element is out of the queue
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// The new number is subscripted into the queue
deque.addLast(i);
// Starting from the k - 1 count in window, the maximum number in the window will be recorded
if (i >= k - 1) {
// The queue head is the maximum subscript in the window and is recorded in the return array
res[i - k + 1] = nums[deque.peek()];
}
}
return res;
}
}