Niuke interview high frequency list (group 1) difficulty: simple & medium

（1）NC78 Reverse a linked list

（2）NC140  Sort

Two common sorts

Use fast platoon to realize

 public int[] MySort (int[] arr) {
        fastSort(arr,0,arr.length-1);
        return arr;
        
    }
    private void fastSort(int[] arr,int l,int r){
        if(l>=r)
            return;
        int num = arr[r];
        int sl = l,sr=r;
        while(l<r){
            while(l<r&&arr[l]<num) l++;
            // Be sure to judge before filling 
            if(l<r)
                arr[r--] = arr[l];
            while(l<r&&arr[r]>num)r--;
            // Be sure to judge before filling 
            if(l<r)
                arr[l++] = arr[r];
        }
        arr[r] = num;
        fastSort(arr,sl,l-1);
        fastSort(arr,l+1,sr);
    }

  Realize by merging

public class Solution {

    public int[] MySort (int[] arr) {
        // write code here
        mergeSort(arr,0,arr.length-1);
        return arr;
        
    }
    private void mergeSort(int[] arr , int l , int r){
        if(l>=r)
            return;
        int mid = (l+r)>>1;
        // Continue recursion on both sides 
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        // Both ends recursively , Just merge this layer 
        merge(arr,l,mid,r);
    }
    private void merge(int[] arr,int l,int mid,int r){
        int[] t = new int[r-l+1];
        int index = 0;
        int h1 = l, h2 = mid+1;
        while(h1<=mid&&h2<=r){
            if(arr[h1]<arr[h2])
                t[index++] = arr[h1++];
            else
                t[index++] = arr[h2++];
        }
        while(h1<=mid)
            t[index++]=arr[h1++];
        while(h2<=r)
            t[index++]=arr[h2++];
        // Note that remember to transfer the values in the temporary array to the original array 
        for(int i = 0;i<t.length;i++)
            arr[l++]=t[i];
    }
}

Heap sort  

Priority queue

(3)NC45  Implementation of binary tree preorder , In the middle order and after order

Return to form

public int[][] threeOrders (TreeNode root) {
        //  Distinguish with a linked list to store 
        ArrayList<Integer> prelist = new ArrayList<Integer>();
        ArrayList<Integer> inlist = new ArrayList<Integer>();
        ArrayList<Integer> postlist = new ArrayList<Integer>();
        
        preOrder(root,prelist);
        inOrder(root,inlist);
        postOrder(root,postlist);
        
        // Then create a two-dimensional array according to the length of the linked list 
        int[][] res = new int[3][prelist.size()];
        for(int i=0;i<prelist.size();i++){
            res[0][i] = prelist.get(i);
        }
        for(int i=0;i<inlist.size();i++){
            res[1][i] = inlist.get(i);
        }
        for(int i=0;i<postlist.size();i++){
            res[2][i] = postlist.get(i);
        }
        return res;
        
    }

(4)NC119  The smallest K Number

This topic can be divided into chapters , Large top pile . It's easier to implement the big top stack . Or use Array Bring their own sort Sort

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(k<=0||input.length==0)
            return res;
        if(input.length<=k){
            for(int i =0;i<input.length;i++)
                res.add(input[i]);
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((o1,o2)->(o2-o1));
        for(int i = 0;i<input.length;i++){
            if(queue.size()>=k){
                if(queue.peek()>input[i]){
                    queue.poll();
                    queue.offer(input[i]);
                }
                   
            }
            else{
                queue.offer(input[i]);
            }
           
        }
        while(!queue.isEmpty()){
            res.add(queue.poll());
        }
        return res;
    }
}

(5)NC15  Find the sequence traversal of binary tree

(6)NC88  Search for the first K Big

Use fast platoon , There are two points to note

1、 Be sure to remember , temporal t Put in

2、 Recursive time , The operation of reducing the scope

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if(n<=0||K>n)
            return -1;
        sortInt(a,0,n-1,K-1);
        return a[K-1];
    }
    private void sortInt(int[] a, int l,int r,int k){
        int t = a[r];
        int nl = l,nr=r;
        while(nl<nr){
            while(nl<nr&&a[nl]>t)nl++;
            if(nl<nr) a[nr--]=a[nl];
            while(nl<nr&&a[nr]<=t)nr--;
            if(nl<nr) a[nl++]=a[nr];
        }
        // Remember to t Go back 
        a[nl]=t;
        if(nl==k)
            return;
        //+1,-1 The operation of reducing the scope , Otherwise, it will cause a dead cycle 
        if(nl<k)
            sortInt(a,nl+1,r,k);
        else 
            sortInt(a,l,nl-1,k);
    }
}