Article directory
- stack
-
- bracket matching
- Minimum stack
- Maximum stack
- basic calculator
- Reverse Polish expression calculation
- queue
-
- Two stacks implement queues
- Two queue implementation stack
- LRU cache
- Hash
-
- sum of two numbers
- sum of three numbers
Stack
Bracket matching
Traverse the string, push the left bracket onto the stack, pop the right bracket out of the stack to determine whether there is a match, end the traversal, and determine whether the stack is empty
public boolean isValid(String s) {<!-- -->
Map<Character,Character> map = new HashMap<Character,Character>();
Stack<Character> stack = new Stack<Character>();
map.put('(',')');
map.put('{','}');
map.put('[',']');
for(int i = 0; i<s.length();i + + ){<!-- -->
Character c = s.charAt(i);
if(map.containsKey(c)){<!-- -->
stack.push(c);
}else {<!-- -->
if(stack.isEmpty()){<!-- -->
return false;
}
Character key = stack.pop();
Character value = map.get(key);
if(c!=value){<!-- -->
return false;
}
}
}
return stack.isEmpty();
}
Minimal stack
Create two stacks, one stack is used to store elements normally, and the other stack is used to store the smallest element corresponding to the normal stack element
class MinStack {<!-- -->
private Deque<Integer> xStack;
private Deque<Integer> minStack;
public MinStack(){<!-- -->
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val){<!-- -->
xStack.push(val);
minStack.push(val<minStack.peek()?val:minStack.peek());
}
public void pop(){<!-- -->
xStack.pop();
minStack.pop();
}
public int top(){<!-- -->
return xStack.peek();
}
public int getMin(){<!-- -->
return minStack.peek();
}
}
Max stack
The principle is the same as the minimum stack
class MaxStack {<!-- -->
private Deque<Integer> xStack;
private Deque<Integer> maxStack;
public MinStack(){<!-- -->
xStack = new LinkedList<Integer>();
maxStack = new LinkedList<Integer>();
maxStack.push(Integer.MIN_VALUE);
}
public void push(int val){<!-- -->
xStack.push(val);
maxStack.push(val>maxStack.peek()?val:maxStack.peek());
}
public void pop(){<!-- -->
xStack.pop();
maxStack.pop();
}
public int top(){<!-- -->
return xStack.peek();
}
public int getMax(){<!-- -->
return maxStack.peek();
}
}
Basic Calculator
Traverse the string and record the operator before the current number. If it is + or -, push the current number or the opposite number onto the stack. If it is * or /, pop an element from the stack and operate on the current element, push the result onto the stack, and finally Pop the stack one by one to perform addition operations to get the final result
public int calculate(String s) {<!-- -->
Stack<Integer> stack = new Stack<>();
int num = 0;
char pre = ' + ';
for (int i = 0; i < s.length(); i + + ) {<!-- -->
char c = s.charAt(i);
if (Character.isDigit(c)) {<!-- -->
num = num * 10 + c - '0';
}
if (!Character.isDigit(c) & amp; & amp; s.charAt(i) != ' ' || i == s.length() - 1) {<!-- -->
if (pre == ' + ' || pre == '-') {<!-- -->
stack.push(pre == ' + ' ? num : (-1) * num);
} else {<!-- -->
int x = stack.pop();
if (pre == '*') {<!-- -->
x *= num;
} else {<!-- -->
x /= num;
}
stack.push(x);
}
pre = c;
num = 0;
}
}
int res = 0;
while (!stack.isEmpty()) {<!-- -->
res + = stack.pop();
}
return res;
}
Reverse Polish expression calculation
Traverse the character array, if it is a number, push it onto the stack; if it is an operator, pop two elements out of the stack for operation, and push the result onto the stack
public int evalRPN(String[] tokens) {<!-- -->
Stack<Integer> stack = new Stack<>();
for(int i=0;i<tokens.length;i + + ){<!-- -->
if(!Character.isDigit(tokens[i].charAt(0)) & amp; & amp;tokens[i].length()==1){<!-- -->
char c = tokens[i].charAt(0);
int x = stack.pop();
int y = stack.pop();
int res=0;
if(c==' + '){<!-- -->
res = y + x;
}else if(c=='-'){<!-- -->
res = y-x;
}else if(c=='*'){<!-- -->
res = y*x;
}else if(c=='/'){<!-- -->
res = y/x;
}
stack.push(res);
}else{<!-- -->
stack.push(Integer.parseInt(tokens[i]));
}
}
return stack.pop();
}
Queue
Two stacks implement queues
A stack serves as an entry point for elements and is called an entry stack. A stack serves as an exit point for elements and is called an exit stack. Push elements are pushed from the entry stack and elements are popped from the exit stack. If the exit stack is empty, the entry stack is The stack element is popped and pushed into the exit stack
class MyQueue {<!-- -->
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {<!-- -->
inStack = new LinkedList<Integer>();
outStack = new LinkedList<Integer>();
}
public void push(int x) {<!-- -->
inStack.push(x);
}
public int pop() {<!-- -->
if(outStack.isEmpty()){<!-- -->
while(!inStack.isEmpty()){<!-- -->
int x = inStack.pop();
outStack.push(x);
}
}
return outStack.pop();
}
public int peek() {<!-- -->
if(outStack.isEmpty()){<!-- -->
while(!inStack.isEmpty()){<!-- -->
int x = inStack.pop();
outStack.push(x);
}
}
return outStack.peek();
}
public boolean empty() {<!-- -->
return inStack.isEmpty() & amp; & amp;outStack.isEmpty();
}
}
Two queues implement stack
Every time an element is entered from one queue, after entering, the elements of the other queue are dequeued in turn, entered into a queue, and then the two queues are exchanged
class MyStack {<!-- -->
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack() {<!-- -->
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
void push(int x){<!-- -->
queue2.offer(x);
while(!queue1.isEmpty()){<!-- -->
int num = queue1.poll();
queue2.offer(num);
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
int pop(){<!-- -->
return queue1.poll();
}
int top(){<!-- -->
return queue1.peek();
}
boolean empty(){<!-- -->
return queue1.isEmpty();
}
}
LRU cache
Create a doubly linked list to store elements, add a head node and a tail node to the doubly linked list to facilitate insertion and deletion operations, create a map to store the node key, and value, and find the node in O(1) time. When getting an element, determine whether it exists in the map. If it exists, delete it first, then insert it at the head, and finally return it. When inserting or updating, it is judged whether it exists in the map. If it exists, it is updated, and if it does not exist, it is inserted. The insertion operation is directly inserted into the head, and the update operation is first deleted and then inserted into the head. After insertion, if the number of elements exceeds the limit, delete it from the end
class LRUCache {<!-- -->
class DoubleLinkedNode{<!-- -->
int key;
int value;
DoubleLinkedNode pre;
DoubleLinkedNode next;
public DoubleLinkedNode(){<!-- -->
}
public DoubleLinkedNode(int key, int value){<!-- -->
this.key = key;
this.value = value;
}
}
Map<Integer,DoubleLinkedNode> map;
DoubleLinkedNode head;
DoubleLinkedNode tail;
int size;
int capacity;
public LRUCache(int capacity) {<!-- -->
map = new HashMap<>();
head = new DoubleLinkedNode();
tail = new DoubleLinkedNode();
head.next = tail;
tail.pre = head;
size = 0;
this.capacity = capacity;
}
public int get(int key) {<!-- -->
if(map.containsKey(key)){<!-- -->
DoubleLinkedNode node = map.get(key);
remove(node);
addToHead(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {<!-- -->
if(map.containsKey(key)){<!-- -->
DoubleLinkedNode node = map.get(key);
node.value = value;
remove(node);
addToHead(node);
}else{<!-- -->
DoubleLinkedNode node = new DoubleLinkedNode(key, value);
map.put(key, node);
addToHead(node);
size + + ;
if(size>capacity){<!-- -->
int removeKey = removeFromTail();
map.remove(removeKey);
size--;
}
}
}
public void remove(DoubleLinkedNode node) {<!-- -->
node.pre.next = node.next;
node.next.pre = node.pre;
}
public void addToHead(DoubleLinkedNode node) {<!-- -->
node.next = head.next;
head.next.pre = node;
node.pre = head;
head.next = node;
}
public int removeFromTail() {<!-- -->
DoubleLinkedNode pre = tail.pre;
remove(tail.pre);
return pre.key;
}
}
Hash
Sum of two numbers
Use HashMap to turn a double loop into a single traversal
public int[] twoSum(int[] nums, int target) {<!-- -->
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i + + ){<!-- -->
if(map.containsKey(target-nums[i])){<!-- -->
return new int[]{<!-- -->map.get(target-nums[i]),i};
}else{<!-- -->
map.put(nums[i],i);
}
}
return null;
}
Sum of three numbers
Use sorting and double pointers to replace the high complexity of three-layer loops, and at the same time solve the problem that double-layer loops and hashing cannot directly remove duplicates
public List<List<Integer>> threeSum(int[] nums) {<!-- -->
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int first = 0; first < n; first + + ) {<!-- -->
if (first > 0 & amp; & amp; nums[first] == nums[first - 1]) {<!-- -->
continue;
}
int third = n - 1;
int target = -nums[first];
for (int second = first + 1; second < n; second + + ) {<!-- -->
if (second > first + 1 & amp; & amp; nums[second] == nums[second - 1]) {<!-- -->
continue;
}
while (second <third & amp; & amp; nums[second] + nums[third] > target) {<!-- -->
third--;
}
if (second == third) {<!-- -->
break;
}
if (nums[second] + nums[third] == target) {<!-- -->
List<Integer> list = new ArrayList<>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
res.add(list);
}
}
}
return res;
}