左神直通BAT算法笔记（基础篇）-上

Anwen
8,153 阅读1小时+

个人技术博客：www.zhenganwen.top

时间复杂度

时间复杂度是衡量算法好坏的重要指标之一。时间复杂度反映的是不确定性样本量的增长对于算法操作所需时间的影响程度，与算法操作是否涉及到样本量以及涉及了几次直接相关，如遍历数组时时间复杂度为数组长度n（对应时间复杂度为O(n)），而对数据的元操作（如加减乘除与或非等）、逻辑操作（如if判断）等都属于常数时间内的操作（对应时间复杂度O(1)）。

在化简某算法时间复杂度表达式时需遵循以下规则：

  • 对于同一样本量，可省去低阶次数项，仅保留高阶次数项，如O(n^2)+O(n)可化简为O(n^2)，O(n)+O(1)可化简为O(n)
  • 可省去样本量前的常量系数，如O(2n)可化简为O(n)，O(8)可化简为O(1)
  • 对于不同的不确定性样本量，不能按照上述两个规则进行化简，要根据实际样本量的大小分析表达式增量。如O(logm)+O(n^2)不能化简为O(n^2)或O(logm)。而要视m、n两者之间的差距来化简，比如m>>n时可以化简为O(logm)，因为表达式增量是由样本量决定的。

额外空间复杂度

算法额外空间复杂度指的是对于输入样本，经过算法操作需要的额外空间。比如使用冒泡排序对一个数组排序，期间只需要一个临时变量temp，那么该算法的额外空间复杂度为O(1)。又如归并排序，在排序过程中需要创建一个与样本数组相同大小的辅助数组，尽管在排序过后该数组被销毁，但该算法的额外空间复杂度为O(n)。

经典例题——举一反三

找出B中不属于A的数

找出数组B中不属于A的数，数组A有序而数组B无序。假设数组A有n个数，数组B有m个数，写出算法并分析时间复杂度。

方法一：遍历

首先遍历B，将B中的每个数拿到到A中找，若找到则打印。对应算法如下：

int A[] = {1, 2, 3, 4, 5};
int B[] = {1, 4, 2, 6, 5, 7};

for (int i = 0; i < 6; ++i) {
  int temp = B[i];
  bool flag = false;
  for (int j = 0; j < 5; ++j) {
    if (A[j] == temp) {
      flag = true;    //找到了
      break;
    }
  }
  if (!flag) {    //没找到
    printf("%d", temp);
  }
}

不难看出上述算法的时间复杂度为O(m*n)，因为将两个数组都遍历了一遍

方法二：二分查找

由于数组A是有序的，在一个有序序列中查找一个元素可以使用二分法（也称折半法）。原理就是将查找的元素与序列的中位数进行比较，如果小于则去掉中位数及其之后的序列，如果大于则去掉中位数及其之前的序列，如果等于则找到了。如果不等于那么再将其与剩下的序列继续比较直到找到或剩下的序列为空为止。

利用二分法对应题解的代码如下：

for (int i = 0; i < 6; ++i) {		//B的长度为6
  int temp = B[i];
  //二分法查找
  int left = 0,right = 5-1;			//A的长度为5
  int mid = (left + right) / 2;
  while (left < right && A[mid] != temp) {
    if (A[mid] > temp) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
    mid = (left + right) / 2;
  }
  if (A[mid] != temp) {
    printf("%d", temp);
  }
}

for循环m次，while循环logn次（如果没有特别说明，log均以2为底），此算法的时间复杂度为O(mlogn)

方法三：排序+外排

第三种方法就是将数组B也排序，然后使用逐次比对的方式来查找A数组中是否含有B数组中的某元素。引入a、b两个指针分别指向数组A、B的首元素，比较指针指向的元素值，当a<b时，向后移动a指针查找该元素；当a=b时，说明A中存在该元素，跳过该元素查找，向后移动b；当a>b时说明A中不存在该元素，打印该元素并跳过该元素的查找，向后移动b。直到a或b有一个到达数组末尾为止（若a先到达末尾，那么b和b之后的数都不属于A）

对应题解的代码如下：

void fun3(int A[],int a_length,int B[],int b_length){
    quickSort(B, 0, b_length - 1);	//使用快速排序法对数组B排序->O(mlogm)
    int* a = A,*b=B;
    while (a <= A + a_length - 1 || b <= B + b_length - 1) {
        if (*a == *b) {
            b++;
            continue;
        }
        if (*a > *b) {
            printf("%d", *b);
            b++;
        } else {
            a++;
        }
    }

    if (a == A + a_length) {	//a先到头
        while (b < B + b_length) {
            printf("%d", *b);
            b++;
        }
    }
}

快速排序的代码如下：

#include <stdlib.h>
#include <time.h>

//交换两个int变量的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//产生一个low~high之间的随机数
int randomInRange(int low, int high){
    srand((int) time(0));
    return (rand() % (high - low))+low;
}

//快速排序的核心算法，随机选择一个数，将比该数小的移至数组左边，比该数大的移至
//数组右边，最后返回该数的下标（移动完之后该数的下标可能与移动之前不一样）
int partition(int arr[],int start,int end){
    if (arr == NULL || start < 0 || end <= 0 || start > end) {
        return -1;
    }

    int index = randomInRange(start, end);//随机选择一个数
    swap(arr[index], arr[end]);//将该数暂时放至末尾

    int small = start - 1;
    //遍历前n-1个数与该数比较并以该数为界限将前n-1个数
    //分为两组，small指向小于该数的那一组的最后一个元素
    for (index = start; index < end; index++) {
        if (arr[index] < arr[end]) {
            small++;
            if (small != index) {
                swap(arr[small], arr[index]);
            }
        }
    }

    //最后将该数放至数值较小的那一个组的中间
    ++small;
    swap(arr[small], arr[end]);
    return small;
}

void quickSort(int arr[],int start,int end) {
    if (start == end) {
        return;
    }
    int index = partition(arr, start, end);
    if (index > start) {
        quickSort(arr,start, index - 1);
    }
    if (index < end) {
        quickSort(arr, index + 1, end);
    }
}

此种方法的时间复杂度为：O(mlogm)（先对B排序）+O(m+n)（最坏的情况是指针a和b都到头）。

三种方法的比较

  1. O(m*n)
  2. O(mlogn)（以2为底）
  3. O(mlogm)+O(m+n)（以2为底）

易知算法2比1更优，因为增长率logn<n。而2和3的比较取决于样本量m和n之间的差距，若m>>n那么2更优，不难理解：数组B元素较多，那么对B的排序肯定要花费较长时间，而这一步并不是题解所必需的，不如采用二分法；相反地，若m<<n，那么3更优。

荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)

思路：利用两个指针L、R，将L指向首元素之前，将R指向尾元素之后。从头遍历序列，将当前遍历元素与num比较，若num，则将其与L的右一个元素交换位置并遍历下一个元素、右移L；若=num则直接遍历下一个元素；若>num则将其和R的左一个元素交换位置，并重新判断当前位置元素与num的关系。直到遍历的元素下标到为R-1为止。

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}
void partition(int arr[],int startIndex,int endIndex,int num){
    int L = startIndex - 1, R = endIndex + 1, i = startIndex;
    while (i <= R - 1) {
        if (arr[i] < num) {
            swap(arr[i++], arr[++L]);
        } else if (arr[i] > num) {
            swap(arr[i], arr[--R]);
        } else {
            i++;
        }
    }
}

int main(){
    int arr[] = {1,2, 1, 5, 4, 7, 2, 3, 9,1};
    travles(arr, 8);
    partition(arr, 0, 7, 2);
    travles(arr, 8);
    return 0;
}

L代表小于num的数的右界，R代表大于num的左界，partition的过程就是遍历元素、不断壮大L、R范围的过程。这里比较难理解的地方可能是为什么arr[i]<num时要右移L而arr[i]>num时却不左移R，这是因为对于当前元素arr[i]，如果arr[i]<num进行swap(arr[i],arr[L+1])之后对于当前下标的数据状况是知晓的（一定有arr[i]=arr[L+1]），因为是从头遍历到i的，而L+1<=i。但是如果arr[i]>num进行swap(arr[i],arr[R-1])之后对于当前元素的数据状况是不清楚的，因为R-1>=i，arr[R-1]还没遍历到。

矩阵打印问题

转圈打印方块矩阵

给定一个4阶矩阵如下：

打印结果如下（要求额外空间复杂度为O(1)）：

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

思路：这类问题需要将思维打开，从宏观的层面去找出问题存在的共性从而求解。如果你的思维局限在1是如何变到2的、4是怎么变到8的、11之后为什么时10、它们之间有什么关联，那么你就陷入死胡同了。

从宏观的层面找共性，其实转圈打印的过程就是不断顺时针打印外围元素的过程，只要给你一个左上角的点（如(0,0)）和右下角的点（如(3,3)），你就能够打印出1 2 3 4 8 12 16 15 14 13 9 5；同样，给你(1,1)和(2,2)，你就能打印出6 7 11 10。这个根据两点打印正方形上元素的过程可以抽取出来，整个问题也就迎刃而解了。

打印一个矩阵某个正方形上的点的逻辑如下：

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#define FACTORIAL 4

void printSquare(int leftUp[], int rigthDown[],int matrix[][FACTORIAL]){
    int i = leftUp[0], j = leftUp[1];
    while (j < rigthDown[1]) {
        printf("%d ", matrix[i][j++]);
    }
    while (i < rigthDown[0]) {
        printf("%d ", matrix[i++][j]);
    }
    while (j > leftUp[1]) {
        printf("%d ", matrix[i][j--]);
    }
    while (i > leftUp[0]) {
        printf("%d ", matrix[i--][j]);
    }
}

void printMatrixCircled(int matrix[][FACTORIAL]){
    int leftUp[] = {0, 0}, rightDown[] = {FACTORIAL-1,FACTORIAL-1};
    while (leftUp[0] < rightDown[0] && leftUp[1] < rightDown[1]) {
        printSquare(leftUp, rightDown, matrix);
        ++leftUp[0];
        ++leftUp[1];
        --rightDown[0];
        --rightDown[1];
    }
}

int main(){
    int matrix[4][4] = {
            {1,  2,  3,  4},
            {5,  6,  7,  8},
            {9,  10, 11, 12},
            {13, 14, 15, 16}
    };
    printMatrixCircled(matrix);//1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
}

旋转方块矩阵

给定一个方块矩阵，请把该矩阵调整成顺时针旋转90°之后的样子，要求额外空间复杂度为O(1)。

思路：拿上图举例，首先选取矩阵四个角上的点1,3,9,7，按顺时针的方向1到3的位置（1->3）、3->9、9->7、7->1，这样对于旋转后的矩阵而言，这四个点已经调整好了。接下来只需调整2,6,8,4的位置，调整方法是一样的。只需对矩阵第一行的前n-1个点采用同样的方法进行调整、对矩阵第二行的前前n-3个点……，那么调整n阶矩阵就容易了。

这也是在宏观上观察数据变动的一般规律，找到以不变应万变的通解（给定一个点，确定矩阵上以该点为角的正方形，将该正方形旋转90°），整个问题就不攻自破了。

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#define FACTORIAL 4

void circleSquare(int leftUp[],int rightDown[],int matrix[][FACTORIAL]){
    int p1[] = {leftUp[0], leftUp[1]};
    int p2[] = {leftUp[0], rightDown[1]};
    int p3[] = {rightDown[0], rightDown[1]};
    int p4[] = {rightDown[0],leftUp[1]};
    while (p1[1] < rightDown[1]) {
        //swap
        int tmp = matrix[p4[0]][p4[1]];
        matrix[p4[0]][p4[1]] = matrix[p3[0]][p3[1]];
        matrix[p3[0]][p3[1]] = matrix[p2[0]][p2[1]];
        matrix[p2[0]][p2[1]] = matrix[p1[0]][p1[1]];
        matrix[p1[0]][p1[1]] = tmp;

        p1[1]++;
        p2[0]++;
        p3[1]--;
        p4[0]--;
    }
}

void circleMatrix(int matrix[][FACTORIAL]){
    int leftUp[] = {0, 0}, rightDown[] = {FACTORIAL - 1, FACTORIAL - 1};
    while (leftUp[0] < rightDown[0] && leftUp[1] < rightDown[1]) {
        circleSquare(leftUp, rightDown, matrix);
        leftUp[0]++;
        leftUp[1]++;
        --rightDown[0];
        --rightDown[1];
    }
}

void printMatrix(int matrix[][FACTORIAL]){
    for (int i = 0; i < FACTORIAL; ++i) {
        for (int j = 0; j < FACTORIAL; ++j) {
            printf("%2d ", matrix[i][j]);
        }
        printf("\n");
    }
}

int main(){
    int matrix[FACTORIAL][FACTORIAL] = {
            {1,  2,  3,  4},
            {5,  6,  7,  8},
            {9,  10, 11, 12},
            {13, 14, 15, 16}
    };
    printMatrix(matrix);
    circleMatrix(matrix);
    printMatrix(matrix);
}

之字形打印矩阵

对如上矩阵的打印结果如下（要求额外空间复杂度为O(1)）：

1 2 7 13 8 3 4 9 14 15 10 5 6 11 16 17 12 18

此题也是需要从宏观上找出一个共性：给你两个，你能否将该两点连成的45°斜线上的点按给定的打印方向打印出来。拿上图举例，给出(2,0)、(0,2)和turnUp=true，应该打印出13,8,3。那么整个问题就变成了两点的走向问题了，开始时两点均为(0,0)，然后一个点往下走，另一个点往右走（如1->7，1->2）；当往下走的点是边界点时就往右走（如13->14），当往右走的点到边界时就往下走（如6->12）。每次两点走一步，并打印两点连线上的点。

//
// Created by zaw on 2018/10/22.
//
#include <stdio.h>

const int rows = 3;
const int cols = 6;

void printLine(int leftDown[],int rightUp[], bool turnUp,int matrix[rows][cols]){
    int i,j;
    if (turnUp) {
        i = leftDown[0], j = leftDown[1];
        while (j <= rightUp[1]) {
            printf("%d ", matrix[i--][j++]);
        }
    } else {
        i = rightUp[0], j = rightUp[1];
        while (i <= leftDown[0]) {
            printf("%d ", matrix[i++][j--]);
        }
    }
}

void zigZagPrintMatrix(int matrix[rows][cols]){
    if (matrix==NULL)
        return;
    int leftDown[] = {0, 0}, rightUp[] = {0, 0};
    bool turnUp = true;
    while (leftDown[1] <= cols - 1) {
        printLine(leftDown, rightUp, turnUp, matrix);
        turnUp = !turnUp;
        if (leftDown[0] < rows - 1) {
            leftDown[0]++;
        } else {
            leftDown[1]++;
        }
        if (rightUp[1] < cols - 1) {
            ++rightUp[1];
        } else {
            ++rightUp[0];
        }
    }
}

int main(){
    int matrix[rows][cols] = {
            {1,  2,  3,  4,  5,  6},
            {7,  8,  9,  10, 11, 12},
            {13, 14, 15, 16, 17, 18}
    };
    zigZagPrintMatrix(matrix);//1 2 7 13 8 3 4 9 14 15 10 5 6 11 16 17 12 18
    return 0;
}

在行和列都排好序的矩阵上找数

如图：

任何一列或一行上的数是有序的，实现一个函数，判断某个数是否存在于矩阵中。要求时间复杂度为O(M+N)，额外空间复杂度为O(1)。

从矩阵右上角的点开始取点与该数比较，如果大于该数，那么说明这个点所在的列都不存在该数，将这个点左移；如果这个点上的数小于该数，那么说明这个点所在的行不存在该数，将这个点下移。直到找到与该数相等的点为止。最坏的情况是，该数只有一个且在矩阵左下角上，那么时间复杂度为O(M-1+N-1)=O(M+N)

//
// Created by zaw on 2018/10/22.
//
#include <stdio.h>
const int rows = 4;
const int cols = 4;

bool findNumInSortedMatrix(int num,int matrix[rows][cols]){
    int i = 0, j = cols - 1;
    while (i <= rows - 1 && j <= cols - 1) {
        if (matrix[i][j] > num) {
            --j;
        } else if (matrix[i][j] < num) {
            ++i;
        } else {
            return true;
        }
    }
    return false;
}

int main(){
    int matrix[rows][cols] = {
            {1, 2, 3, 4},
            {2, 4, 5, 8},
            {3, 6, 7, 9},
            {4, 8, 9, 10}
    };
    if (findNumInSortedMatrix(7, matrix)) {
        printf("find!");
    } else {
        printf("not exist!");
    }
    return 0;
}

岛问题

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？

比如矩阵：

1 0 1
0 1 0
1 1 1

就有3个岛。

分析：我们可以遍历矩阵中的每个位置，如果遇到1就将与其相连的一片1都感染成2，并自增岛数量。

public class IslandNum {
	
	public static int getIslandNums(int matrix[][]){
		int res = 0 ;
		for(int i = 0 ; i < matrix.length ; i++){
			for(int j = 0 ; j < matrix[i].length ; j++){
				if(matrix[i][j] == 1){
					res++;
					infect(matrix , i , j);
				}
			}
		}
		return res;
	}

	public static void infect(int matrix[][], int i ,int j){
		if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[i].length || matrix[i][j] != 1){
			return;
		}
		matrix[i][j] = 2;
		infect(matrix , i-1 , j);
		infect(matrix , i+1 , j);
		infect(matrix , i , j-1);
		infect(matrix , i , j+1);
	}

	public static void main(String[] args){
		int matrix[][] = {
			{1,0,0,1,0,1},
			{0,1,1,0,0,0},
			{1,0,0,0,1,1},
			{1,1,1,1,1,1}
		};
		System.out.println(getIslandNums(matrix));
	}
}

经典结构和算法

字符串

KMP算法

KMP算法是由一个问题而引发的：对于一个字符串str（长度为N）和另一个字符串match（长度为M），如果match是str的子串，请返回其在str第一次出现时的首字母下标，若match不是str的子串则返回-1。

最简单的方法是将str从头开始遍历并与match逐次比较，若碰到了不匹配字母则终止此次遍历转而从str的第二个字符开始遍历并与match逐次比较，直到某一次的遍历每个字符都与match匹配否则返回-1。易知此种做法的时间复杂度为O(N*M)。

KMP算法则给出求解该问题时间复杂度控制在O(N)的解法。

首先该算法需要对应match创建一个与match长度相同的辅助数组help[match.length]，该数组元素表示match某个下标之前的子串的前后缀子串最大匹配长度。前缀子串表示一个串中以串首字符开头的不包含串尾字符的任意个连续字符，后缀子串则表示一个串中以串尾字符结尾的不包括串首字符的任意个连续字符。比如abcd的前缀子串可以是a、ab、abc，但不能是abcd，而abcd的后缀字串可以是d、cd、bcd，但不能是abcd。再来说一下help数组，对于char match[]="abc1abc2"来说，有help[7]=3，因为match[7]='2'，因此match下标在7之前的子串abc1abc的前缀子串和后缀子串相同的情况下，前缀子串的最大长度为3（即前缀字串和后缀字串都取abc）；又如match="aaaab"，有help[4]=3（前缀子串和后缀子串最大匹配长度当两者为aaa时取得），相应的有help[3]=2、help[2]=1。

假设当要寻找的子串match的help数组找到之后（对于一个串的help数组的求法在介绍完KMP算法之后再详细说明）。就可以进行KMP算法求解此问题了。KMP算法的逻辑（结论）是，对于str的i~(i+k)部分（i、i+k均为str的合法下标）和match的0~k部分（k为match的合法下标），如果有str[i]=match[0]、str[i+1]=match[1]……str[i+k-1]=match[k-1]，但str[i+k]!=[k]，那么str的下标不用从i+k变为i+1重新比较，只需将子串str[0]~str[i+k-1]的最大匹配前缀子串的后一个字符cn重新与str[i+k]向后依次比较，后面如果又遇到了不匹配的字符重复此操作即可：

当遇到不匹配字符时，常规的做法是将str的遍历下标sIndex移到i+1的位置并将match的遍历下标mIndex移到0再依次比较，这种做法并没有利用上一轮的比较信息（对下一轮的比较没有任何优化）。而KMP算法则不是这样，当遇到不匹配的字符str[i+k]和match[k]时，str的遍历指针sIndex=i+k不用动，将match右滑并将其遍历指针mIndex打到子串match[0]~match[k-1]的最大匹配前缀子串的后一个下标n的位置。然后sIndex从i+k开始，mIndex从n开始，依次向后比较，若再遇到不匹配的数则重复此过程。

对应代码如下：

void length(char* str){
  if(str==NULL)
    return -1;
  int len=0;
  while(*(str++)!='\0'){
    len++;
  }
  return len;
}

int getIndexOf(char* str,char* m){
    int slen = length(str) , mlen = length(m);
    if(mlen > slen)
        return -1;
    int help[mlen];
    getHelpArr(str,help);
    int i=0,j=0;	//sIndex,mIndex
    while(i < slen && j < mlen){
        if(str[i] == m[j]){
            i++;
            j++;
        }else if(help[j] != -1){
            j = help[j];    //mIndex -> cn's index
        }else{	//the first char is not match,move the sIndex
            i++;    
        }
    }
    return j == mlen ? i - mlen : -1;
}

可以发现KMP算法中str的遍历指针并没有回溯这个动作（只向后移动），当完成匹配时sIndex的移动次数小于N，否则sIndex移动到串尾也会终止循环，所以while对应的匹配过程的时间复杂度为O(N)(if(help[j] != -1){ j = help[j] }的执行次数只会是常数次，因此可以忽略)。

下面只要解决如何求解一个串的help数组，此问题就解决了。help数组要从前到后求解，直接求help[n]是很难有所头绪的。当串match长度mlen=1时，规定help[0]=-1。当mlen=2时，去掉match[1]之后只剩下match[0]，最大匹配子串长度为0（因为前缀子串不能包含串尾字符，后缀子串不能包含串首字符），即help[1]=0。当mlen>2时，help[n]（n>=2）都可以推算出来：

如上图所示，如果我们知道了help[n-1]，那么help[n]的求解有两种情况：如果match[cn]=match[n-1]，那么由a区域与b区域（a、b为子串match[0~n-2]的最大匹配前缀子串和后缀字串）相同可知help[n]=help[n-1]+1；如果match[cn]!=match[n-1]，那么求a区域中下一个能和b区域后缀子串中匹配的较大的一个，即a区域的最大匹配前缀字串c区域，将match[n-1]和c区域的后一个位置（cn'）上的字符比较，如果相等则help[n]等于c区域的长度+1，而c区域的长度就是help[cn]（help数组的定义如此）；如果不等则将cn打到cn'的位置继续和match[n-1]比较，直到cn被打到0为止（即help[cn]=-1为止），那么此时help[n]=0。

对应代码如下：

int* getHelpArr(char* s,int help[]){
    if(s==NULL)
        return NULL;
    int slen = length(s);
    help[0]=-1;
    help[1]=0;
    int index = 2;//help数组从第三个元素开始的元素值需要依次推算
    int cn = 0;		//推算help[2]时，help[1]=0，即s[1]之前的字符组成的串中不存在最大匹配前后子串，那么cn作为最大匹配前缀子串的后一个下标自然就是0了
    while(index < slen){
        if(s[index-1] == s[cn]){	//if match[n-1] == match[cn]
            help[index] = help[index-1] + 1;
            index++;
            cn++;
        }else if(help[cn] == -1){	//cn reach 0
            help[index]=0;
            index++;
            cn++;
        }else{
            cn = help[cn];	//set cn to cn' and continue calculate help[index]
        }
    }
    return help;
}

那么这个求解help数组的过程的时间复杂度如何计算呢？仔细观察克制while循环中仅涉及到index和cn这两个变量的变化：

第一个if分支 第二个if分支 第三个if分支
index 增大 增大 不变
index-cn 不变 不变 增大

可以发现while循环执行一次不是index增大就是index-cn增大，而index < slen、index - cn < slen，即index最多自增M（match串的长度）次 ，index-cn最多增加M次，如此while最多执行M+M次，即时间复杂为O(2M)=O(M)。

综上所述，使用KMP求解此问题的时间复杂度为O(M)（求解match的help数组的时间复杂度）+O(N)（匹配的时间复杂度）=O(N)（因为N > M）。

KMP算法的应用

  1. 判断一个二叉树是否是另一棵二叉树的子树（即某棵树的结构和数据状态和另一棵二叉树的子树样）。

    思路：如果这棵树的序列化串是另一棵树的序列化串的子串，那么前者必定是后者的子树。

前缀树（字典树）

前缀树的介绍

前缀树是一种存储字符串的高效容器，基于此结构的操作有：

  • insert插入一个字符串到容器中

  • search容器中是否存在某字符串，返回该字符串进入到容器的次数，没有则返回0

  • delete将某个字符串进入到容器的次数减1

  • prefixNumber返回所有插入操作中，以某个串为前缀的字符串出现的次数

设计思路：该结构的重点实现在于存储。前缀树以字符为存储单位，将其存储在结点之间的树枝上而非结点上，如插入字符串abc之后前缀树如下：

每次插入串都要从头结点开始，遍历串中的字符依次向下“铺路”，如上图中的abc3条路。对于每个结点而言，它可以向下铺a~z26条不同的路，假如来到某个结点后，它要向下铺的路（取决于遍历到哪个字符来了）被之前插入串的过程铺过了那么就可以直接走这条路去往下一个结点，否则就要先铺路再去往下一个结点。如再插入串abde和bcd的前缀树将如下所示：

根据前缀树的search和prefixNumber两个操作，我们还需要在每次铺路后记录以下每个结点经过的次数（across），以及每次插入操作每个结点作为终点结点的次数（end）。

前缀树的实现

前缀树的实现示例：

public class TrieTree {

  public static class TrieNode {
    public int across;
    public int end;
    public TrieNode[] paths;

    public TrieNode() {
      super();
      across = 0;
      end = 0;
      paths = new TrieNode[26];
    }
  }

  private TrieNode root;

  public TrieTree() {
    super();
    root = new TrieNode();
  }

  //向树中插入一个字符串
  public void insert(String str) {
    if (str == null || str.length() == 0) {
      return;
    }
    char chs[] = str.toCharArray();
    TrieNode cur = root;
    for (char ch : chs) {
      int index = ch - 'a';
      if (cur.paths[index] == null) {
        cur.paths[index] = new TrieNode();
      }
      cur = cur.paths[index];
      cur.across++;
    }
    cur.end++;
  }

  //查询某个字符串插入的次数
  public int search(String str) {
    if (str == null || str.length() == 0) {
      return 0;
    }
    char chs[] = str.toCharArray();
    TrieNode cur = root;
    for (char ch : chs) {
      int index = ch - 'a';
      if (cur.paths[index] == null) {
        return 0;
      }else{
        cur = cur.paths[index];
      }
    }
    return cur.end;
  }

  //删除一次插入过的某个字符串
  public void delete(String str) {
    if (search(str) > 0) {
      char chs[] = str.toCharArray();
      TrieNode cur = root;
      for (char ch : chs) {
        int index = ch - 'a';
        if (--cur.paths[index].across == 0) {
          cur.paths[index] = null;
          return;
        }
        cur = cur.paths[index];
      }
      cur.end--;
    }
  }

	//查询所有插入的字符串中，以prefix为前缀的有多少个
  public int prefixNumber(String prefix) {
    if (prefix == null || prefix.length() == 0) {
      return 0;
    }
    char chs[] = prefix.toCharArray();
    TrieNode cur = root;
    for (char ch : chs) {
      int index = ch - 'a';
      if (cur.paths[index] == null) {
        return 0;
      }else{
        cur = cur.paths[index];
      }
    }
    return cur.across;
  }

  public static void main(String[] args) {
    TrieTree tree = new TrieTree();
    tree.insert("abc");
    tree.insert("abde");
    tree.insert("bcd");
    System.out.println(tree.search("abc"));	//1
    System.out.println(tree.prefixNumber("ab"));	//2
  }
}

前缀树的相关问题

一个字符串类型的数组arr1，另一个字符串类型的数组arr2：

  • arr2中有哪些字符，是arr1中出现的？请打印
  • arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印
  • arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印arr2中出现次数最大的前缀。

数组

冒泡排序

冒泡排序的核心是从头遍历序列。以升序排列为例：将第一个元素和第二个元素比较，若前者大于后者，则交换两者的位置，再将第二个元素与第三个元素比较，若前者大于后者则交换两者位置，以此类推直到倒数第二个元素与最后一个元素比较，若前者大于后者，则交换两者位置。这样一轮比较下来将会把序列中最大的元素移至序列末尾，这样就安排好了最大数的位置，接下来只需对剩下的（n-1）个元素，重复上述操作即可。

void swap(int *a, int *b){
  int temp = *a;
  *a = *b;
  *b = temp;
}

void bubbleSort(int arr[], int length) {
  if(arr==NULL || length<=1){
    return;
  }
  for (int i = length-1; i > 0; i--) {	//只需比较(length-1)轮
    for (int j = 0; j < i; ++j) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }
}

该算法的时间复杂度为n+(n-1)+...+1，很明显是一个等差数列，由（首项+末项）*项数/2求其和为(n+1)n/2，可知时间复杂度为O(n^2)

选择排序

以升序排序为例：找到最小数的下标minIndex，将其与第一个数交换，接着对子序列（1-n）重复该操作，直到子序列只含一个元素为止。(即选出最小的数放到第一个位置，该数安排好了，再对剩下的数选出最小的放到第二个位置，以此类推）

void selectionSort(int arr[], int length) {
  for (int i = 0; i < length-1; ++i) {    //要进行n-1次选择，选出n-1个数分别放在前n-1个位置上
    if(arr==NULL || length<=1){
      return;
    }
    int minIndex = i;	//记录较小数的下标
    for (int j = i+1; j < length; ++j) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    if (minIndex != i) {
      swap(&arr[minIndex],&arr[i]);
    }
  }
}

同样，不难得出该算法的时间复杂度（big o）为O(n^2)（n-1+n-2+n-3+…+1）

插入排序

插入排序的过程可以联想到打扑克时揭一张牌然后将其到手中有序纸牌的合适位置上。比如我现在手上的牌是7、8、9、J、Q、K，这时揭了一张10，我需要将其依次与K、Q、J、9、8、7比较，当比到9时发现大于9，于是将其插入到9之后。对于一个无序序列，可以将其当做一摞待揭的牌，首先将首元素揭起来，因为揭之前手上无牌，因此此次揭牌无需比较，此后每揭一次牌都需要进行上述的插牌过程，当揭完之后，手上的握牌顺序就对应着该序列的有序形式。

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void insertionSort(int arr[], int length){
    if(arr==NULL || length<=1){
        return;
    }
    for (int i = 1; i < length; ++i) {		//第一张牌无需插入，直接入手，后续揭牌需比较然后插入，因此从第二个元素开始遍历（插牌）
      	//将新揭的牌与手上的逐次比较，若小于则交换，否则停止，比较完了还没遇到更小的也停止
        for (int j = i - 1; j >= 0 || arr[j] <= arr[j + 1]; j--) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

插入排序的big o该如何计算？可以发现如果序列有序，那么该算法的big o为O(n)，因为只是遍历了一次序列（这时最好情况）；如果序列降序排列，那么该算法的big o为O(n^2)（每次插入前的比较交换加起来要：1+2+…+n-1）（最坏情况）。**一般应用场景中都是按算法的最坏情况来考量算法的效率的，因为你做出来的应用要能够承受最坏情况。**即该算法的big o为O(n^2)

归并排序

归并排序的核心思想是先让序列的左半部分有序、再让序列的右半部分有序，最后从两个子序列（左右两半）从头开始逐次比较，往辅助序列中填较小的数。

以序列{2,1,4,3}为例，归并排序的过程大致如下：

算法代码示例：

void merge(int arr[],int helpArr[], int startIndex, int midIndex,int endIndex) {
    int L = startIndex, R = midIndex + 1, i = startIndex;
    while (L <= midIndex && R <= endIndex) { //只要没有指针没越界就逐次比较
        helpArr[i++] = arr[L] < arr[R] ? arr[L++] : arr[R++];
    }
    while (L != midIndex + 1) {
        helpArr[i++] = arr[L++];
    }
    while (R != endIndex + 1) {
        helpArr[i++] = arr[R++];
    }
    for (i = startIndex; i <= endIndex; i++) {
        arr[i] = helpArr[i];
    }
}

void mergeSort(int arr[],int helpArr[], int startIndex, int endIndex) {
    int midIndex;
    if (startIndex < endIndex) {  //当子序列只含一个元素时，不再进行此子过程
      	//(endIndex+startIndex)/2可能会导致int溢出，下面求中位数的做法更安全
        midIndex = startIndex + ((endIndex - startIndex) >> 1);
        mergeSort(arr, helpArr, startIndex, midIndex);        //对左半部分排序
        mergeSort(arr, helpArr, midIndex + 1, endIndex);      //对右半部分排序
        merge(arr, helpArr, startIndex, midIndex, endIndex);  //使整体有序
    }
}

int main(){
    int arr[] = {9, 1, 3, 4, 7, 6, 5};
    travels(arr, 7);//遍历打印
    int helpArr[7];
    mergeSort(arr, helpArr, 0, 7);
    travels(arr, 7);

    return 0;
}

此算法的核心就是第24、25、26这三行。第26行应该不难理解，就是使用两个指针L、R外加一个辅助数组，将两个序列有序地并入辅助数组。但为什么24、25行执行过后数组左右两半部分就分别有序了呢？这就又牵扯到了归并排序的核心思想：先让一个序列左右两半部分有序，然后再并入使整体有序。因此24、25是对左右两半部分分别递归执行归并排序，直到某次递归时左右两半部分均为一个元素时递归终止。当一个序列只含两个元素时，调用mergeSort会发现24、25行是无效操作，直接执行merge。就像上图所示，两行递归完毕后，左右两半部分都会变得有序。

当一个递归过程比较复杂时（不像递归求阶乘那样一幕了然），我们可以列举简短样本进行分析。

对于这样复杂的递归行为，千万不要想着追溯整个递归过程，只需分析第一步要做的事（比如此例中第一步要做的是就是mergeSort函数所呈现出来的那样：对左半部分排序、对右半部分排序、最后并入，你先不管是怎么排序的，不要被24、25行的mergeSort给带进去了）和递归终止的条件（比如此例中是``startIndex>=endIndex`，即要排序的序列只有一个元素时）。

归并排序的时间复杂度是O(nlogn)，额外空间复杂度是O(n)。

根据Master公式（本文 小技巧一节中有讲到）可得T(n)=2T(n/2)+O(n)，第一个2的含义是子过程（对子序列进行归并排序）要执行两次，第二个2的含义是子过程样本量占一半（因为分成了左右两半部分），最后O(n)表示左右有序之后进行的并入操作为O(n+n)=O(n)(L、R指针移动次数总和为n，将辅助数组覆盖源数组为n)，符合T(n)=aT(n/b)+O(n^d)，经计算该算法的时间复杂度为O(nlogn)

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。例如：

对于数组[1,3,4,2,5]
1左边比1小的数，没有；
3左边比3小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2=16

简单的做法就是遍历一遍数组，将当前遍历的数与该数之前数比较并记录小于该数的数。易知其时间复杂度为O(n^2)（0+1+2+……+n-1）。

更优化的做法是利用归并排序的并入逻辑：

对应代码：

int merge(int arr[],int helpArr[], int startIndex, int midIndex,int endIndex) {
    int L = startIndex, R = midIndex + 1, i = startIndex;
    int res=0;
    while (L <= midIndex && R <= endIndex ) { //只要没有指针没越界就逐次比较
        res += arr[L] < arr[R] ? arr[L] * (endIndex - R + 1) : 0;
        helpArr[i++] = arr[L] < arr[R] ? arr[L++] : arr[R++];
    }
    while (L != midIndex + 1) {
        helpArr[i++] = arr[L++];
    }
    while (R != endIndex + 1) {
        helpArr[i++] = arr[R++];
    }
    for (i = startIndex; i <= endIndex; i++) {
        arr[i] = helpArr[i];
    }
    return res;
}

int mergeSort(int arr[],int helpArr[], int startIndex, int endIndex) {
    int midIndex;
    if (startIndex < endIndex) {  //当子序列只含一个元素时，不再进行此子过程
        midIndex = startIndex + ((endIndex - startIndex) >> 1);
        return mergeSort(arr, helpArr, startIndex, midIndex) +        //对左半部分排序
               mergeSort(arr, helpArr, midIndex + 1, endIndex) +     //对右半部分排序
               merge(arr, helpArr, startIndex, midIndex, endIndex);  //使整体有序
    }
    return 0;	//一个元素时不存在小和
}

int main(){
    int arr[] = {1,3,4,2,5};
    int helpArr[5];
    printf("small_sum:%d\n",mergeSort(arr, helpArr, 0, 4)) ;
    return 0;
}

该算法在归并排序的基础上做了略微改动，即merge中添加了变量res记录每次并入操作应该累加的小和、mergeSort则将每次并入应该累加的小和汇总。此种做法的复杂度与归并排序的相同，优于遍历的做法。可以理解，依次求每个数的小和过程中有很多比较是重复的，而利用归并排序求小和时利用了并入的两个序列分别有序的特性省去了不必要的比较，如134并入25时，2>1直接推出2后面的数都>1，因此直接1*(endIndex-indexOf(2)+1)即可。这在样本量不大的情况下看不出来优化的效果，试想一下如果样本量为2^32，那么依照前者求小和O(n^2)可知时间复杂度为O(21亿的平方)，而归并排序求小和则只需O(21亿*32)，足以见得O(n^2)和O(nlogn)的优劣。

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对。

这题的思路也可以利用归并排序来解决，在并入操作时记录arr[L]>arr[R]的情况即可。

快速排序

经典快排

经典快排就是将序列中比尾元素小的移动到序列左边，比尾元素大的移动到序列右边，对以该元素为界的左右两个子序列（均不包括该元素）重复此操作。

首先我们要考虑的是对给定的一个数，如何将序列中比该数小的移动到左边，比该数大的移动到右边。

思路：利用一个辅助指针small，代表较小数的右边界（初始指向首元素前一个位置），遍历序列每次遇到比该数小的数就将其与arr[small+1]交换并右移small，最后将该数与arr[small+1]交换即达到目的。对应算法如下：

void partition(int arr[], int startIndex, int endIndex){
    int small = startIndex - 1;
    for (int i = startIndex; i < endIndex; ++i) {
        if(arr[i] < arr[endIndex]) {
            if (small + 1 != i) {
                swap(arr[++small], arr[i]);
            } else {
                //如果small、i相邻则不用交换
                small++;
            }
        }
    }
    swap(arr[++small], arr[endIndex]);
}
int main(){
    int arr[] = {1, 2, 3, 4, 6, 7, 8, 5};
    travles(arr, 8);//1 2 3 4 6 7 8 5
    partition(arr, 0, 7);
    travles(arr, 8);//1 2 3 4 5 7 8 6
    return 0;
}

接着就是快排的递归逻辑：对1 2 3 4 6 7 8 5序列partition之后，去除之前的比较参数5，对剩下的子序列1234和786继续partition，直到子序列为一个元素为止：

int partition(int arr[], int startIndex, int endIndex){
    int small = startIndex - 1;
    for (int i = startIndex; i < endIndex; ++i) {
        if(arr[i] < arr[endIndex]) {
            if (small + 1 != i) {
                swap(arr[++small], arr[i]);
            } else {
                //如果small、i相邻则不用交换
                small++;
            }
        }
    }
    swap(arr[++small], arr[endIndex]);
    return small;
}

void quickSort(int arr[], int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return;
    }
    int index = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, index - 1);
    quickSort(arr, index + 1, endIndex);
}
int main(){
    int arr[] = {1, 5, 6, 2, 7, 3, 8, 0};
    travles(arr, 8);	//1 5 6 2 7 3 8 0
    quickSort(arr, 0,7);
    travles(arr, 8);	//0 1 2 3 5 6 7 8
    return 0;
}

经典排序的时间复杂度与数据状况有关，如果每一次partition时，尾元素都是序列中最大或最小的，那么去除该元素序列并未如我们划分为样本量相同的左右两个子序列，而是只安排好了一个元素（就是去掉的那个元素），这样的话时间复杂度就是O(n-1+n-2+……+1)=O(n^2)；但如果每一次partition时，都将序列分成了两个样本量相差无几的左右两个子序列，那么时间复杂度就是O(nlogn)（使用Master公式求解）。

由荷兰国旗问题引发对经典快排的改进

可以发现这里partition的过程与荷兰国旗问题中的partition十分相似，能否以后者的partition实现经典快排呢？我们来试一下：

int* partition(int arr[], int startIndex, int endIndex){ ;
    int small = startIndex - 1, great = endIndex + 1, i = startIndex;
    while (i <= great - 1) {
        if (arr[i] < arr[endIndex]) {
            swap(arr[++small], arr[i++]);
        } else if (arr[i] > arr[endIndex]){
            swap(arr[--great], arr[i]);
        } else {
            i++;
        }
    }
    int range[] = {small, great};
    return range;
}

void quickSort(int arr[], int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return;
    }
    int* range = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, range[0]);
    quickSort(arr, range[1], endIndex);
}

int main(){
    int arr[] = {1, 5, 6, 2, 7, 3, 8, 0};
    travles(arr, 8);	//1 5 6 2 7 3 8 0
    quickSort(arr, 0,7);
    travles(arr, 8);	//0 1 2 3 5 6 7 8
    return 0;
}

比较一下经典排序和使用荷兰国旗问题改进后的经典排序，不难发现，后者一次partition能去除一个以上的元素（等于arr[endIndex]的区域），而前者每次partition只能去除一个元素，这里的去除相当于安排（排序）好了对应元素的位置。因此后者比经典排序更优，但是优化不大，只是常数时间内的优化，实质上的效率还是要看数据状况（最后的情况为O(nlogn)，最坏的情况为O(n^2)）。

随机快排——O(nlogn)

上面谈到了快排的短板是依赖数据状况，那么我们有没有办法消除这个依赖，让他成为真正的O(nlogn)呢？

事实上，为了让算法中的操作不依托于数据状况（如快排中每一次partition取尾元素作为比较，这就没有规避样本的数据状况，如果尾元素是最大或最小值就成了最坏情况）常常有两种做法：

1、使用随机取数

2、将样本数据哈希打乱

随机快排就是采用上了上述第一种解决方案，在每一轮的partition中随机选择序列中的一个数作为要比较的数：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//产生[startIndex,endIndex]之间的随机整数
int randomInRange(int startIndex,int endIndex){
    return rand() % (endIndex - startIndex + 1) + startIndex;
}

int* partition(int arr[], int startIndex, int endIndex){ ;
    int small = startIndex - 1, great = endIndex + 1, i = startIndex;
    int randomNum = arr[randomInRange(startIndex, endIndex)];
    while (i <= great - 1) {
        if (arr[i] < randomNum) {
            swap(arr[++small], arr[i++]);
        } else if (arr[i] > randomNum){
            swap(arr[--great], arr[i]);
        } else {
            i++;
        }
    }
    int range[] = {small, great};
    return range;
}

void quickSort(int arr[], int startIndex, int endIndex) {
    if (startIndex > endIndex) {
        return;
    }
    int* range = partition(arr, startIndex, endIndex);
    quickSort(arr, startIndex, range[0]);
    quickSort(arr, range[1], endIndex);
}

void travles(int dataArr[], int length){
    for (int i = 0; i < length; ++i) {
        printf("%d ", dataArr[i]);
    }
    printf("\n");
}

int main(){
    srand(time(NULL));//此后调用rand()时将以调用时的时间为随机数种子
    int arr[] = {9,7,1,3,2,6,8,4,5};
    travles(arr, 9);
    quickSort(arr, 0,8);
    travles(arr, 9);
    return 0;
}

观察比较代码可以发现随机快排只不过是在partition时随机选出一个下标上的数作为比较对象，从而避免了每一轮选择尾元素会受数据状况的影响的问题。

那么随机快排的时间复杂度又为多少呢？

经数学论证，由于每一轮partition选出的作为比较对象的数是随机的，即序列中的每个数都有1/n的概率被选上，那么该算法时间复杂度为概率事件，经数学论证该算法的数学期望为O(nlogn)。虽然说是数学期望，但在实际工程中，常常就把随机快排的时间复杂度当做O(nlog)。

堆排序

什么是堆

堆结构就是将一颗完全二叉树映射到数组中的一种存储方式：

大根堆和小根堆

当堆的每一颗子树（包括树本身）的最大值就是其结点时称为大根堆；相反，当堆的每一颗子树的最小值就是其根结点时称为小根堆。其中大根堆的应用较为广泛，是一种很重要的数据结构。

heapInsert和heapify

大根堆最重要的两个操作就是heapInsert和heapify，前者是当一个元素加入到大根堆时应该自底向上与其父结点比较，若大于父结点则交换；后者是当堆中某个结点的数值发生变化时，应不断向下与其孩子结点中的最大值比较，若小于则交换。下面是对应的代码：

//index之前的序列符合大根堆排序，将index位置的元素加入堆结构，但不能破坏大根堆的特性
void heapInsert(int arr[],int index){
    while (arr[index] > arr[(index - 1) / 2]) { //当该结点大于父结点时
        swap(arr[index], arr[(index - 1) / 2]);
        index = (index - 1) / 2;    //继续向上比较
    }
}

//数组中下标从0到heapSize符合大根堆排序
//index位置的值发生了变化，重新调整堆结构为大根堆
//heapSize指的是数组中符合大根堆排序的范围而不是数组长度,最大为数组长度，最小为0 
void heapify(int arr[], int heapSize, int index){
    int leftChild = index * 2 + 1;
    while (leftChild < heapSize) {  //当该结点有左孩子时
        int greatOne = leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild] ?
                leftChild + 1 : leftChild;  //只有当右孩子存在且大于左孩子时，最大值是右孩子，否则是左孩子
        greatOne = arr[greatOne] > arr[index] ? greatOne : index;//将父结点与最大孩子结点比较，确定最大值
        if (greatOne == index) {
            //如果最大值是本身，则不用继续向下比较
            break;
        }
        swap(arr[index], arr[greatOne]);

        //next turn下一轮
        index = greatOne;
        leftChild = index * 2 + 1;
    }
}

建立大根堆

void buildBigRootHeap(int arr[],int length){
    if (arr == NULL || length <= 1) {
        return;
    }
    for (int i = 0; i < length; ++i) {
        heapInsert(arr, i);
    }
}

利用heapify排序

前面做了那么多铺垫都是为了建立大根堆，那么如何利用它来排序呢？

对应代码实现如下：

void heapSort(int arr[],int length){
    if (arr == NULL || length <= 1) {
        return;
    }
  	//先建立大根堆
    for (int i = 0; i < length; ++i) {
        heapInsert(arr, i);
    }
 	  //循环弹出堆顶元素并heapify
    int heapSize = length;
    swap(arr[0], arr[--heapSize]);//相当于弹出堆顶元素
    while (heapSize > 0) {
        heapify(arr, heapSize, 0);
        swap(arr[0], arr[--heapSize]);
    }
}

int main(){
    int arr[] = {9,7,1,3,6,8,4,2,5};
    heapSort(arr, 9);
    travles(arr, 9);
    return 0;
}

堆排序的优势在于无论是入堆一个元素heapInsert还是出堆一个元素之后的heapify都不是将整个样本遍历一遍（O(n)级别的操作），而是树层次上的遍历（O(logn)级别的操作）。

这样的话堆排序过程中，建立堆的时间复杂度为O(nlogn)，循环弹出堆顶元素并heapify的时间复杂度为O(nlogn)，整个堆排序的时间复杂度为O(nlogn)，额外空间复杂度为O(1)

优先级队列结构（比如Java中的PriorityQueue）就是堆结构。

排序算法的稳定性

排序算法的稳定性指的是排序前后是否维持值相同的元素在序列中的相对次序。如序列271532，在排序过程中如果能维持第一次出现的2在第二次出现的2的前面，那么该排序算法能够保证稳定性。首先我们来分析一下前面所讲排序算法的稳定性，再来谈谈稳定性的意义。

  • 冒泡排序。可以保证稳定性，只需在比较相邻两个数时只在后一个数比前一个数大的情况下才交换位置即可。
  • 选择排序。无法保证稳定性，比如序列926532，在第一轮maxIndex的选择出来之后（maxIndex=0），第二次出现的2（尾元素）将与9交换位置，那么两个2的相对次序就发生了变化，而这个交换是否会影响稳定性在我们coding的时候是不可预测的。
  • 插入排序。可以保证稳定性，每次插入一个数到有序序列中时，遇到比它大的就替换，否则不替换。这样的话，值相同的元素，后面插入的就总在前面插入的后面了。
  • 归并排序。可以保证稳定性，在左右两半子序列排好序后的merge过程中，比较大小时如果相等，那么优先插入左子序列中的数。
  • 快排。不能保证稳定性，因为partition的过程会将比num小的与small区域的右一个数交换位置，将比num大的与great区域的左一个数交换位置，而small、great分居序列两侧，很容易打乱值相同元素的相对次序。
  • 堆排序。不能保证稳定性。二叉树如果交换位置的结点是相邻层次的可以保证稳定性，但堆排序中弹出堆顶元素后的heapify交换的是第一层的结点和最后一层的结点。

维持稳定性一般是为了满足业务需求。假设下面是一张不同厂商下同一款产品的价格和销售情况表：

品牌 价格 销量
三星 1603 92
小米 1603 74
vivo 1604 92

要求先按价格排序，再按销量排序。如果保证稳定性，那么排序后应该是这样的：

品牌 价格 销量
三星 1603 92
vivo 1604 92
小米 1603 74

即按销量排序后，销量相同的两条记录会保持之前的按价格排序的状态，这样先前的价格排序这个工作就没白做。

比较器的使用

之前所讲的一些算法大都是对基本类型的排序，但实际工程中要排序的对象可能是无法预测的，那么如何实现一个通用的排序算法以应对呢？事实上，之前的排序都可以归类为基于比较的排序。也就是说我们只需要对要比较的对象实现一个比较器，然后排序算法基于比较器来排序，这样算法和具体要排序的对象之间就解耦了。以后在排序之前，基于要排序的对象实现一个比较器（定义了如何比较对象大小的逻辑），然后将比较器丢给排序算法即可，这样就实现了复用。

在Java（本人学的是Java方向）中，这个比较器就是Comparator接口，我们需要实现其中的compare方法，对于要排序的对象集合定义一个比较大小的逻辑，然后在构造用来添加这类对象的有序容器时传入这个构造器即可。封装好的容器会在容器元素发生改变时使用我们的比较器来重新组织这些元素。

import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.PriorityQueue;
import java.util.Comparator;

public class ComparatorTest {
    
    @Data
    @AllArgsConstructor
    static class Student {
        private long id;
        private String name;
        private double score;
    }

    static class IdAscendingComparator implements Comparator<Student> {
        /**
         * 底层排序算法对两个元素比较时会调用这个方法
         * @param o1
         * @param o2
         * @return  若返回正数则认为o1<o2，返回0则认为o1=o2，否则认为o1>o2
         */
        @Override
        public int compare(Student o1, Student o2) {
            return o1.getId() < o2.getId() ? -1 : 1;
        }
    }

    public static void main(String[] args) {
        //大根堆
        PriorityQueue heap = new PriorityQueue(new IdAscendingComparator());
        Student zhangsan = new Student(1000, "zhangsan", 50);
        Student lisi = new Student(999, "lisi", 60);
        Student wangwu = new Student(1001, "wangwu", 50);
        heap.add(zhangsan);
        heap.add(lisi);
        heap.add(wangwu);
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());//弹出并返回堆顶元素
        }
    }
}

还有TreeSet等，都是在构造是传入比较器，否则将直接根据元素的值（Java中引用类型变量的值为地址，比较将毫无意义）来比较，这里就不一一列举了。

有关排序问题的补充

  1. 归并排序可以做到额外空间复杂度为O(1)，但是比较难，感兴趣的可以搜 归并排序 内部缓存法
  2. 快速排序可以做到保证稳定性，但是很难，可以搜01 stable sort（论文）
  3. 有一道题是：是奇数放到数组左边，是偶数放到数组右边，还要求奇数和奇数之间、偶数和偶数之间的原始相对次序不变。这道题和归并排序如出一辙，只不过归并排序是将arr[length-1]或arr[randomIndex]作为比较的标准，而这道题是将是否能整除2作为比较的标准，这类问题都同称为o1 sort，要使这类问题做到稳定性，要看01 stable sort这篇论文。

工程中的综合排序算法

实际工程中的排序算法一般会将 归并排序、插入排序、快速排序综合起来，集大家之所长来应对不同的场景要求：

  • 当要排序的元素为基本数据类型且元素个数较少时，直接使用 插入排序。因为在样本规模较小时（比如60），O(NlogN)的优势并不明显甚至不及O(N^2)，而在O(N^2)的算法中，插入排序的常数时间操作最少。
  • 当要排序的元素为对象数据类型（包含若干字段），为保证稳定性将采用 归并排序。
  • 当要排序的元素为基本数据类型且样本规模较大时，将采用 快速排序。

桶排序

上一节中所讲的都是基于比较的排序，也即通过比较确定每个元素所处的位置。那么能不能不比较而实现排序呢？这就涉及到了 桶排序 这个方法论：准备一些桶，将序列中的元素按某些规则放入翻入对应的桶中，最后根据既定的规则依次倒出桶中的元素。

非基于比较的排序，与被排序的样本的实际数据状况有很大关系，所以在实际中并不常用。

计数排序

计数排序是 桶排序 方法论的一种实现，即准备一个与序列中元素的数据范围大小相同的数组，然后遍历序列，将遇到的元素作为数组的下标并将该位置上的数加1。例如某序列元素值在0~100之间，请设计一个算法对其排序，要求时间复杂度为O(N)。

#include <stdio.h>
void countSort(int arr[],int length){
    int bucketArr[101];
    int i;
    for(i = 0 ; i <= 100 ; i++){
        bucketArr[i]=0;	//init buckets
    }
    for(i = 0 ; i < length ; i++){
        bucketArr[arr[i]]++;	//put into buckets
    }
    int count, j=0;
    for(i = 0 ; i <= 100 ; i++) {
        if (bucketArr[i] != 0) { //pour out
            count = bucketArr[i];
            while (count-- > 0) {
                arr[j++] = i;
            }
        }
    }
}

void travels(int arr[], int length){
    for (int i = 0; i < length; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(){
    int arr[] = {9, 2, 1, 4, 5, 2, 1, 6, 3, 8, 1, 2};
    travels(arr, 12);//9 2 1 4 5 2 1 6 3 8 1 2
    countSort(arr, 12);
    travels(arr, 12);//1 1 1 2 2 2 3 4 5 6 8 9
    return 0;
}

如果下次面试官问你有没有事件复杂度比O(N)更优的排序算法时，不要忘了计数排序哦！！！

补充问题

  1. 给定一个数组，求如果排序后，相邻两数的最大值，要求时间复杂度为O(N)，且要求不能用非基于比较的排序。

    这道题的思路比较巧妙：首先为这N个数准备N+1个桶，然后以其中的最小值和最大值为边界将数值范围均分成N等分，然后遍历数组将对应范围类的数放入对应的桶中，下图以数组长度为9举例

    这里比较难理解的是：

    • 题目问的是求如果排序后，相邻两数的最大差值。该算法巧妙的借助一个空桶（N个数进N+1个桶，必然有一个是空桶），将问题转向了求两个相邻非空桶 （其中可能隔着若干个空桶）之间前桶的最大值和后桶最小值的差值，而无需在意每个桶中进了哪些数（只需记录每个桶入数的最大值和最小值以及是否有数）

    对应代码如下：

    #include <stdio.h>

//根据要入桶的数和最大最小值得到对应桶编号
int getBucketId(int num,int bucketsNum,int min,int max){
    return (num - min) * bucketsNum / (max - min);
}

int max(int a, int b){
    return a > b ? a : b;
}

int min(int a, int b){
    return a < b ? a : b;
}

int getMaxGap(int arr[], int length) {
    if (arr == NULL || length < 2) {
        return -1;
    }
    int maxValue = -999999, minValue = 999999;
    int i;
    //找出最大最小值
    for (i = 0; i < length; ++i) {
        maxValue = max(maxValue, arr[i]);
        minValue = min(minValue, arr[i]);
    }
    //记录每个桶的最大最小值以及是否有数，初始时每个桶都没数
    int maxs[length + 1], mins[length + 1];
    bool hasNum[length + 1];
    for (i = 0; i < length + 1; i++) {	
        hasNum[i] = false;
    }
    //put maxValue into the last bucket
    mins[length] = maxs[length] = maxValue;
    hasNum[length] = true;

    //iterate the arr
    int bid; //bucket id
    for (i = 0; i < length; i++) {
        if (arr[i] != maxValue) {
            bid = getBucketId(arr[i], length + 1, minValue, maxValue);
          	//如果桶里没数，则该数入桶后，最大最小值都是它，否则更新最大最小值
            mins[bid] = !hasNum[bid] ? arr[i] : arr[i] < mins[bid] ? arr[i] : mins[bid];
            maxs[bid] = !hasNum[bid] ? arr[i] : arr[i] > maxs[bid] ? arr[i] : maxs[bid];
            hasNum[bid] = true;
        }
    }

    //find the max gap between two nonEmpty buckets
    int res = 0, j = 0;
    for (i = 0; i < length; ++i) {
        j = i + 1;//the next nonEmtpy bucket id
        while (!hasNum[j]) {//the last bucket must has number
            j++;
        }
        res = max(res, (mins[j] - maxs[i]));
    }

    return res;
}

int main(){
    int arr[] = {13, 41, 67, 26, 55, 99, 2, 82, 39, 100};
    printf("%d", getMaxGap(arr, 9));	//17
    return 0;
}

链表

反转单链表和双向链表

实现反转单向链表和反转双向链表的函数，要求时间复杂度为O(N)，额外空间复杂度为O(1)

此题的难点就是反转一个结点的next指针后，就无法在该结点通过next指针找到后续的结点了。因此每次反转之前需要将该结点的后继结点记录下来。

#include<stdio.h>
#include<malloc.h>
#define MAX_SIZE 100

struct LinkNode{
	int data;
	LinkNode* next;
};

void init(LinkNode* &head){
	head = (LinkNode*)malloc(sizeof(LinkNode));
	head->next=NULL;
}

void add(int i,LinkNode* head){
	LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
	p->data = i;
	p->next =  head->next;
	head->next = p;
}

void printList(LinkNode* head){
	if(head==NULL)
		return;
	LinkNode* p = head->next;
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

#include<stdio.h>
#include "LinkList.cpp"

void reverseList(LinkNode *head){
	if(head == NULL)
		return;
	LinkNode* cur = head->next;
	LinkNode* pre = NULL;
	LinkNode* next = NULL;
	while(cur != NULL){
		next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}
	//pre -> end node
	head->next = pre;
	return;
}

int main(){
	LinkNode* head;
	init(head);
	add(1,head);
	add(2,head);
	add(3,head);
	add(4,head);
	
	printList(head);
	reverseList(head);
	printList(head);
}

判断一个链表是否为回文结构

请实现一个函数判断某个单链表是否是回文结构，如1->3->1返回true、1->2->2->1返回true、2->3->1返回false。

我们可以利用回文链表前后两半部分逆序的特点、结合栈先进后出来求解此问题。将链表中间结点之前的结点依次压栈，然后从中间结点的后继结点开始遍历链表的后半部分，将遍历的结点与栈弹出的结点比较。

代码示例如下：

#include<stdio.h>
#include "LinkList.cpp"
#include "SqStack.cpp"

/*
	判断某链表是否是回文结构
	1、首先找到链表的中间结点（若是偶数个结点则是中间位置的左边一个结点）
	2、使用一个栈将中间结点之前的结点压栈，然后从中间结点的后一个结点开始从栈中拿出结点比较 
*/

bool isPalindromeList(LinkNode* head){
	if(head == NULL)
		return false;
		
	LinkNode *slow = head , *fast = head;
	SqStack* stack;
	init(stack);
	
	//fast指针每走两步，slow指针才走一步 
	while(fast->next != NULL && fast->next->next != NULL){
		fast = fast->next->next;	
		slow = slow->next;	
		push(slow,stack);
	}
	
	//链表没有结点或只有一个结点，不是回文结构
	if(isEmpty(stack)) 
		return false;
		
	//判断偶数个结点还是奇数个结点
	if(fast->next != NULL){	//奇数个结点,slow需要再走一步 
		slow = slow->next;
	}
	
	//从slow的后继结点开始遍历链表，将每个结点与栈顶结点比较
	LinkNode* node;
	slow = slow->next;
	while(slow != NULL){
		pop(stack,node);
		//一旦发现有一个结点不同就不是回文结构 
		if(slow->data != node->data)
			return false;
		slow = slow->next;
	} 
	return true;
}

int main(){
	
	LinkNode* head;
	init(head);
	add(2,head);
	add(3,head);
	add(3,head);
	add(2,head);
	printList(head);
	
	if(isPalindromeList(head)){
		printf("是回文链表");
	}else{
		printf("不是回文链表");
	}
	return 0;
}

LinkList.cpp:

#include<stdio.h>
#include<malloc.h>
#define MAX_SIZE 100

struct LinkNode{
	int data;
	LinkNode* next;
};

void init(LinkNode* &head){
	head = (LinkNode*)malloc(sizeof(LinkNode));
	head->next=NULL;
}

void add(int i,LinkNode* head){
	LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
	p->data = i;
	p->next =  head->next;
	head->next = p;
}

void printList(LinkNode* head){
	if(head==NULL)
		return;
	LinkNode* p = head->next;
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

SqStack:

#include<stdio.h>
#include<malloc.h>

struct SqStack{
	LinkNode* data[MAX_SIZE];
	int length;
}; 

void init(SqStack* &stack){
	stack = (SqStack*)malloc(sizeof(SqStack));
	stack->length=0; 
}

bool isEmpty(SqStack* stack){
	if(stack->length > 0)
		return false;
	return true;
}

bool isFull(SqStack* stack){
	if(stack->length == MAX_SIZE)
		return true;
	return false;
}

void push(LinkNode* i,SqStack* stack){
	if(stack==NULL)
		return;
	if(!isFull(stack)){
		stack->data[stack->length++] = i;
	}
}

bool pop(SqStack* stack,LinkNode* &i){
	if(stack==NULL)
		return false;
	if(!isEmpty(stack))
		i = stack->data[--stack->length];
		return true;
}

进阶：要求使用时间复杂度为O(N)，额外空间复杂度为O(1)求解此问题。

思路：我们可以先将链表的后半部分结点的next指针反向，然后从链表的两头向中间推进，逐次比较。（当然了，为了不破坏原始数据结构，我们在得出结论之后还需要将链表指针恢复原样）

#include<stdio.h>
#include "LinkList.cpp"
#include "SqStack.cpp"

bool isPalindromeList(LinkNode* head){
    /*第一步、与方法一一样，找到中间结点*/
    if(head == NULL)
        return false;

    LinkNode *n1 = head , *n2 = head;
    while(n2->next != NULL && n2->next->next != NULL){
        n2 = n2->next->next;
        n1 = n1->next;
    }
    //如果没有结点或者只有一个首结点
    if(n2 == head){
        return false;
    }
    //如果是奇数个结点
    if(n2->next != NULL){
        n1 = n1->next;  //n1 -> middle node
    }

    /*第二步、不使用额外空间，在链表自身上做文章：反转链表后半部分结点的next指针*/
    n2 = n1->next;  // n2 -> right part first node
    n1->next = NULL;//middle node->next = NULL
    LinkNode *n3 = NULL;
    while (n2 != NULL) {
        n3 = n2->next;  //记录下一个要反转指针的结点
        n2->next = n1;  //反转指针
        n1 = n2;
        n2 = n3;
    }
    //n1 -> end node
    n3 = n1;  //record end node
    n2 = head->next;
    while (n2 != NULL) {
        if (n2->data != n1->data) {
            return false;
        }
        n2 = n2->next;  //move n2 forward right
        n1 = n1->next;  //move n1 forward left
    }
    //recover the right part nodes
    n2 = n3; //n2 -> end node
    n1 = NULL;
    while (n2 != NULL) {
        n3 = n2->next;
        n2->next = n1;
        n1=n2;
        n2 = n3;
    }

    return true;
}


/*bool isPalindromeList(LinkNode* head){
    if(head == NULL)
        return false;

    LinkNode *slow = head , *fast = head;
    SqStack* stack;
    init(stack);

    //fast指针每走两步，slow指针才走一步
    while(fast->next != NULL && fast->next->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
        push(slow,stack);
    }

    //链表没有结点或只有一个结点，不是回文结构
    if(isEmpty(stack))
        return false;

    //判断偶数个结点还是奇数个结点
    if(fast->next != NULL){	//奇数个结点,slow需要再走一步
        slow = slow->next;
    }

    //从slow的后继结点开始遍历链表，将每个结点与栈顶结点比较
    LinkNode* node;
    slow = slow->next;
    while(slow != NULL){
        pop(stack,node);
        //一旦发现有一个结点不同就不是回文结构
        if(slow->data != node->data)
            return false;
        slow = slow->next;
    }
    return true;
}*/

int main(){

    LinkNode* head;
    init(head);
    add(2,head);
    add(3,head);
    add(3,head);
    add(1,head);
    printList(head);

    if(isPalindromeList(head)){
        printf("yes");
    }else{
        printf("no");
    }
    return 0;
}

链表与荷兰国旗问题

将单向链表按某值划分成左边小、中间相等、右边大的形式

#include<stdio.h>
#include "LinkList.cpp"

/*
	partition一个链表有两种做法。
	1，将链表中的所有结点放入一个数组中，那么就转换成了荷兰国旗问题，但这种做法会使用O(N)的额外空间；
	2，分出逻辑上的small,equal,big三个区域，遍历链表结点将其添加到对应的区域中，最后再将这三个区域连起来。 
	这里只示范第二种做法： 
*/
void partitionList(LinkNode *head,int val){
	if(head == NULL)
		return;
	LinkNode *smH = NULL;	//small area head node
	LinkNode *smT = NULL;	//small area tail node
	LinkNode *midH = NULL;	//equal area head node
	LinkNode *midT = NULL;	//equal area tail node
	LinkNode *bigH = NULL;	//big area head node
	LinkNode *bigT = NULL;	//big area tail node
	LinkNode *cur = head->next;	
	LinkNode *next = NULL;//next node need to be distributed to the three areas
	while(cur != NULL){
		next = cur->next;
		cur->next = NULL;
		if(cur->data > val){
			if(bigH == NULL){
				bigH = bigT = cur;
			}else{
				bigT->next = cur;
				bigT = cur;
			}
		}else if(cur->data == val){
			if(midH == NULL){
				midH = midT = cur;
			}else{
				midT->next = cur;
				midT = cur;
			}
		}else{
			if(smH == NULL){
				smH = smT = cur;
			}else{
				smT->next = cur;
				smT = cur;
			}
		}
		cur = next;
	}
	//reconnect small and equal
	if(smT != NULL){
		smT->next = midH;
		midT = midT == NULL ? midT : smT;
	}
	//reconnect equal and big
	if(bigT != NULL){
		midT->next = bigH;
	}

	head = smH != NULL ? smH : midH != NULL ? midH : bigH;

	return;
} 

int main(){
	LinkNode* head;
	init(head);
	add(5,head);
	add(2,head);
	add(7,head);
	add(9,head);
	add(1,head);
	add(3,head);
	add(5,head);
	printList(head);
	partitionList(head,5);
	printList(head);
}

复制含有随机指针结点的链表

借助哈希表，额外空间O(N)

将链表的所有结点复制一份，以key,value为源结点，副本结点的方式存储到哈希表中，再建立副本结点之间的关系（next、rand指针域）

import java.util.HashMap;
import java.util.Map;

public class CopyLinkListWithRandom {

    public static class Node {
        public Node(int data) {
            this.data = data;
        }

        public Node() {
        }

        int data;
        Node next;
        Node rand;
    }

    public static Node copyLinkListWithRandom(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> copyMap = new HashMap<>();
        while (cur != null) {
            copyMap.put(cur, new Node(cur.data));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            copyMap.get(cur).next = copyMap.get(cur.next);
            copyMap.get(cur).rand = copyMap.get(cur.rand);
            cur = cur.next;
        }
        return copyMap.get(head);
    }

    public static void printListWithRandom(Node head) {
        if (head != null) {
            while (head.next != null) {
                head = head.next;
                System.out.print("node data:" + head.data);
                if (head.rand != null) {
                    System.out.println(",rand data:" + head.rand.data);
                } else {
                    System.out.println(",rand is null");
                }
            }
        }
    }
  
    public static void main(String[] args) {
        Node head = new Node();
        head.next = new Node(1);
        head.next.next = new Node(2);
        head.next.next.next = new Node(3);
        head.next.next.next.next = new Node(4);
        head.next.rand = head.next.next.next.next;
        head.next.next.rand = head.next.next.next;
        printListWithRandom(head);

        System.out.println("==========");

        Node copy = copyLinkListWithRandom(head);
        printListWithRandom(copy);
    }
}

进阶操作：额外空间O(1)

将副本结点追加到对应源结点之后，建立副本结点之间的指针域，最后将副本结点从该链表中分离出来。

//extra area O(1)
public static Node copyLinkListWithRandom2(Node head){
  if (head == null) {
    return null;
  }
  Node cur = head;
  //copy every node and append
  while (cur != null) {
    Node copy = new Node(cur.data);
    copy.next = cur.next;
    cur.next = copy;
    cur = cur.next.next;
  }
  //set the rand pointer of every copy node
  Node copyHead = head.next;
  cur = head;
  Node curCopy = copyHead;
  while (curCopy != null) {
    curCopy.rand = cur.rand == null ? null : cur.rand.next;
    cur = curCopy.next;
    curCopy = cur == null ? null : cur.next;
  }
  //split
  cur = head;
  Node next = null;
  while (cur != null) {
    curCopy = cur.next;
    next = cur.next.next;
    curCopy.next = next == null ? null : next.next;
    cur.next = next;
    cur = next;
  }
  return copyHead;
}

若两个可能有环的单链表相交，请返回相交的第一个结点

根据单链表的定义，每个结点有且只有一个next指针，那么如果单链表有环，它的结构将是如下所示：

相交会导致两个结点指向同一个后继结点，但不可能出现一个结点有两个后继结点的情况。

1、当相交的结点不在环上时，有如下两种情况：

2、当相交的结点在环上时，只有一种情况：

综上，两单链表若相交，要么都无环，要么都有环。

此题还需要注意的一点是如果链表有环，那么如何获取入环呢（因为不能通过next是否为空来判断是否是尾结点了）。这里就涉及到了一个规律：如果快指针fast和慢指针slow同时从头结点出发，fast走两步而slow走一步，当两者相遇时，将fast指针指向头结点，使两者都一次只走一步，两者会在入环结点相遇。

public class FirstIntersectNode {
    public static class Node{
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
        }
    }

    public static Node getLoopNode(Node head) {
        if (head == null) {
            return null;
        }
        Node fast = head;
        Node slow = head;
        do {
            slow = slow.next;
            if (fast.next == null || fast.next.next == null) {
                return null;
            } else {
                fast = fast.next.next;
            }
        } while (fast != slow);
        //fast == slow
        fast = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public static Node getFirstIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1);    //两链表的入环结点loop1和loop2
        Node loop2 = getLoopNode(head2);
        //no loop
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        //both loop
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, head2, loop1, loop2);
        }
        //don't intersect
        return null;
    }

    private static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2) {
        Node cur1 = head1;
        Node cur2 = head2;
        //入环结点相同，相交点不在环上
        if (loop1 == loop2) {
            int n = 0;
            while (cur1.next != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2.next != loop1) {
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;           //将cur1指向结点数较多的链表
            cur2 = cur1 == head1 ? head2 : head1;   //将cur2指向另一个链表
            n = Math.abs(n);
            while (n != 0) {                        //将cur1先走两链表结点数差值个结点
                cur1 = cur1.next;
                n--;
            }
            while (cur1 != cur2) {                  //cur1和cur2会在入环结点相遇
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
        //入环结点不同，相交点在环上
        cur1 = loop1.next;
        while (cur1 != loop1) {
            if (cur1 == loop2) {    //链表2的入环结点在链表1的环上，说明相交
                return loop1;   //返回loop1或loop2均可，因为整个环就是两链表的相交部分
            }
            cur1 = cur1.next;
        }
        //在链表1的环上转了一圈也没有找到链表2的入环结点，说明不想交
        return null;
    }

    private static Node noLoop(Node head1, Node head2) {
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }
        if (cur1 != cur2) {     //两链表的尾结点不同，不可能相交
            return null;
        }
        cur1 = n > 0 ? head1 : head2;           //将cur1指向结点数较多的链表
        cur2 = cur1 == head1 ? head2 : head1;   //将cur2指向另一个链表
        n = Math.abs(n);
        while (n != 0) {                        //将cur1先走两链表结点数差值个结点
            cur1 = cur1.next;
            n--;
        }
        while (cur1 != cur2) {                  //cur1和cur2会在入环结点相遇
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    public static void printList(Node head) {
        for (int i = 0; i < 50; i++) {
            System.out.print(head.data+" ");
            head = head.next;
        }
        System.out.println();
    }

}

对应三种情况测试如下：

public static void main(String[] args) {

        //==================== both loop ======================
        //1->2->[3]->4->5->6->7->[3]...
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next.next = head1.next.next;

        //9->8->[6]->7->3->4->5->[6]...
        Node head2 = new Node(9);
        head2.next = new Node(8);
        head2.next.next = head1.next.next.next.next.next;
        head2.next.next.next = head1.next.next.next.next.next.next;
        head2.next.next.next.next = head1.next.next;
        head2.next.next.next.next.next = head1.next.next.next;
        head2.next.next.next.next.next.next = head1.next.next.next.next;
        head2.next.next.next.next.next.next.next = head1.next.next.next.next.next;

        printList(head1);
        printList(head2);
        System.out.println(getFirstIntersectNode(head1, head2).data);
        System.out.println("==================");

        //1->[2]->3->4->5->6->7->8->4...
        Node head3 = new Node(1);
        head3.next = new Node(2);
        head3.next.next = new Node(3);
        head3.next.next.next = new Node(4);
        head3.next.next.next.next = new Node(5);
        head3.next.next.next.next.next = new Node(6);
        head3.next.next.next.next.next.next = new Node(7);
        head3.next.next.next.next.next.next.next = new Node(8);
        head3.next.next.next.next.next.next.next.next = head1.next.next.next;

        //9->0->[2]->3->4->5->6->7->8->4...
        Node head4 = new Node(9);
        head4.next = new Node(0);
        head4.next.next = head3.next;
        head4.next.next.next = head3.next.next;
        head4.next.next.next.next = head3.next.next.next;
        head4.next.next.next.next.next = head3.next.next.next.next;
        head4.next.next.next.next.next.next = head3.next.next.next.next.next;
        head4.next.next.next.next.next.next.next = head3.next.next.next.next.next.next;
        head4.next.next.next.next.next.next.next.next = head3.next.next.next.next.next.next.next;
        head4.next.next.next.next.next.next.next.next.next = head3.next.next.next;

        printList(head3);
        printList(head4);
        System.out.println(getFirstIntersectNode(head3,head4).data);
        System.out.println("==================");

        //============= no loop ==============
        //1->[2]->3->4->5
        Node head5 = new Node(1);
        head5.next = new Node(2);
        head5.next.next = new Node(3);
        head5.next.next.next = new Node(4);
        head5.next.next.next.next = new Node(5);
        //6->[2]->3->4->5
        Node head6 = new Node(6);
        head6.next = head5.next;
        head6.next.next = head5.next.next;
        head6.next.next.next = head5.next.next.next;
        head6.next.next.next.next = head5.next.next.next.next;

        System.out.println(getFirstIntersectNode(head5,head6).data);
    }

栈和队列

用数组结构实现大小固定的栈和队列

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#define MAX_SIZE 1000

struct ArrayStack{
    int data[MAX_SIZE];
    int top;
};

void init(ArrayStack *&stack) {
    stack = (ArrayStack *) malloc(sizeof(ArrayStack));
    stack->top = -1;
}

bool isEmpty(ArrayStack* stack){
    return stack->top == -1 ?;
}

bool isFull(ArrayStack *stack){
    return stack->top == MAX_SIZE - 1 ?;
}

void push(int i, ArrayStack *stack){
    if (!isFull(stack)) {
        stack->data[++stack->top] = i;
    }
}

int pop(ArrayStack* stack){
    if (!isEmpty(stack)) {
        return stack->data[stack->top--];
    }
}

int getTopElement(ArrayStack *stack){
    if (!isEmpty(stack)) {
        return stack->data[stack->top];
    }
}

int main(){

    ArrayStack* stack;
    init(stack);
    push(1, stack);
    push(2, stack);
    push(3, stack);

    printf("%d ", pop(stack));
    printf("%d ", getTopElement(stack));
    printf("%d ", pop(stack));
    printf("%d ", pop(stack));
		//3 2 2 1
    return 0;
}

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#define MAX_SIZE 1000

//数组结构实现的环形队列
struct ArrayCircleQueue{
    int data[MAX_SIZE];
    int front,rear;
};

void init(ArrayCircleQueue *&queue){
    queue = (ArrayCircleQueue *) malloc(sizeof(ArrayCircleQueue));
    queue->front = queue->rear = 0;
}

bool isEmpty(ArrayCircleQueue *queue){
    return queue->front == queue->rear;
}

bool isFull(ArrayCircleQueue *queue){
    return (queue->rear+1)%MAX_SIZE==queue->front;
}

void enQueue(int i, ArrayCircleQueue *queue){
    if (!isFull(queue)) {
        //move the rear and fill it
        queue->data[++queue->rear] = i;
    }
}

int deQueue(ArrayCircleQueue *queue){
    if (!isEmpty(queue)) {
        return queue->data[++queue->front];
    }
}

int main(){
    ArrayCircleQueue* queue;
    init(queue);
    enQueue(1, queue);
    enQueue(2, queue);
    enQueue(3, queue);
    while (!isEmpty(queue)) {
        printf("%d ", deQueue(queue));
    }
}

取栈中最小元素

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作getMin。要求如下：

  • pop、push、getMin操作的时间复杂度都是O(1)。
  • 设计的栈类型可以使用现成的栈结构。

思路：由于每次push之后都会可能导致栈中已有元素的最小值发生变化，因此需要一个容器与该栈联动（记录每次push产生的栈中最小值）。我们可以借助一个辅助栈，数据栈push第一个元素时，将其也push到辅助栈，此后每次向数据栈push元素的同时将其和辅助栈的栈顶元素比较，如果小，则将其也push到辅助栈，否则取辅助栈的栈顶元素push到辅助栈。（数据栈正常push、pop数据，而辅助栈push每次数据栈push后产生的栈中最小值；但数据栈pop时，辅助栈也只需简单的pop即可，保持同步）

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#include "ArrayStack.cpp"

int min(int a, int b){
    return a < b ? a : b;
}

struct GetMinStack{
    ArrayStack* dataStack;
    ArrayStack* helpStack;
};

void initGetMinStack(GetMinStack* &stack){
    stack = (GetMinStack *) malloc(sizeof(GetMinStack));
    init(stack->dataStack);
    init(stack->helpStack);
}

void push(int i, GetMinStack *stack) {
    if (!isFull(stack->dataStack)) {
        push(i, stack->dataStack);  //ArrayStack.cpp
        if (!isEmpty(stack->helpStack)) {
            i = min(i, getTopElement(stack->helpStack));
        }
        push(i, stack->helpStack);
    }
}

int pop(GetMinStack* stack){
    if (!isEmpty(stack->dataStack)) {
        pop(stack->helpStack);
        return pop(stack->dataStack);
    }
}

int getMin(GetMinStack *stack){
    if (!isEmpty(stack->dataStack)) {
        return getTopElement(stack->helpStack);
    }
}

int main(){
    GetMinStack *stack;
    initGetMinStack(stack);
    push(6, stack);
    printf("%d ", getMin(stack));//6
    push(3, stack);
    printf("%d ", getMin(stack));//3
    push(1, stack);
    printf("%d ", getMin(stack));//1
  	pop(stack);
    printf("%d ", getMin(stack));//3

    return 0;
}

仅用队列结构实现栈结构

思路：只要将关注点放在 后进先出 这个特性就不难实现了。使用一个数据队列和辅助队列，当放入数据时使用队列的操作正常向数据队列中放，但出队元素时，需将数据队列的前n-1个数入队辅助队列，而将数据队列的队尾元素弹出来，最后数据队列和辅助队列交换角色。

//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#include "../queue/ArrayCircleQueue.cpp"

struct DoubleQueueStack{
    ArrayCircleQueue* dataQ;
    ArrayCircleQueue* helpQ;
};

void init(DoubleQueueStack* &stack){
    stack = (DoubleQueueStack *) malloc(sizeof(DoubleQueueStack));
    init(stack->dataQ);
    init(stack->helpQ);
}

void swap(ArrayCircleQueue *&dataQ, ArrayCircleQueue *&helpQ){
    ArrayCircleQueue* temp = dataQ;
    dataQ = helpQ;
    helpQ = temp;
}

void push(int i,DoubleQueueStack* stack){
    if (!isFull(stack->dataQ)) {
        return enQueue(i, stack->dataQ);
    }
}

int pop(DoubleQueueStack* stack){
    if (!isEmpty(stack->dataQ)) {
        int i = deQueue(stack->dataQ);
        while (!isEmpty(stack->dataQ)) {
            enQueue(i, stack->helpQ);
            i = deQueue(stack->dataQ);
        }
        swap(stack->dataQ, stack->helpQ);
        return i;
    }
}

bool isEmpty(DoubleQueueStack* stack){
    return isEmpty(stack->dataQ);
}

int getTopElement(DoubleQueueStack* stack){
    if (!isEmpty(stack->dataQ)) {
        int i = deQueue(stack->dataQ);
        while (!isEmpty(stack->dataQ)) {
            enQueue(i, stack->helpQ);
            i = deQueue(stack->dataQ);
        }
        enQueue(i, stack->helpQ);
        swap(stack->dataQ, stack->helpQ);
        return i;
    }
}

int main(){

    DoubleQueueStack *stack;
    init(stack);
    push(1, stack);
    push(2, stack);
    push(3, stack);
    while (!isEmpty(stack)) {
        printf("%d ", pop(stack));
    }
    push(4, stack);
    printf("%d ", getTopElement(stack));
    
    return 0;
}

仅用栈结构实现队列结构

思路：使用两个栈，一个栈PutStack用来放数据，一个栈GetStack用来取数据。取数据时，如果PulllStack为空则需要将PutStack中的所有元素一次性依次pop并放入GetStack。

特别要注意的是这个 倒数据的时机：

  • 只有当GetStack为空时才能往里倒
  • 倒数据时必须一次性将PutStack中的数据倒完
//
// Created by zaw on 2018/10/21.
//
#include <stdio.h>
#include <malloc.h>
#include "../stack/ArrayStack.cpp"

struct DoubleStackQueue{
    ArrayStack* putStack;
    ArrayStack* getStack;
};

void init(DoubleStackQueue *&queue){
    queue = (DoubleStackQueue *) malloc(sizeof(DoubleStackQueue));
    init(queue->putStack);
    init(queue->getStack);
}

bool isEmpty(DoubleStackQueue *queue){
    return isEmpty(queue->getStack) && isEmpty(queue->putStack);
}

void pour(ArrayStack *stack1, ArrayStack *stack2){
    while (!isEmpty(stack1)) {
        push(pop(stack1), stack2);
    }
}

void enQueue(int i, DoubleStackQueue *queue){
    if (!isFull(queue->putStack)) {
        push(i, queue->putStack);
    } else {
        if (isEmpty(queue->getStack)) {
            pour(queue->putStack, queue->getStack);
            push(i, queue->putStack);
        }
    }
}

int deQueue(DoubleStackQueue* queue){
    if (!isEmpty(queue->getStack)) {
        return pop(queue->getStack);
    } else {
        if (!isEmpty(queue->putStack)) {
            pour(queue->putStack, queue->getStack);
            return pop(queue->getStack);
        }
    }
}


int main(){
    DoubleStackQueue *queue;
    init(queue);
    enQueue(1, queue);
    printf("%d\n", deQueue(queue));
    enQueue(2, queue);
    enQueue(3, queue);
    while (!isEmpty(queue)) {
        printf("%d ", deQueue(queue));
    }
    return 0;
}
avatar
文章
阅读
粉丝