High frequency record
| Sorting method | Time complexity (average) | Time complexity (worst) | Time complexity (best) | Spatial complexity | The stability of | complexity |
|---|---|---|---|---|---|---|
| Direct insertion sort | O(n2)O(n2) | O(n2)O(n2) | O(n)O(n) | O(1)O(1) | stable | simple |
| Hill sorting | O(nlog2n)O(nlog2n) | O(n2)O(n2) | O(n)O(n) | O(1)O(1) | unstable | More complicated |
| Direct selection sort | O(n2)O(n2) | O(n2)O(n2) | O(n2)O(n2) | O(1)O(1) | unstable | simple |
| Heap sort | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(1)O(1) | unstable | More complicated |
| Bubble sort | O(n2)O(n2) | O(n2)O(n2) | O(n)O(n) | O(1)O(1) | stable | simple |
| Quick sort | O(nlog2n)O(nlog2n) | O(n2)O(n2) | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | unstable | More complicated |
| Merge sort | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(nlog2n)O(nlog2n) | O(n)O(n) | stable | More complicated |
| Radix sort | O(d(n+r))O(d(n+r)) | O(d(n+r))O(d(n+r)) | O(d(n+r))O(d(n+r)) | O(n+r)O(n+r) | stable | More complicated |
BubbleSort
Compare two adjacent elements in sequence, swap if the order is wrong, until all elements are exhausted, the last element is the largest (smallest) value, and then sort as described above.
Time complexity: O(n^2)
private void bubbleSort(int a[]){
int temp;
for(int i = 0; i<a.length-1; i++){for(int j = 0; j<a.length-1-i; j++){if(a[j]>a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp; }}}}Copy the codeSelection sort
On the first trip, find the smallest and put it on the first, on the second trip, find the second smallest and put it on the second…
Time complexity: O(n^2)
public static void selectSort(int a[]){
for(int i = 0; i<a.length; i++){for(int j = i+1; j<a.length; j++){if(a[i]>a[j]){
inttemp = a[i]; a[i] = a[j]; a[j] = temp; }}}}Copy the codeQuickSort
Divide and conquer: divide a large piece into smaller pieces and count them one by one
- Set the value of one side to sentry
- I’m going to put everything to the right of this number, everything less than or equal to this number on the left.
- I’m sorting the rest of the interval
private void quickSort(int a[],int left,int right){
// End condition
if(left <right){
// Sort each time
int base = division(a,left,right);
// The sentries start sorting
/ / the left
quickSort(a,left,base-1);
/ / right
quickSort(a,base+1,right); }}// Use divide-and-conquer sorting
private int division(int a[],int left,int right){
/ / the sentry
int base = a[left];
while (left<right){
// The sentry is on the left, so move right left
while(left<right && a[right]>=base){
right--;
}
if(left ! = right) { a[left] = a[right]; }// The sentry is on the right, so the left moves right
while(left<right && a[left]<=base){
left++;
}
if(left ! = right) { a[right] = a[left]; } } a[left] = base;return left;
}
Copy the codeBinary insertion:
while (lo <= hi) {
// Dichotomy is divided into two, array middle index
final int mid = (lo + hi) >>> 1;
// The dichotomy is one and two, the value at the middle index of the array
final int midVal = array[mid];
if (midVal < value) {
/** If the value in the middle of the array is smaller than the value you are looking for, the value is in the middle and back of the array, so the current subscript is mid + 1 */
lo = mid + 1;
} else if (midVal > value) {
/** If the value in the middle of the array is greater than the value to be found, it means that the value to be found is in the middle of the array, so the current subscript value is mid-1 */
hi = mid - 1;
} else {
// If the value in the middle of the array is the same as the value in question, return the index mid in the middle of the array
return mid; // value found}}Copy the codePoker algorithm
Path from the root node to the destination node
Find the smallest k number
- Using quicksort: O(nlogn)
public static int[] getLeastNumbers1(int[] input, int k) {
if (input == null || input.length < k) {
return null;
}
int[] output = new int[k];
pivotFindMinK(input, output, k, 0, input.length - 1);
return output;
}
private static void pivotFindMinK(int[] numbers, int[] output, int k, int start, int end) {
if (numbers == null || numbers.length == 0) {
return;
}
int left = start;
int right = end;
int temp = numbers[left];
while (left < right) {
while (numbers[right] > temp && left < right) {
right--;
}
numbers[left] = numbers[right];
while (numbers[left] <= temp && left < right) {
left++;
}
numbers[right] = numbers[left];
}
numbers[left] = temp;
if (left > k-1) {
pivotFindMinK(numbers, output, k, start, left - 1);
} else if (left < k-1) {
pivotFindMinK(numbers, output, k, right + 1, end);
} else {
System.arraycopy(numbers, 0, output, 0, k); }}Copy the code- Create an array, put k numbers in front of the array, and arrange them in order from small to large, traverse the original array, if there is a smaller value than the new array, insert sort, and then get the new array.
- Small root heap implementation, in order to put the small root heap — big top heap (parent <= children), small root heap size k, over size, delete the top element, conversely, add the big root heap — small top heap (parent >= children)
Binary search method
/ * * * using recursive binary search * title: recursionBinarySearch *@paramArr ordered array *@paramKey Indicates the keyword to be searched. *@returnLocation found */
public static int recursionBinarySearch(int[] arr,int key,int low,int high){
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
int middle = (low + high) / 2; // The initial middle position
if(arr[middle] > key){
If the value is larger than the keyword, the keyword is in the left area
return recursionBinarySearch(arr, key, low, middle - 1);
}else if(arr[middle] < key){
If the value is smaller than the keyword, the keyword is in the right area
return recursionBinarySearch(arr, key, middle + 1, high);
}else {
return middle;
}
Copy the codeCan the sum of two numbers in an integer array equal a given number
- If the array is ordered, the two subscripts, if they’re greater than the given number, the left hand side — if they’re less than the given number, the right hand side ++, until they’re equal or the right hand side equals the left hand side
int[] a = {1.4.5.7.9.12.56.456};
int i = 0;
int j = a.length-1;
int sum = 65;
while(i<j){
if(a[i] + a[j] >sum){
j--;
}else if(a[i] + a[j] <sum){
i++;
}else{
System.out.println(a[i] + "+" + a[j] + "=" + sum);
break; }}Copy the code- If the array is unordered
public static void twoSum(int[] nums,int target){
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i<nums.length; i++){ System.out.println("-- -- -- -- -- -- -- --");
if(map.containsKey(nums[i])){
System.out.println(nums[map.get(nums[i])] + "+" + nums[i] + "=" + target);
break;
}
intvalue = target-nums[i]; map.put(value,i); }}Copy the codeMaximum sum of contiguous subarrays
public int maxSubArray(int[] nums) {
int max = nums[0];
int sum = nums[0];
for(int i = 1; i<nums.length; i++){if(nums[i] + sum < nums[i]){
sum = nums[i];
}else{
sum +=nums[i];
}
if(sum > max){ max = sum; }}return max;
}
Copy the codeMoore voting method
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for(int num : nums){
if(votes == 0) x = num;
votes += num == x ? 1 : -1;
}
returnx; }}Copy the codeBinary tree
Binary tree traversal
// sequence traversal
public void levelOrder(BinaryTreeNode root) {
BinaryTreeNode temp;
Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
queue.offer(root);
while(! queue.isEmpty()) { temp = queue.poll(); System.out.print(temp.getData() +"\t");
if (null! = temp.getLeft()) queue.offer(temp.getLeft());if (null! = temp.getRight()) { queue.offer(temp.getRight()); }}}// Preorder traversal recursively
public void preOrder(BinaryTreeNode root) {
if (null! = root) { System.out.print(root.getData() +"\t"); preOrder(root.getLeft()); preOrder(root.getRight()); }}// Preorder traversal in a non-recursive manner
public void preOrderNonRecursive(BinaryTreeNode root) {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.push(root);
while(! stack.isEmpty()) { BinaryTreeNode node = stack.pop(); System.out.print(node.getData() +"\t");
if(node.getRight() ! =null) {
stack.push(node.getRight());
}
if(node.getLeft() ! =null) { stack.push(node.getLeft()); }}}// Middle order facilitates non-recursion
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {return list;
}
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while(! stack.isEmpty()){ TreeNode node = stack.pop();if(node.left ! =null){
stack.add(node);
stack.add(node.left);
}else{
list.add(node.val);
if(node.right ! =null){
stack.add(node.right);
}else{
while(! stack.isEmpty()){ TreeNode node1 = stack.pop(); list.add(node1.val);if(node1.right ! =null){
stack.add(node1.right);
break;
}
}
}
}
}
return list;
}
// after the sequence traversal
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) {return new ArrayList<>();
}
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while(! stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val);if(node.left ! =null){
stack.add(node.left);
}
if(node.right ! =null){
stack.add(node.right);
}
}
List<Integer> result = new ArrayList<>();
for(int i = list.size()-1; i>=0; i--){ result.add(list.get(i)); }return result;
}
// Zigzag print
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> listList = new ArrayList<>();
if(root == null) {return listList;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int i = 1;
while(! queue.isEmpty()){ LinkedList<Integer> list =new LinkedList<>();
int count = queue.size();
for(int j = 0; j<count; j++){ TreeNode node = queue.poll();if(i%2= =0){
list.addFirst(node.val);
}else{
list.add(node.val);
}
if(node.left ! =null){
queue.add(node.left);
}
if(node.right ! =null){
queue.add(node.right);
}
}
i++;
if(list.size()>0){ listList.add(list); }}return listList;
}
Copy the codeTwo views the first public parent view
- Add a set and a set, one to store a, put b in array A, return false when array a is repeated, and return in another set.
public static Set<Integer> getIds(Integer[] a, Integer[] b){
Set<Integer> same = new HashSet<Integer>(); // Store the same elements in two arrays
Set<Integer> temp = new HashSet<Integer>(); // To store the elements of array A
for (int i = 0; i < a.length; i++) {
temp.add(a[i]); // Insert elements from array A into Set to remove duplicate elements
}
for (int j = 0; j < b.length; j++) {
// Add elements from array B to temp
Temp. Add (b[j]) returns false if the same element already exists in temp
if(!temp.add(b[j]))
same.add(b[j]);
}
}
Copy the codeIf you want to find the index of two arrays, use map where key is the value and value is the index of the array
- Put array A into set, poll b into set, return false, repeat the value
public static void getIds(int a[], int b[]) {
Set<Integer> set1 = new HashSet<>();
for(Integer integer:a){
set1.add(integer);
}
for(Integer j:b){
if(! set1.add(j)){ System.out.println(j);break; }}}Copy the code- The first root node in two linked lists
The two Pointers run two chains respectively. After the short run, the long head is assigned to the past, and then the long run is also completed. Finally, the intersection of the two Pointers is the first root node of the two linked lists
public static void getNode(Node nodeA, Node nodeB) {
Node pA = nodeA;
Node pB = nodeB;
while(pA ! = pB) {if (pA.next == null) {
pA = nodeB;
} else {
pA = pA.next;
}
if (pB.next == null) {
pB = nodeA;
} else {
pB = pB.next;
}
}
System.out.print(pA.value);
}
Copy the code- The most recent common ancestor of a binary tree
class Solution {
TreeNode node;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dps(root,p,q);
return node;
}
public boolean dps(TreeNode root, TreeNode p, TreeNode q){
if(root == null) {return false;
}
if(root.val == p.val){
node = p;
return true;
}
if(root.val == q.val){
node = q;
return true;
}
boolean a = dps(root.left,p,q);
boolean b = dps(root.right,p,q);
if(a && b){
node = root;
}
if(a || b){
return true;
}
return false; }}Copy the codeDetermine if the list is circular and return to the entry
Two Pointers, one running one at a time, one running two at a time, if they intersect, there is a ring chain
The slow ones will run one by one from the beginning, the fast ones will run from the intersection point, one by one, and finally meet is the entrance
public static Node isCircle(Node node) {
Node p = node;
Node q = node;
while(p ! =null&& q ! =null) {
p = p.next.next;
q = q.next;
if(p == q){
while(node ! = p){ node = node.next; p = p.next; }returnnode; }}return p;
}
Copy the codeWe have an array of integers, positive and negative numbers, and we put the negative numbers to the left, keeping their relative positions the same
To a linked list, traversing the linked list will recover and separate linked to the remaining positive chain
The array has two indexes, one that records the end of a negative number, and one that iterates through the array.
public static void get(int a[]){
for(int i = 0,j = 0; j<a.length; j++){if(a[j]<0) {int temp = a[j];
int k = j;
while(i<=k-1){
a[k] = a[k-1]; k--; } a[i] = temp; i++; }}for(inti:a){ System.out.println(i); }}Copy the codePrint the serpentine matrix
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[0];
int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
int[] res = new int[(r + 1) * (b + 1)];
while(true) {
for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
if(++t > b) break;
for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
if(l > --r) break;
for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
if(t > --b) break;
for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
if(++l > r) break;
}
returnres; }}Copy the codeFind the number of leaves in a binary tree
public int testTree(Tree tree){
if(tree==null) {return 0;
}
if(tree.left==null&&tree.right==null){
System.out.println("Leaf node:"+tree.val);
return 1;
}
return testTree(tree.left)+testTree(tree.right);
}
Copy the codeFind the depth of the binary tree
public static int treeDepth(TreeNode root) {
if (root == null) {
return 0;
}
// Calculate the depth of the left subtree
int left = treeDepth(root.left);
// Calculate the depth of the right subtree
int right = treeDepth(root.right);
// Depth of tree root = depth of subtree with longest path + 1
return left >= right ? (left + 1) : (right + 1);
}
Copy the codeDynamic programming
Maximum sum of arrays
Cumulative value: a cumulative value
Maximum: Records the maximum value of the cumulative value
Assuming the array is the largest, add one value at a time. If i-1 is less than 0, add I to the sum, if >0, add I to the sum, and update the maximum if the sum is greater than the maximum.
If the subscript of the largest sum of the array is needed, the subscript of the largest value is recorded
public static void main(String[] args) {
int[] array = {1, -2.3.10, -4.7.2, -5};
Long begintime = System.nanoTime();
int result = FindGreatestSumOfSubArray(array);
Long endtime = System.nanoTime();
System.out.println("The maximum sum of a continuous subarray is:"+result+", running time:"+(endtime - begintime) + "ns");
}
public static int FindGreatestSumOfSubArray(int[] array) {
int len = array.length;
if (len == 0) {return 0;
}
int[] currentsum = new int[len];
currentsum[0] = array[0];
int greatsetsum = array[0];
System.out.println("Step 1: Summing subarrays and:"+currentsum[0] +", the largest subarray and:+greatsetsum);
for(int i=1; i<array.length; i++){// The following is the state transition equation for dynamic programming
if(currentsum[i-1] >0){
currentsum[i] = currentsum[i-1] + array[i];
}else{
currentsum[i] = array[i];
}
// Update greatSetSum based on currentSum
if(currentsum[i] > greatsetsum){
greatsetsum = currentsum[i];
}
System.out.println("The first"+(i+1) +"Step: summing subarrays and:"+currentsum[i]+", the largest subarray and:+greatsetsum);
}
returngreatsetsum; }}Copy the code