「金三银四」

系列文章目录

本系列文章主要面向马上要进行算法实习，就业，跳槽的友友们。
本系列文章暂时不会进行实例解析，只提供模板，目的是以最快的速度给这些友友们提供尽可能的帮助！

1、堆排序

// 堆排序额外空间复杂度O(1)publicstaticvoidheapSort(int[] arr){if(arr == null || arr.length <2){return;}// O(N*logN)//        for (int i = 0; i < arr.length; i++) { // O(N)//            heapInsert(arr, i); // O(logN)//        }// O(N)for(int i = arr.length -1; i >=0; i--){heapify(arr, i, arr.length);}int heapSize = arr.length;swap(arr,0,--heapSize);// O(N*logN)while(heapSize >0){// O(N)heapify(arr,0, heapSize);// O(logN)swap(arr,0,--heapSize);// O(1)}}// arr[index]刚来的数，往上publicstaticvoidheapInsert(int[] arr,int index){while(arr[index]> arr[(index -1)/2]){swap(arr, index,(index -1)/2);
            index =(index -1)/2;}}// arr[index]位置的数，能否往下移动publicstaticvoidheapify(int[] arr,int index,int heapSize){int left = index *2+1;// 左孩子的下标while(left < heapSize){// 下方还有孩子的时候// 两个孩子中，谁的值大，把下标给largest// 1）只有左孩子，left -> largest// 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest// 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largestint largest = left +1< heapSize && arr[left +1]> arr[left]? left +1: left;// 父和较大的孩子之间，谁的值大，把下标给largest
            largest = arr[largest]> arr[index]? largest : index;if(largest == index){break;}swap(arr, largest, index);
            index = largest;
            left = index *2+1;}}publicstaticvoidswap(int[] arr,int i,int j){int tmp = arr[i];
        arr[i]= arr[j];
        arr[j]= tmp;}

2、归并排序

// 递归方法实现publicstaticvoidmergeSort1(int[] arr){if(arr == null || arr.length <2){return;}process(arr,0, arr.length -1);}// 请把arr[L..R]排有序// l...r N// T(N) = 2 * T(N / 2) + O(N)// O(N * logN)publicstaticvoidprocess(int[] arr,int L,int R){if(L == R){// base casereturn;}int mid = L +((R - L)>>1);process(arr, L, mid);process(arr, mid +1, R);merge(arr, L, mid, R);}publicstaticvoidmerge(int[] arr,int L,int M,int R){int[] help =newint[R - L +1];int i =0;int p1 = L;int p2 = M +1;while(p1 <= M && p2 <= R){
            help[i++]= arr[p1]<= arr[p2]? arr[p1++]: arr[p2++];}// 要么p1越界了，要么p2越界了while(p1 <= M){
            help[i++]= arr[p1++];}while(p2 <= R){
            help[i++]= arr[p2++];}for(i =0; i < help.length; i++){
            arr[L + i]= help[i];}}// 非递归方法实现publicstaticvoidmergeSort2(int[] arr){if(arr == null || arr.length <2){return;}int N = arr.length;// 步长int mergeSize =1;while(mergeSize < N){// log N// 当前左组的，第一个位置int L =0;while(L < N){if(mergeSize >= N - L){break;}int M = L + mergeSize -1;int R = M + Math.min(mergeSize, N - M -1);merge(arr, L, M, R);
                L = R +1;}// 防止溢出if(mergeSize > N /2){break;}
            mergeSize <<=1;}}

3、由归并排序衍生出来的小和问题

publicstaticintsmallSum(int[] arr){if(arr == null || arr.length <2){return0;}returnprocess(arr,0, arr.length -1);}// arr[L..R]既要排好序，也要求小和返回// 所有merge时，产生的小和，累加// 左 排序   merge// 右 排序  merge// mergepublicstaticintprocess(int[] arr,int l,int r){if(l == r){return0;}// l < rint mid = l +((r - l)>>1);returnprocess(arr, l, mid)+process(arr, mid +1, r)+merge(arr, l, mid, r);}publicstaticintmerge(int[] arr,int L,int m,int r){int[] help =newint[r - L +1];int i =0;int p1 = L;int p2 = m +1;int res =0;while(p1 <= m && p2 <= r){
            res += arr[p1]< arr[p2]?(r - p2 +1)* arr[p1]:0;
            help[i++]= arr[p1]< arr[p2]? arr[p1++]: arr[p2++];}while(p1 <= m){
            help[i++]= arr[p1++];}while(p2 <= r){
            help[i++]= arr[p2++];}for(i =0; i < help.length; i++){
            arr[L + i]= help[i];}return res;}

4、由归并排序衍生出来的逆序对问题

publicstaticintreverPairNumber(int[] arr){if(arr == null || arr.length <2){return0;}returnprocess(arr,0, arr.length -1);}// arr[L..R]既要排好序，也要求逆序对数量返回// 所有merge时，产生的逆序对数量，累加，返回// 左 排序 merge并产生逆序对数量// 右 排序 merge并产生逆序对数量publicstaticintprocess(int[] arr,int l,int r){if(l == r){return0;}// l < rint mid = l +((r - l)>>1);returnprocess(arr, l, mid)+process(arr, mid +1, r)+merge(arr, l, mid, r);}publicstaticintmerge(int[] arr,int L,int m,int r){int[] help =newint[r - L +1];int i = help.length -1;int p1 = m;int p2 = r;int res =0;while(p1 >= L && p2 > m){
            res += arr[p1]> arr[p2]?(p2 - m):0;
            help[i--]= arr[p1]> arr[p2]? arr[p1--]: arr[p2--];}while(p1 >= L){
            help[i--]= arr[p1--];}while(p2 > m){
            help[i--]= arr[p2--];}for(i =0; i < help.length; i++){
            arr[L + i]= help[i];}return res;}

5、两个队列实现栈

publicstaticclassTwoQueueStack<T>{public Queue<T> queue;public Queue<T> help;publicTwoQueueStack(){
            queue =newLinkedList<>();
            help =newLinkedList<>();}publicvoidpush(T value){
            queue.offer(value);}public T poll(){while(queue.size()>1){
                help.offer(queue.poll());}
            T ans = queue.poll();
            Queue<T> tmp = queue;
            queue = help;
            help = tmp;return ans;}public T peek(){while(queue.size()>1){
                help.offer(queue.poll());}
            T ans = queue.poll();
            help.offer(ans);
            Queue<T> tmp = queue;
            queue = help;
            help = tmp;return ans;}publicbooleanisEmpty(){return queue.isEmpty();}}

6、两个栈实现队列

publicstaticclassTwoStacksQueue{public Stack<Integer> stackPush;public Stack<Integer> stackPop;publicTwoStacksQueue(){
            stackPush =newStack<Integer>();
            stackPop =newStack<Integer>();}// push栈向pop栈倒入数据privatevoidpushToPop(){if(stackPop.empty()){while(!stackPush.empty()){
                    stackPop.push(stackPush.pop());}}}publicvoidadd(int pushInt){
            stackPush.push(pushInt);pushToPop();}publicintpoll(){if(stackPop.empty()&& stackPush.empty()){thrownewRuntimeException("Queue is empty!");}pushToPop();return stackPop.pop();}publicintpeek(){if(stackPop.empty()&& stackPush.empty()){thrownewRuntimeException("Queue is empty!");}pushToPop();return stackPop.peek();}}