Object comparator
public static boolean isEqual(Integer o1, Integer o2) {
if (o1 == null && o2 != null) {
return false;
}
if (o1 != null && o2 == null) {
return false;
}
if (o1 == null && o2 == null) {
return true;
}
return o1.equals(o2);
}Unidirectional linked list
//One way linked list node structure (can be implemented as a template)
public class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
Bidirectional linked list
//Bidirectional linked list node structure
public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
The simplest exercise of one-way linked list and two-way linked list
public static class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
// head
// a -> b -> c -> null
// c -> b -> a -> null
public static Node reverseLinkedList(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
======================================================================================
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
public static DoubleNode reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}2) Delete all given values
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
// head = removeValue(head, 2);
public static Node removeValue(Node head, int num) {
// head comes to the first position that does not need to be deleted
while (head != null) {
if (head.value != num) {
break;
}
head = head.next;
}
// 1 ) head == null
// 2 ) head != null
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}Stack and queue
Stack: data in and out, like a magazine
Queue: data first in first out, like queuing
Practical implementation of stack and queue
Bidirectional linked list implementation
public static class Node<T> {
public T value;
public Node<T> last;
public Node<T> next;
public Node(T data) {
value = data;
}
}
public static class DoubleEndsQueue<T> {
public Node<T> head;
public Node<T> tail;
public void addFromHead(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
}
public void addFromBottom(T value) {
Node<T> cur = new Node<T>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.last = tail;
tail.next = cur;
tail = cur;
}
}
public T popFromHead() {
if (head == null) {
return null;
}
Node<T> cur = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
cur.next = null;
head.last = null;
}
return cur.value;
}
public T popFromBottom() {
if (head == null) {
return null;
}
Node<T> cur = tail;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
cur.last = null;
}
return cur.value;
}
public boolean isEmpty() {
return head == null;
}
}Array implementation stack
Array + index
Double ended linked list implementation stack
Press in and take out in the same direction
public static class MyStack<T> {
private DoubleEndsQueue<T> queue;
public MyStack() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T pop() {
return queue.popFromHead();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}Double ended linked list implementation queue
Press in and out in different directions
public static class MyQueue<T> {
private DoubleEndsQueue<T> queue;
public MyQueue() {
queue = new DoubleEndsQueue<T>();
}
public void push(T value) {
queue.addFromHead(value);
}
public T poll() {
return queue.popFromBottom();
}
public boolean isEmpty() {
return queue.isEmpty();
}
}Array implementation queue
Circular array + two pointers + size
public static class MyQueue {
private int[] arr;
private int pushi;// end
private int polli;// begin
private int size;
private final int limit;
public MyQueue(int limit) {
arr = new int[limit];
pushi = 0;
polli = 0;
size = 0;
this.limit = limit;
}
public void push(int value) {
if (size == limit) {
throw new RuntimeException("The queue is full and can't be added");
}
size++;
arr[pushi] = value;
pushi = nextIndex(pushi);
}
public int pop() {
if (size == 0) {
throw new RuntimeException("The queue is empty. You can't take any more");
}
size--;
int ans = arr[polli];
polli = nextIndex(polli);
return ans;
}
public boolean isEmpty() {
return size == 0;
}
// If the current subscript is i, return to the next position
private int nextIndex(int i) {
return i < limit - 1 ? i + 1 : 0;
}
}Since languages have these structures and APIs, why do you need to practice by hand?
1) Algorithmic problem independent language
2) The api provided by the language is limited. When there are new functions that the api does not provide, they need to be rewritten
3) The bottom layer of any software tool is the most basic algorithm and data structure, which can not be bypassed
Realize a special stack, and then realize the function of returning the smallest element in the stack on the basis of the basic functions
Memory data stack + minimum stack (compare the pressing data with the minimum stack top data size, press it into the minimum stack if it is small, and press the minimum stack top data again if it is large)
public static class MyStack1 {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack2() {
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum) {
if (this.stackMin.isEmpty()) {
this.stackMin.push(newNum);
} else if (newNum < this.getmin()) {
this.stackMin.push(newNum);
} else {
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public int pop() {
if (this.stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
this.stackMin.pop();
return this.stackData.pop();
}
public int getmin() {
if (this.stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}How to implement queue structure with stack structure
push stack + pop stack: 1 push stack data is poured to the pop stack at one time. 2. Only when the pop stack is empty can data be poured in
public static class TwoStacksQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
// push stack pours data into pop stack
private void pushToPop() {
if (stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
public void add(int pushInt) {
stackPush.push(pushInt);
pushToPop();
}
public int poll() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.pop();
}
public int peek() {
if (stackPop.empty() && stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushToPop();
return stackPop.peek();
}
}How to implement stack structure with queue structure
queue+help two queues. The data is stored in the queue. When taking the data, move the queue data into the help queue until only the last data is returned, and exchange the queue and help queue
public static class TwoQueueStack<T> {
public Queue<T> queue;
public Queue<T> help;
public TwoQueueStack() {
queue = new LinkedList<>();
help = new LinkedList<>();
}
public void push(T value) {
queue.offer(value);
}
public T poll() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public T peek() {
while (queue.size() > 1) {
help.offer(queue.poll());
}
T ans = queue.poll();
help.offer(ans);
Queue<T> tmp = queue;
queue = help;
help = tmp;
return ans;
}
public boolean isEmpty() {
return queue.isEmpty();
}
}Recursion? What is this?
1. Method call
2. Method end condition
For novices, it is necessary to draw the structure diagram of the calling process (tree diagram), which is conducive to the analysis of recursion
Recursion is not metaphysics. The bottom layer of recursion is realized by system stack
Any recursive function can be changed to non recursive
example
How to find the maximum value in array arr[L..R] by recursive method.
1) Divide the [L..R] range into left and right halves. Left: [L..Mid] right [Mid+1..R]
2) The left part maximizes and the right part maximizes
3) The maximum value in the [L..R] range is max {left part maximum value, right part maximum value}
Note: 2) is a recursive process. When there is only one number in the range, you can no longer recurse
// Find the maximum value L on the range of arr[L..R] R N
public static int process(int[] arr, int L, int R) {
// There is only one number in the arr[L..R] range. It returns directly, base case
if (L == R) {
return arr[L];
}
// L...R is more than one number
// mid = (L + R) / 2
int mid = L + ((R - L) >> 1); // Midpoint one
int leftMax = process(arr, L, mid);
int rightMax = process(arr, mid + 1, R);
return Math.max(leftMax, rightMax);
}Master formula
Shape such as
T (n) = a * t (n / b) + O (n ^ d) (where a, B and d are constants)
The time complexity can be determined directly through the Master formula
If log (B, a) < D, the complexity is O(N^d)
If log (B, a) > D, the complexity is O(N^log(b,a))
If log(b,a) == d, the complexity is O(N^d * logN)
Hashtable
1) Hash table can be understood as a collection structure at the use level
2) If there is only key and no accompanying data value, you can use the HashSet structure
3) If there are both key s and accompanying data value s, you can use the HashMap structure
4) Whether there is accompanying data or not is the only difference between HashMap and HashSet. The actual structure is the same thing
5) Using the operations of hash table put, remove, put and get, it can be considered that the time complexity is O(1), but the constant time is relatively large
6) If the hash table is a basic type, it is internally passed by value, and the memory occupation is the size of this thing
7) If the hash table is not the basic type, it is passed internally by reference, and the memory occupation is 8 bytes
Ordered table
1) an ordered table can be understood as a set structure at the use level
2) If there is only key and no accompanying data value, the TreeSet structure can be used
3) If there are both key s and accompanying data value s, the TreeMap structure can be used
4) Whether there is accompanying data or not is the only difference between TreeSet and TreeMap. The actual structure of the underlying is the same thing
5) The ordered table organizes key s in order, while the hash table is not organized at all
6) Red black tree, AVL tree, size balance tree and jump table all belong to ordered table structure, but the specific implementation of the bottom layer is different
7) The basic value to be passed is the size of the internal memory
8) If it is not a basic type, it is passed internally by reference, and the memory occupation is 8 bytes
9) No matter what the underlying implementation is, as long as it is an ordered table, it has the following fixed basic functions and fixed time complexity
Comparison between ordered table and hash table
When the hash table is used, the time complexity of addition, deletion, modification and query is O(1)
When used, the ordered table has more functions than the hash table, and the time complexity is O(logN)
The ordered table sorts the data, so if it is not a basic type, you need to implement the comparator