The sorting

The so-called sorting algorithm is to resort one or more groups of data according to the established pattern through a specific algorithm factor. The new sequence follows certain rules and reflects certain rules, so the processed data is easy to screen and calculate, and greatly improves the computational efficiency.

For sorting:

We need to have some stability first
When two identical elements occur in a sequence
After a certain sorting algorithm
Their relative positions do not change before and after sorting.

So let’s take a look at some of the uHF ranking algorithms for interviews

Bubble sort

Bubble sort is basically just two for loops nested and then swapped. I won’t go into that.

Steps:

1. Compare adjacent elements. If the first is larger (smaller) than the second, swap them both.

2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When this is done, the final element will be the largest (smallest) number.

3. Repeat the above steps for all elements except the last selected element (ordered).

4. Keep repeating the above steps for fewer and fewer elements (unordered elements) until there are no more

Video:

Bubble sort demonstration of data structure sorting algorithm

Sample code:

public void bubbleSort(int[] arr) {
    int temp = 0;
    boolean swap;
    for (int i = arr.length - 1; i > 0; i--) { // The length of the sort required each time
        // Add a swap flag to indicate that the array is in order if the current round has not been swapped
        swap = false;
        for (int j = 0; j < i; j++) { // From the first element to the ith element
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swap = true; }}if(! swap){break; }}}Copy the code

Merge sort

For merge sort, the idea can be summed up as divide and conquer. So you take an array, you divide it up into a bunch of individual numbers, and then you combine them one by one, and you get an ordered array.

Steps:

Divide the sequence to be sorted into subsequences of length 1
Then combine these sequences in pairs; I get some ordered sequence of length 2
And then combine these sequences in pairs; I get some ordered sequence of length 4
And combine them in pairs; It just merges into one sequence
So that gives us the sort that we want

Video:

Merge sort

Sample code:

/ / the entry
public void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    internalMergeSort(arr, temp, 0, arr.length - 1);
}

private void internalMergeSort(int[] arr, int[] temp, int left, int right) {
    // When left == right, no further division is required
    if (left < right) {
        int mid = (left + right) / 2;
        // Split left and right down
        internalMergeSort(arr, temp, left, mid);
        internalMergeSort(arr, temp, mid + 1, right);
        // After splitting, return the result to mergemergeSortedArray(arr, temp, left, mid, right); }}// Merge two ordered subsequences
public void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    // add the column that is not empty
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // Copy temp data back to the original array
    for (i = 0; i < k; i++) { arr[left + i] = temp[i]; }}Copy the code

Quick sort

The idea of quicksort can be simply summed up as: flank both sides, one at a time. Each selection of a reference point, a sorting to determine its final position, one step in place.

Steps:

1. First take a number from the sequence as the reference number

2. In the partitioning process, everything greater than this number is placed to its right, and everything less than or equal to this number is placed to its left

3. Repeat the second step for the left and right intervals until each interval has only one number

Generally speaking, it is the method of excavation fill number + divide-and-conquer

Note: fast sorting algorithm is not unique, so far I have seen three sorting methods, here I use the oldest, is a lot of textbook sorting method analysis

Video:

Quicksort algorithm

Sample code:

public void quickSort(int[] arr){
    quickSort(arr, 0, arr.length-1);
}

private void quickSort(int[] arr, int low, int high){
    if (low >= high)
        return;
    int pivot = partition(arr, low, high);        // Divide the array into two parts
    quickSort(arr, low, pivot - 1);                   // Sort the left subarray recursively
    quickSort(arr, pivot + 1, high);                  // Sort the right subarray recursively
}

private int partition(int[] arr, int low, int high){
    int pivot = arr[low];     / / benchmark
    while (low < high){
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];             // Swap records larger than the baseline to the left end
        while (low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low];           Swap records smaller than the baseline to the right end
    }
    // The scan is complete and the benchmark is in place
    arr[low] = pivot;
    // Return the base position
    return low;
}
Copy the code

Count sorting

Counting sort as the name implies, the idea is to record the number of occurrences of each number, finally in order to take out.

Steps:

Create an array C of length K+1, with each element initially set to 0(the default in Java is 0).
Iterate over the array and count the number of occurrences of each element. For example, if an element with key I appears three times, then C[I]=3.
C[I +1]=C[I]+C[i-1] =C[I]+C[i-1]
Create a temporary array T of the same length as the array to be sorted. Go through the end of the array, arrange the elements into T, and you can get the location of the elements directly from C, but remember to subtract one from the corresponding position in C every time you process an element.

Video:

Visual interpretation of counting sorting algorithm

Sample code:

I’ve seen a ton of code on the Internet, but it’s mostly for sorting numbers above zero. The following algorithm can be used to sort numbers less than 0, but I added a lot of comments, and it is easy to understand:

public void countSort(int[] arr) {
	// Find the maximum and minimum values
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }

    int[] b = new int[arr.length]; // Store arrays
    int[] count = new int[max - min + 1]; // Count arrays

    for (int num = min; num <= max; num++) {
        // Initialize each element to 0, array subscript starts at 0, so subtract min
        count[num - min] = 0;
    }

    for (int i = 0; i < arr.length; i++) {
        int num = arr[i];
        count[num - min]++; // For each occurrence of a value, the value of the corresponding element in the count array is +1
        // count[I] is the number of elements whose value is equal to I
    }

    for (int i = min + 1; i <= max; i++) {
        count[i - min] += count[i - min - 1];
        // count[I] is the number of elements <= I
        // This is done to facilitate the final assignment,
        Count [num - min]-- = count[num - min]-- = count[num - min]--
    }

    for (int i = 0; i < arr.length; i++) {
            int num = arr[i]; // The i-th bit of the original array
            int index = count[num - min] - 1; // Summing up the indices of the corresponding elements in the array
            b[index] = num; // Store the value in the corresponding index of the storage array
            count[num - min]--; // In the summing array, the sum of the values decreases by 1.
    }

    // Replace the value of the stored array with the original array
    for(int i=0; i < arr.length;i++){
        arr[i] = b[i];
    }
}
Copy the code

Bucket sort

The idea of bucket sorting is that, first of all, according to specific rules, divided into a number of ‘buckets’, each’ bucket ‘has a range, the size of the corresponding’ bucket ‘within the range of the number, numbered. Then arrange the numbers in each ‘bucket’ in order, and finally join each ‘bucket’ in order.

Steps:

According to the range of difference between the largest element and the smallest element in the set to be sorted and the mapping rule, the number of buckets to be applied is determined.
Iterate over the set to be sorted and move each element to the corresponding bucket;
Sorts the elements in each bucket and moves them into the sorted collection.

The sorted collection mentioned in Step 3 is the same collection to be sorted in Steps 1 and 2. Different from counting sort, after step 2 of bucket sort is completed, all elements are in the bucket, and after sorting the elements in the bucket, the process of moving elements does not depend on the original set, so you can move the elements in the bucket back to the original set.

Video:

Bucket sort

Sample code:

The counting sort mentioned above can also be regarded as a special bucket sort to a certain extent. Similarly, bucket sort code on the Internet is a large pile, what language all have. But none of them solve the sorting problem of numbers less than 0, so either they don’t deal with it or they throw an exception, so this algorithm effectively solves the sorting problem of numbers less than 0

public static void bucketSort(int[] arr){
	// Find the maximum and minimum values
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length; i++){
        max = Math.max(max, arr[i]);
        min = Math.min(min, arr[i]);
    }
    
    / / barrels
    // In bucket sorting, the number of buckets is arbitrary
    // The number of buckets divided by this method changes with the density of the partition sequence
    int bucketNum = (max - min) / arr.length + 1;
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
    // Initialize each bucket
    for(int i = 0; i < bucketNum; i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    
    // Put each element into the appropriate bucket
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    
    // Sort each bucket
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
        for (int j = 0; j < bucketArr.get(i).size(); j++) { arr[j] = bucketArr.get(i).get(j); }}}Copy the code

Binary tree

In computer science, a binary tree is a tree structure with at most two subtrees per node. Subtrees are usually called “left subtrees” and “right subtrees”. Binary trees are often used to implement binary search trees and binary heaps.

Here’s a look at what happens in an interview to test our binary tree question. First we define a node class:

The node classes used in the following tests are as follows: ps: Explain the ones on LeetCode
class TreeNode { public TreeNode left, right; public int val; public TreeNode(int val) { this.val = val; }}Copy the code

Sequential traversal

The traversal of binary trees can be divided into the following three types:

Sequential traversal: Traversal order rule is [root left and right]
Middle order traversal: Traversal order rule is [left root right]
Post-order traversal: Traversal order rule is [left and right root]

Sequential traversal:

The first is code implementation:

// order traversal first
public void preTraverse(TreeNode root) {
    if(root ! =null) { System.out.println(root.val); preTraverse(root.left); preTraverse(root.right); }}Copy the code

Traversal result: ABCDEFGHK

Middle-order traversal:

The first is code implementation:

// middle order traversal
public void inTraverse(TreeNode root) {
    if(root ! =null) { inTraverse(root.left); System.out.println(root.val); inTraverse(root.right); }}Copy the code

Traversal result: BDCAEHGKF

Post-order traversal:

The first is code implementation:

// after the sequence traversal
public void postTraverse(TreeNode root) {
    if(root ! =null) { postTraverse(root.left); postTraverse(root.right); System.out.println(root.val); }}Copy the code

Traversal result: DCBHKGFEA

video

A class to solve the computer level 2 problem: binary tree traversal structure

Level traversal

Hierarchical traversal of binary trees is easy to understand, and I’ll give you an example here. First, we give a binary tree:

Hierarchical traversal, as the name implies, is traversal from top to bottom, layer by layer, each layer output from left to right

Calculation result: 5-4-8-11-13-4-7-2-1

For the ergodic calculation method, the common ones are:

Depth-first traversal (DFS)

Breadth-first traversal (BFS)

I have encountered such a problem in the process of brushing:

Given a binary tree, return the Zigzag level order traversal of its nodes' values. then right to left for the next level and alternate between).

Z traversal, so here’s another one:

Zigzag traversal

Let’s look at the implementation in code:

Depth-first traversal (DFS)

The only hierarchical traversal we have learned is BFS (extensive search), and DFS deep search itself is a non-recursive implementation for sequential sorting. This is the first time I’ve ever seen DFS solve a hierarchical traversal problem.

Its steps can be briefly summarized as:

Conventional deep search, record the level of the current node
Adds the current node to the corresponding layer in the List
And since we’re searching from left to right, we’re also joining from left to right
You end up with something like the following

0-1-4 – > 5 August 2-11-13 – > 4 > 3-7 – > 2 – > 1

This traversal method is too rare to find relevant video, fortunately, the principle is easy to understand

// Hierarchy traversal (DFS)
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    
    dfs(root, res, 0);
    return res;
}

private void dfs(TreeNode root, List<List<Integer>> res, int level) {
    if (root == null) {
        return;
    }
    if (level == res.size()) {
        res.add(new ArrayList<>());
    }
    res.get(level).add(root.val);
    
    dfs(root.left, res, level + 1);
    dfs(root.right, res, level + 1);
}
Copy the code

Breadth-first traversal (BFS)

Unlike DFS, which is implemented recursively, BFS needs to be implemented in queues.

The steps of hierarchical traversal are:

A node that is not empty is added to the queue first
Take the node from the queue, and if the left and right nodes of the node are not empty, add the left and right nodes to the queue
Repeat until the queue is empty

To put it bluntly, the parent node joins the queue, the parent node leaves the queue, the left child node joins the queue, and the right child node joins the queue. Recursively iterate over all nodes

video

Binary tree traversal algorithm – hierarchical traversal algorithm

public List<List<Integer>> levelOrder(TreeNode root) {
    List result = new ArrayList();

    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while(! queue.isEmpty()) { ArrayList<Integer> level =new ArrayList<Integer>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode head = queue.poll();
            level.add(head.val);
            if(head.left ! =null) {
                queue.offer(head.left);
            }
            if(head.right ! =null) {
                queue.offer(head.right);
            }
        }
        result.add(level);
    }

    return result;
}
Copy the code

Zigzag traversal

This question type is also very rare. It comes from the original interview question in LeetCode:

Given a binary tree, return the Zigzag level order traversal of its nodes’ values. then right to left for the next level and alternate between). Given a binary tree, perform a zigzagging traverse from top to bottom, i.e. if this layer is left to right, the lower layer is right to left.

The process is similar to BFS, except that there is a flag to distinguish between left and right

A node that is not empty is added to the queue first
Take the node from the queue, and if the left and right nodes of the node are not empty, add the left and right nodes to the queue
Invert isFromLeft
Repeat until the queue is empty

video

Again, this shape is too special, so there is no related video analysis, but fortunately, the algorithm process is also very easy to understand

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null) {return result;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean isFromLeft = false;
    while(! queue.isEmpty()){intsize = queue.size(); isFromLeft = ! isFromLeft; List<Integer> list =new ArrayList<>();
        for(int i = 0; i < size; i++){
            TreeNode node;
            if (isFromLeft){
                node = queue.pollFirst();
            }else{
                node = queue.pollLast();
            }
            list.add(node.val);
            
            if (isFromLeft){
                if(node.left ! =null){
                    queue.offerLast(node.left);
                }
                if(node.right ! =null){ queue.offerLast(node.right); }}else{
                if(node.right ! =null){
                    queue.offerFirst(node.right);
                }
                if(node.left ! =null){
                    queue.offerFirst(node.left);
                }
            }
        }
        result.add(list);
    }
    
    return result;
}
Copy the code

Turn around

This is an interview with Huawei.

Enter the binary tree as follows:

Output after inversion:

At first glance, it seems very difficult. In fact, it is very simple to come up with a solution. Here I will directly cite three solutions:

Method 1: For example, we use recursive thinking. The essential idea is:

The essential idea is also to interchange left and right nodes
The pre-swap recursive call processes the left and right nodes of the root node separately
Ensure that the left and right nodes have been flipped.

In three steps, let’s look at the code implementation:

	   public TreeNode invertTree(TreeNode root) {	        
	        if (root == null) {
	            return null;
	        }
	        Stack<TreeNode> stack = new Stack<>();
	        stack.push(root);	        
	        while(! stack.isEmpty()) {final TreeNode node = stack.pop();
	            final TreeNode left = node.left;
	            node.left = node.right;
	            node.right = left;           
	            if(node.left ! =null) {
	                stack.push(node.left);
	            }
	            if(node.right ! =null) { stack.push(node.right); }}return root;
	    }
Copy the code

Method 2: Loop, queue storage (BFS, non-recursive)

The essential idea is:

The left and right nodes are swapped
Loop over the left and right children of each node
Queues unflipped child nodes
Loop until all nodes in the stack are cycled.

	public TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(! queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode left = node.left; node.left = node.right; node.right = left;if(node.left ! =null) {
				queue.offer(node.left);
			}
			if(node.right ! =null) { queue.offer(node.right); }}return root;
	}
Copy the code

Method three: “last stage, three steps second kill” recursion

The essential idea is:

The left and right nodes are swapped
The pre-swap recursive call processes the left and right nodes of the root node separately
Ensure that the left and right nodes have been flipped.

Let’s look at the code:

public void invert(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invert(root.left);
    invert(root.right);
}
Copy the code

The maximum

At first glance, it is to send points. My first thought was that defining Max in a method to hold the maximum value of traversal would end up redefining Max every time I recurse, which is not the right way to do it. So what?

Adopt the idea of divide and conquer
Start at the bottom of the tree
Compare it in pairs and put back the maximum

Take a look at the algorithm

public int getMax(TreeNode root) {
    if (root == null) {
        return Integer.MIN_VALUE;
    } else {
        int left = getMax(root.left);
        int right = getMax(root.right);
        returnMath.max(Math.max(left, rigth), root.val); }}Copy the code

Maximum depth

Depth, like maximum, is easy to think of as complicated, but it’s actually very simple, and you can also think of it as a divide-and-conquer idea

The maximum depth of a binary tree is the depth of a leaf node with the longest path from the root node.
The depth of the binary tree is equal to the height of the binary tree, which is the height of the root node. The height of the root node is +1 if the height of the left and right subtrees is greater.

video

Find the maximum depth of a binary tree

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}
Copy the code

The minimum depth

This question is so common that I got it wrong the first time I saw it:

Title: The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node. Note: Leaf nodes are nodes that have no child nodes.

You see, you have to specify the correct end condition of the recursion

Here’s an example:

A lot of people write code that doesn’t fit the test case 1,2, because they don’t understand the problem

A leaf node is a node with no children. 1 is not a leaf node

They’re asking for the shortest distance to the leaf, so all of them return 1 and of course that’s not the answer

And the other thing about this problem is to figure out the end condition for recursion

A leaf node is defined as a leaf node when both the left and right children are null
Return 1 when both the left and right children of the root node are empty
Returns the depth of the non-empty child node when one of the children left or right of the root node is empty
If the left and right children of the root node are not empty, return the value of the node with the smaller depth of the left and right children

video

The minimum depth of a binary tree

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    
    if (left == 0) {
        return right + 1;
    } else if (right == 0) {
        return left + 1;
    } else {
        return Math.min(left, right) + 1; }}Copy the code

Balanced binary trees

Concept: The height difference between the left and right subtrees of a balanced binary tree is no more than 1

Set a flag
If an imbalance is found, a non-flag is returned

video

Balanced binary trees

public boolean isBalanced(TreeNode root) {
    returnmaxDepth(root) ! = -1;
}

private int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
        return -1;
    }
    return Math.max(left, right) + 1;
}
Copy the code

Attention

In order to improve the quality of the article, prevent tedious

Next part of the algorithm

The longer the article is summed up. I have always felt that an excessively long essay is like an excessively long meeting/class, which is not a good experience, so I plan to write another essay to summarize the rest of the exam points
In the follow-up article, I will continue to list stack queue heap dynamic planning matrix bit operations and other nearly 100 kinds, interview high-frequency algorithm questions, and its text and text analysis + teaching video + example code, in-depth analysis can continue to pay attention to _yuanhao programming world
Not fast, just high quality, each article will be updated in 2-3 days cycle, and strive to maintain high quality output

This article is enough to effectively solve the problem of “SQLite” database access security

Everyone has to learn picture compression to effectively solve the Android app OOM

Android gives your Room a free ride on the RxJava bandwagon from repetitive code

The founder of the ViewModel and ViewModelProvider. Factory: the ViewModel

Singleton pattern – globally available Context objects, enough for this article

Scale gesture ScaleGestureDetector source code analysis, this article is enough

ObjectAnimator, ValueAnimator, ObjectAnimator, ValueAnimator

After watching this animation frame of Never View again, I kneeled and rubbed the clothes board

Android custom clock control hour, minute hand, second hand drawing this article is enough

Android custom control – draw clock dial

Welcome to attention_yuanhaoThe nuggets!

I set up a warehouse on GitHub for you to follow up your study

Warehouse address: Super dry goods! Carefully summarized video, classification, summary, you pass by the old iron support! For a Star!

Thumb up, please! Because your encouragement is the biggest power that I write!

🔥 interview essential: high-frequency algorithm summary “text and text analysis + teaching video + example code” sort + binary tree part 🔥

The sorting

Bubble sort

Steps:

Video:

Sample code:

Merge sort

Steps:

Video:

Sample code:

Quick sort

Steps:

Video:

Sample code:

Count sorting

Steps:

Video:

Sample code:

Bucket sort

Steps:

Video:

Sample code:

Binary tree

Sequential traversal

Sequential traversal:

Middle-order traversal:

Post-order traversal:

video

Level traversal

Depth-first traversal (DFS)

Breadth-first traversal (BFS)

video

Zigzag traversal

video

Turn around

Method 1: For example, we use recursive thinking. The essential idea is:

Method 2: Loop, queue storage (BFS, non-recursive)

Method three: “last stage, three steps second kill” recursion

The maximum

Maximum depth

video

The minimum depth

Here’s an example:

video

Balanced binary trees

video

Attention

Next part of the algorithm

Related articles

This article is enough to effectively solve the problem of “SQLite” database access security

Everyone has to learn picture compression to effectively solve the Android app OOM

Android gives your Room a free ride on the RxJava bandwagon from repetitive code

The founder of the ViewModel and ViewModelProvider. Factory: the ViewModel

Singleton pattern – globally available Context objects, enough for this article

Scale gesture ScaleGestureDetector source code analysis, this article is enough

ObjectAnimator, ValueAnimator, ObjectAnimator, ValueAnimator

After watching this animation frame of Never View again, I kneeled and rubbed the clothes board

Android custom clock control hour, minute hand, second hand drawing this article is enough

Android custom control – draw clock dial

Welcome to attention_yuanhaoThe nuggets!

I set up a warehouse on GitHub for you to follow up your study

Thumb up, please! Because your encouragement is the biggest power that I write!

Related Posts

3. Run your first Flutter App in three minutes

ZSH: Command not found: Indicates the solution

Batch image compression for mobile development improves development efficiency