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 codeTraversal 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 codeTraversal 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 codeTraversal 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 codeBreadth-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 codeZigzag 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 codeMethod 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 codeMethod 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
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
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!
