1. Quick sort

In normal coding, sometimes the sort method in Arrays included in the JDK is sometimes used, which defaults to using quick sorting. Quicksort is also a typical application of divide-and-conquer problem solving. In many programming languages, unstable sorting of arrays and lists is used in internal implementations using quick sorting.

Let's briefly explain the implementation of quicksort:

Idea of quick sorting:

Adopt the idea of divide and conquer recursion,

Each recursively takes the leftmost value from the array as the pivot, with other elements smaller than the pivot placed on the left side of the pivot and larger than the pivot placed on the right.

public void quickSort(int[] arr,int l,int r){

if(l>=r) return;

int p=todo (arr,l,r);

quickSort(arr,p+1,r); Two parts outside the recursive pivot

quickSort(arr,l,p-1);

}

public int findPivot(int[] arr,int l,int r){ //寻找枢轴

Quick sort idea: Put the leftmost element of the array in the right place, the elements to the left of the element are smaller than this element, and the elements on the right are larger than this element. A similar sort is performed on each element, and the entire array becomes ordered.

int p=arr[l]; Get the leftmost element

int i=l+1; int j=r; i,j represents the element pointed to by the current pointer

while(true)

{

while(i< =r&arr[i]<p) i++;// When the element i points to is less than p, no adjustment is required

while(j>l&&arr[j]>p) j--; When the element j points to is greater than p, no adjustment is required

if(i>j) break; Boundary conditions

int temp=arr[i]; Jump out of the above two while, indicating that at this time i points to an element larger than p, j points to an element smaller than p, and at this time the positions are exchanged to ensure that the left side is smaller than the right side.

scar[i]=scar[j];

arr[j]=temp;

i++;

j--;

} // Jump out of the big while, indicating that i>j

int temp=arr[j]; For example, the pivot is 4, i is 3, j is 6, after jumping out of while (true), i point to 6, j points to 3, at this time swap 4 and 3 to ensure that the left side is less than 4, the right side is greater than 4.

arr[j]=arr[l];

arr[l]=temp;

return j; The position of the last j points to 4, which is the pivot

Time complexity of quick sorting:

Each pass in a quicksort requires iterating through the array from left to right and right to left, so the complexity of each pass is O(n)

In the ideal case, each pivot is the middle number of the entire array, so that the entire array requires only the complexity of O (logN) to traverse. (Similar to the binary algorithm, if each time is an intermediate number, the complexity is O(logN))

So the total time complexity is ideally O(NlogN)

The worst case is that each pivot is the minimum or maximum value of the entire array, so that the complexity returns to O(N) and the total time complexity is O(n^2).

Spatial complexity:

In the best case, the array is evenly traversed by O(logN), so the depth of the stack required for recursion should be about O(logN),

In the case of poor comparison, each pivot is the maximum and minimum value of the array, so O(n) recursion is required, and the depth of the stack is O(n).

2. Morris traversal

Usually encounter binary tree problems, basically the most traversal method is through recursion traversal, very simple and convenient, but in fact, you can also use the stack to achieve iterative traversal of binary trees.

But both of these traversal methods require a certain amount of extra space as support.

Today's talk about this is that there is no need to use other space, simply use the pointer to the tree itself to traverse.

Knowledge points about quicksort, Morris traversal, divide and conquer

Morris traverses ideas:

Start the traversal, if this node has no left node, it means that this is the leftmost node, so it is the current starting point of the middle order traversal, and you can join the queue directly.

If this is not the case:

There may be two cases, one is that a pre node association has been established, and the other is that a pre node association has not been established.

1. For cases where no node association is established:

Start looking for the pre node of this node, connected by the right pointer of the pre node.

2。 For established node associations:

The output operation is performed and returned to the next higher node via the right pointer.

public List<Integer> inorderTraversal(TreeNode root) {

if (root == null) {

return new ArrayList<>();

TreeNode cur = root; Record the current node location

List<Integer> res = new ArrayList<>();

while (cur != null) {

if (cur.left == null) { // The left node is empty, move to the right child node

res.add(cur.val);

cur = cur.right;

} else {

TreeNode prev = cur.left;

while (prev.right != null && prev.right != cur) { // traverses to the rightmost node of the left subtree

prev = prev.right;

if (prev.right == null) { // Establish a connection to the returned parent node

prev.right = cur;

cur = cur.left;

} else { // The left subtree establishes a connection, indicating that the traversal is complete and the connection can be removed

res.add(cur.val); The middle order traverses the entry of the current node

prev.right = null;

return res;

The time complexity of Morris traversal is: O(N)

The spatial complexity is: O(1)

3. Merge K liters of sequence listings

Idea: divide and conquer algorithm + merge two linked lists

class Solution {

public ListNode mergeKLists(ListNode[] lists) {

if(lists.length==0) return null;

if(lists.length==1) return lists[0];

return dfs(lists,0,lists.length-1);

public ListNode dfs(ListNode[] lists, int start, int end) { // divide and rule algorithm

if(start==end) return lists[start];

int mid=(end-start)/2 + start;

ListNode left=dfs(lists,start,mid);

ListNode right=dfs(lists,mid+1,end);

return mergeTwo(left,right);

public ListNode mergeTwo(ListNode l1, ListNode l2){ //merge algorithm

if(l1==null) return l2;

if(l2==null) return l1;

ListNode head=new ListNode(0);

ListNode p=head;

while(l1!=null|| l2!=null){

if(l1!=null&&l2!=null){

if(l1.val<l2.val){

p.next=new ListNode(l1.val);

l1=l1.next;

}else{

p.next=new ListNode(l2.val);

l2=l2.next;

}

}else if(l1==null){

p.next=new ListNode(l2.val); l2=l2.next;

}else if(l2==null){

p.next=new ListNode(l1.val); l1=l1.next;

p=p.next;

return head.next;

Time complexity: I can't tell the specifics... But it is certainly faster than the two-by-two merger, the complexity of the two-by-two merger is O(N), the division of the rule is similar to the binary, the complexity is O (logN).

Spatial complexity: If you make changes on the original linked list, the complexity is O(1).

4. Bit operations

When you see that you can't use the addition, subtraction, multiplication, and division operators, you can think that the general idea of this problem is to implement addition through bitwise operations.

If you think about it carefully, it is not difficult to find that the difference in the real bit operation can be calculated as the sum of two numbers without the carry.

What if there is a carry?

Specific carry conditions can be found in the same way.

For example, when calculating 8+3, 8:1000, 3:0011, there is no carry situation, and the difference or followed by 1011, that is, 11.

If it is 8+9, 8:1000, 9:1001, then the XOR is 0001, that is, 1.

If the result of the concession is one digit to the left, plus the result of the XOR, is it not equal to the total result?

Based on this idea, we can have the following code:

public int merge(int a,int b){

if(b==0) return a;

merge(a^b,(a&b)<<1);

Now that addition already exists, is it possible to continue to create multiplication according to addition?

Multiplication can be split into multiple additions, so we split the first multiplier into an array, and each element in the array is the second multiplier, and then adds up all the elements of the array to be the multiplicative value.

You can select the first element plus the second element, and then take the result plus the third element. But this method will be less efficient.

The idea of divide and conquer can be employed here. Divide the big tasks into smaller tasks that can no longer be small, and then add up the small tasks separately, and then return layer by layer, and finally converge into large tasks.

public int add(int a, int b) {

int[] list=new int[Math.abs(a)];

for(int i=0;i<Math.abs(a);i=merge(i,1)){

list[i]=b;

}

return dfs(list,0,merge(a,-1));

public int dfs(int[] list,int start,int end){

if(start>=end) return list[start];

int mid=merge(start,end)>>1;

int left=dfs(list,start,mid);

int right=dfs(list,merge(mid,1),end);

return merge(left,right);

public int merge(int a,int b){

if(b==0) return a;

return merge(a^b,(a&b)<<1);

Multiplication that uses bitwise operations and does not include addition, subtraction, multiplication, and division.

1. Using a hash table is quick and convenient

2. Bit operations

public boolean isUnique(String astr){

long bit = 0;

for(int i=0,i<arr.length,i++){

int move = arr.charAt(i) - 'A';

if((bit & (1L << move)) != 0) return false;

else bit |= (1L << move);

return true;

Status binary tree:

A binary tree that distinguishes nodes based on state. That is, according to the title, we can know that each node of this binary tree has its own state, and some nodes have a consistent state. If you go directly from top to bottom with pre-order traversal, it is difficult, because often the subsequent node situation will affect the previous result. And going down from front to front will cause too many front nodes to be added. For example, the first question you face from top to bottom: Does the root node need to add a monitor? Because there is no traversal to the subsequent situation, it is not possible to determine whether to add.

If you use the bottom-up traversal method, you can add monitors where you must add them, and the fewer monitors you need to add the higher you go, the clearer the overall situation. The final step is to determine whether the root node is needed.

So we traverse the entire tree by giving the node a state + going from bottom to top, so that the statistics are clear.

Based on the above discussion, it can be analyzed that for each node \textit{root}root, three types of state need to be maintained:

1. This node has monitors

2. This node does not have a monitor, but it is within the range of being monitored

3. This node is not within the scope of monitoring

The final condition of recursion is the left and right empty nodes that reach the leaf node, because it is an empty node, so its state is always in the monitoring range. At this point, the status of the left and right empty nodes should be already within the scope of monitoring, and it is not a monitor. The corresponding status is 2.

According to the above bottom-up strategy, for a node, its state needs to be judged by the state of the left and right child nodes. (A bit like dynamic programming, which can also be called tree dynamic programming)

1. If the left and right node states have a state of 3, it means that at least one of the left and right nodes is not within the scope of monitoring, and at this time, it is necessary to add a monitor to this node. Status is 1.

2. If the left and right node states are not 3, and at least one of them has a status of 1, it means that the left and right nodes are within the monitoring range, and at least one is a monitor. At this time, this node does not need a monitor, the status of this node is within the monitoring range, and there is no monitor. Status is 2.

3. If the left and right nodes are not 3, and the left and right nodes are not 1, it means that the left and right nodes are within the monitoring range, and the left and right nodes are not monitors. At this point, the status of this node is Not in Scope of Monitoring, and there is no monitor. Status 3.(You may want to add a monitor to this node.) Please take a look at the picture below :)

If the left and right nodes are 2 and the node is directly set to 1, it will waste a layer of nodes and put more monitors.

If you set it to 3 first and then place a monitor on top of 3, there will be fewer monitors. (The 3 here should be 2 after having a monitor on the upper level)

The termination condition is there, the state transition condition is there, and the result condition is still poor.

The final number of monitors is the number of nodes that have just been in the state of 1. Statistics can be performed in recursive procedures with a global variable.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution { //1.本节点有监视器2.本节点在监视范围内,但没有安装监视器3.本节点不在监视范围内
    int count=0;
    public int minCameraCover(TreeNode root) {
        if(root==null) return 0;
        if(dfs(root)==3) count++;
        return count;
    }
    public int dfs(TreeNode root){
        if(root==null) return 2; //如果是叶子节点，则左右都是2，叶子结点则会返回3
        int left=dfs(root.left);
        int right=dfs(root.right);
        if(left==3 || right==3){ // 左和右一定有一个不在监视范围内
            count++;  //此时此节点装上监控器
            return 1;
        }else if(left==1 || right==1){ //左和右一定全在监视范围内，并且左和右中有一个为监视器
            return 2;  //此时本节点肯定在监视范围内，但不用装监视器
        }else{ //左和右全在监视范围内，并且左和右都不是监视器
            return 3; //此时本节点为不在监控范围内
        }
    }
}

Post-sequence traversal of binary trees (non-recursive method):

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode-solution/

Because binary tree traversal needs to enter the child node and then return to the parent node, it is selected to use the stack to return to the upper layer, down to the stack, and up to the stack.

Enter the left node of the stack first. Then go out of the stack in turn, and the node you get should judge whether you need to go to the right child node, and judge two points:

1. Whether there is a right child node;

2. Whether the right child node has been there;

We use a flag bit to indicate whether we have been to the right child node.

If the right child node of this node has already been there, then according to the post-order traversal rules, it is time to add this node to the result set. After that, the flag position of this node is "Has been there", and then return to the parent node.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while(root!=null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(root.right==null || root.right==pre){
                res.add(root.val);
                pre=root; //此处作为标志位，标志着父节点的右字节点已经来过了。再回到父节点处应当将结果加入返回集合了。
                root=null;
            }else{ //右字节点存在，同时标志位也不存在，此时说明还没去过右边，该去了
                stack.push(root);
                root=root.right;
            }
        }
        return res;
    }
}

Cardinality sorting:

Radix sort belongs to "distribution sort", also known as "bucket sort".

Cardinality sorting is the process of allocating recycling.

Example: Very much like sorting poker cards in everyday life. If the playing cards are divided into colors, the spades ♠️ > the red peaches ♥️ > the plum blossoms ♣️ > square pieces ♦️

At the same time, it is divided into sizes 1<2<3<.....

When sorting, you can:

1. Divide the size first, from 1 to 13, and then divide the color;

2. You can also divide the color first, and then divide the size.

Implementation method:

The number of digits of the sorted number can be used as the suit of the playing cards mentioned above; 146 is three digits, and it is to be sorted three times;

The size of each person counted is the size of the playing card;

Step 1: First put the size of the current position of the playing cards into the bucket, paying attention to the order;

Step 2: Put the poker cards in the bucket back into the array in order.

Repeat these two steps in turn, and the number of times you repeat is the number of bits in the largest number of bits in the array.

class Solution {
    public int maximumGap(int[] nums) {
        //基数排序
        int max=0;
        for(int i=0;i<nums.length;i++){
            max=Math.max(max,nums[i]);
        }
        //求出最大值是几位数
        int p=0;
        while(max>0){
            p++; max/=10;
        }
        int[] count=new int[10];
        int[] buckets=new int[nums.length];
        for(int k=1;k<=p;k++){ //从个位开始循环
            for(int i=0;i<count.length;i++){ //清洗上一次循环
                count[i]=0;
            }
            for(int i=0;i<nums.length;i++){
                count[getFigure(nums[i],k)]++;  //求出个位，个位为某个值的计数位+1
            }
            for(int i=1;i<count.length;i++){
                count[i]+=count[i-1];
            }
            for(int i=nums.length-1;i>=0;i--){ //倒序将其插入到对应的桶中。倒序的原因是，前面的count统计是从左至右的，此时就要从右至左。
                int j=getFigure(nums[i],k);
                buckets[count[j]-1]=nums[i];
                count[j]--;
            }
            for(int i=0;i<nums.length;i++){
                nums[i]=buckets[i];
            }
        }
        //排序完毕，开始找两两最大差
        max=0;
        for(int i=1;i<nums.length;i++){
            max=Math.max(max,nums[i]-nums[i-1]);
        }
        return max;
    }
    public int getFigure(int num,int k){
        for(int i=1;i<k;i++){
            num/=10;
            if(num==0) break;
        }
        return num%10;
    }
}

Knowledge points about quicksort, Morris traversal, divide and conquer