1. The right boundary of binary search is leng-1; While left <= right right = mid – 1; To find the left edge, check that left is greater than length and that left is not equal to target. To find the right edge, we need to check that right is less than 0, that right is not equal to target.
2. Quicksort
The pivot takes the first number from the array, dividing the number greater to the right and the number less to the left. Double pointer, while loop left < right. While (left < right && nums [left] <= pivot) find the number on the left greater than pivot and the number on the right less than pivot
public static int partition(int[] nums, int start, int end){ int pivot = nums[start]; int left = start + 1, right = end; While (left < right && nums[left] <= pivot) {left++; While (left < right && nums[right] >= pivot) {right--; } if(left < right){exchange(nums, left, right); left++; right--; } } if(left == right && nums[right] > pivot) right--; exchange(nums, start, right); return right; }Copy the code3. Find the KTH largest number
Maximum heap implements PriorityQueue
The code is finding the minimum number of K.
public static int[] smallestK(int[] arr, int k) { int[] vec = new int[k]; If (k == 0) {return vec; } PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { return num2 - num1; }}); for (int i = 0; i < k; ++i) { queue.offer(arr[i]); } for (int i = k; i < arr.length; ++i) { if (queue.peek() > arr[i]) { queue.poll(); queue.offer(arr[i]); } } for (int i = 0; i < k; ++i) { vec[i] = queue.poll(); } return vec; }Copy the code4. Pre-order, middle-order, back-order, and multi-level traversal of the binary tree
Before the order
public List<Integer> orderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if(root == null) return list; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(! stack.isEmpty()) { TreeNode cur = stack.pop(); if(cur.right ! = null) stack.push(cur.right); if(cur.left ! = null) stack.push(cur.left); list.add(cur.val); } return list; }Copy the codeIn the sequence
public List<Integer> inorderTraversal(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); List<Integer> list = new ArrayList<>(); if(root == null) return list; TreeNode cur = root; while(! stack.isEmpty() || cur ! = null) { while(cur ! = null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); list.add(cur.val); cur = cur.right; } return list; }Copy the codeAfter the order
Class Solution {public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(! stack.isEmpty()){ TreeNode node = stack.pop(); res.add(node.val); if(node.left ! = null) stack.push(node.left); if(node.right ! = null) stack.push(node.right); } Collections.reverse(res); return res; }}Copy the code5. Reverse linked list iteration: pre = null; Store the next node in the while, next.
Recursive method:
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
Copy the code6. Check whether the list has rings
Fast and slow pointer, judge whether meet.
Look for places where lists form rings
Start from the beginning at the same time. When the fast and slow Pointers meet, the fast Pointers continue to start from the beginning. The meeting position is the position to form the ring.
7. LRU implementation
HashMap + bidirectional linked list
Node
DoubleList: getSize\addLast\remove\removeFirst
LRUCathe: makeRecentLy\addRecentLy\deleteKey\removeLeastRecentLy
class Node { private int key, val; private Node pre, next; public Node(int key, int val) { this.key = key; this.val = val; } } class DoubleList { Node head, tail; private int size; public DoubleList() { head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.pre = head; size = 0; } public int getSize() { return size; } public void addLast(Node node) { node.pre = tail.pre; node.next = tail; tail.pre.next = node; tail.pre = node; size++; } public void remove(Node node) { node.pre.next = node.next; node.next.pre = node.pre; size--; } public Node removeFirst() { if (head.next == tail) { return null; } Node first = head.next; remove(first); return first; } } class LRUCache { private DoubleList cache; private HashMap<Integer, Node> map; private int cap; public LRUCache(int cap) { this.cap = cap; map = new HashMap<>(); cache = new DoubleList(); } public int get(int key) { if (! map.containsKey(key)) { return -1; } // Upgrade this data to the recently used makeRecently(key); return map.get(key).val; } public void put(int key, int val) {if (map.containsKey(key)) {// Delete old data deleteKey(key); // addRecently used data addRecently(key, val); return; } if (cap == cache.getSize()) {removeLeastRecently(); } // add the recently used element addRecently(key, val); } private void makeRecently(int key) {Node x = map.get(key); Cache.remove (x); Cache.addlast (x); Private void addRecently(int key, int val) {Node x = new Node(key, val); private void addRecently(int key, int val) {Node x = new Node(key, val); // The end of the list is the most recent element cache.addlast (x); Map.put (key, x); } /* deleteKey */ private void deleteKey(int key) {Node x = map.get(key); // Remove cache.remove(x); Remove (key); // Remove map.remove(key) from the map. } private void removeLeastRecently() {private void removeLeastRecently() {private void removeLeastRecently() {private void removeLeastRecently(); Int deletedKey = deletedNode.key; map.remove(deletedKey); }Copy the codeLinkedHashMap
public class LRUCathe {
int capacity;
LinkedHashMap<Integer, Integer> cathe = new LinkedHashMap<>();
public LRUCathe(int capticy) {
this.capacity = capticy;
}
public int get(int key) {
if (!cathe.containsKey(key)) {
return -1;
}
makeItRecently(key);
return cathe.get(key);
}
public void put(int key, int val) {
if (cathe.containsKey(key)) {
cathe.put(key, val);
makeItRecently(key);
}
if (cathe.size() >= capacity) {
int oldestKey = cathe.keySet().iterator().next();
cathe.remove(oldestKey);
}
cathe.put(key, val);
}
private void makeItRecently(int key) {
int val = cathe.get(key);
cathe.remove(key);
cathe.put(key, val);
}
}
Copy the code8. Two stacks implement queues
One inStack and one outStack push into inStack peek to judge whether the outStack is empty. If it is empty, the inStack will be transferred. If it is not empty, peek POP will be returned directly
9. Queue implementation stack
10. Backpack problem
11. Buying and selling stocks
12. Plunder