SkySea-GaoMing HomeArchivesTagsCategories
算法实现
|秋招|

个人简介

力扣地址：https://leetcode-cn.com/u/gao-ming-3/
牛客地址：高-明 https://www.nowcoder.com/profile/883461684

复杂度

时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析
T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时
间量度，记作：T(n)= O(f(n))。它表示随问题规模n的增大，算法执行时间的
增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度

渐进紧确界 Θ

随着数据规模增大，算法的运行时间主要取决于时间表达式系数最大的那一项。
T1(n)=30n4+20n3+40n2+46n+100 T2(n)=1000n3+50n2+78n+10
T1(n)=Θ(n4) T2​(n)=Θ(n3)

渐进上界 O

设f(n)和g(n)是定义域为自然数集N上的函数。若存在正数c和n0，使得对一切
n≥n0都有0≤f(n)≤cg(n)成立，则称f(n)的渐进的上界是g(n)，记作
f(n)=O(g(n))。通俗的说n满足一定条件范围内，函数f(n)的阶不高于函数g(n)。
例如：设f(n)=n2+n,则
f(n)=O(n2)，取c=2,n0=1即可
f(n)=O(n3)，取c=1,n0=2即可。显然，O(n2)作为上界更为精确。

渐进下界 Ω

与渐进上界刚好相反，这个下界的阶越高评估越精确

空间复杂度

一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))，例如
直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就
要有O(n)的空间复杂度了，因为每次递归都要存储返回信息

排序

  1. 排序算法的稳定性是指：经过排序之后,能使值相同的数据保持原顺序中的
    相对位置不变
  2. 归并排序的最坏情况，最好情况和平均情况都是O(nlogn); 快速排序的最
    坏情况是O(n^2)，最好的情况和平均情况是O(nlogn)
  3. 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排
    序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交
    换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，
    即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内
    存完成排序。然后，对已经排序的子文件进行多路归并排序
  4. 稳定排序：冒泡、归并、基数 不稳定排序：希快选堆
  5. 堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是
    O(nlogn)和O(1)
  6. master公式的使用 T(n) = a*T(n/b) + O(n^d)
    1) log(b,a) > d -> 复杂度为O(n^log(b,a))
    2) log(b,a) = d -> 复杂度为O(n^d * logn)
    3) log(b,a) < d -> 复杂度为O(n^d)

注意交换两个元素有一种简便写法

1
2
3
4
5
public void sawp(int[] array,int i,int j){
	array[i]=array[i]^array[j];
	array[j]=array[i]^array[j];
	array[i]=array[i]^array[j];
}

选择排序

选择排序是一种不稳定（5,5,2）任何情况下时间复杂度都是O(n^2)的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void select(int[] array)
{
	//思想是每次都选择一个最小值排在前面
	for(int i=0;i<array.length-1;i++)
	{
		int min=i; 
		for(int j=i+1;j<array.length;j++)
		{
			if(array[j]<min)
				min=j;
		}
		//第i个位置要排当前最小值
		if(min!=i)
		{
			int temp=array[min];
			array[min]=array[i];
			array[i]=temp;
		}
	}
}

冒泡排序

冒泡排序是一种稳定在最好情况下时间复杂度是O(n)最坏情况下O(n^2)平均情
况O(n^2)的排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void bubble(int[] array)
{
	//可以进行优化，如果当前已经有序就结束
	boolean flag=true;
	for(int i=1;i<array.length;i++) //最多排序次数
	{
		flag=true;
		for(int j=0;j<array.length-i;j++)
		{
			//按照顺序将前一个和后一个交换位置
			if(array[j]>array[j+1])
			{
				int temp=array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
				flag=false;
			}
		}
		//经过一轮交换发现已经有序就可知直接退出
		if(flag==true)
			break;
	}
}

归并排序

是稳定排序但是需要空间复杂度O(n)，需要调用logn次开辟栈帧空间，还
需要创建一个临时数组，时间复杂度是O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public void merge(int[] array)
{
	//需要开辟一个一样大小的数组空间
	int[] tempt=new int[array.length];
	sort(0,array.length-1,array,tempt);
}
public void sort(int li,int lo,int[] array,int[] tempt)
{
	//拆分的终止条件
	if(li>=lo)
		return ;
	//拆分数组
	int mid=(li+lo)/2;
	sort(li,mid,array,tempt);
	sort(mid+1,lo,array,tempt);
	//将有序的两部分合并为一个有序的部分，用tempt保存有序结果
	merge(li,mid,lo,array,tempt);
}
public void merge(int li,int mid,int lo,int[] array,int[] tempt)
{
	int index=0;
	int i=li;
	int j=mid+1;
	//合并操作
	while(i<=mid&&j<=lo)
	{
		if(array[i]<array[j])
			tempt[index++]=array[i++];
		else
			tempt[index++]=array[j++];
	}
	while(i<=mid)
		tempt[index++]=array[i++];
	while(j<=lo)
		tempt[index++]=array[j++];
	index=0;
	//这里必须要将有序结果重新写入array，因为还有更大规模的合并
	while(li<=lo)
		array[li++]=tempt[index++];
}

快速排序

快速排序是一种不稳定平均时间复杂度为O(nlogn)最好情况O(nlogn)最坏
情况O(n^2)空间复杂度为O(logn)(调用栈帧所需空间)的排序算法，最好情
况时每次都划分很均匀不需要交换，递归深度就是logn，跟归并排序一样。
最坏情况时数组为正序或者逆序时需要经过n-1次递归调用，每次划分执
只比上一次少一个元素的子序列，每次经过n-i次比较
T(n)=n-1+n-2+n-3+…1=n(n-1)/2 时间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public void quick(int[] array)
{
	sort(0,array.length-1,array);
}
public void sort(int li,int lo,int[] array)
{
	if(li>=lo)
		return ;
	//根据指定和元素将数组划分为两部分
	int partcut=part(li,lo,array);
	sort(li,partcut-1,array);
	sort(partcut+1,lo,array);
}
public int part(int li,int lo,int[] array)
{
	int cut=array[li];
	int i=li;
	int j=lo+1;
	while(true)
	{
		while(array[++i]<=cut)
		{
			if(i==lo)
				break;
		}
		while(array[--j]>=cut)
		{
			if(j==li)
				break;
		}
		if(j<=i)
			break;
		int tempt=array[i];
		array[i]=array[j];
		array[j]=tempt;
	}
	int tempt=array[li];
	array[li]=array[j];
	array[j]=tempt;
	//索引j处就是要划分的位置
	return j;
}

插入排序

插入排序是一种稳定平均时间复杂度为O(n^2)最好时间复杂度为O(n)最坏
时间复杂度为O(n^2)的排序算法，最好情况就是完全有序只需要遍历，最坏
情况比如倒序时每次都要交换i次 T(n)=1+2+3+n-1=n(n-1)/2 时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
public void insert(int[] array)
{
	for(int i=1;i<array.length;i++)
	{
		for(j=i;j>0&&array[j]<array[j-1];j--)
		{
			int temp=array[j];
			array[j]=array[j-1];
			array[j-1]=temp;
		}
	}
}

希尔排序

希尔排序是插入排序的改进，是不稳定的算法，时间复杂度介于O(n)到O(n^2)之间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void xhell(int[] array)
{
	int h=1;
	while(h<array.length)
		h=3*h+1;
	while(h>=1)
	{
		for(int i=h;i<array.length;i++)
		{
			for(int j=i;j>=h&&array[j]<array[j-h];j-=h)
			{
				int temp=array[j];
				array[j]=array[j-h];
				array[j-h]=temp;
			}
		}
		h=h/3;
	}
}

基数排序

时间复杂度是(n*k),是一种稳定的排序算法，排序时没有进行比较操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public void radixsort(int[] array)
{
	int max=array[0];
	ArrayList[] list=new ArrayList[10];
	for(int i=0;i<10;i++)
	{
		list[i]=new ArrayList<Integer>();
	}
	for(int i=0;i<array.length;i++)
	{
		if(array[i]>max)
			max=array[i];
	}
	//k保存最大值的位数
	int k=0;
	while(max>0)
	{
		max=max/10;
		k++;
	}
	int t=1;
	//从最低位到最高位
	for(int j=1;j<=k;j++)
	{
		for(int i=0;i<array.length;i++)
		list[array[i]/t%10].push(array[i]);
		int index=0;
		for(int i=0;i<10;i++)
		{
			while(list[i].size()>0)
				array[index++]=list[i].pop();
		}
		t=t*10;
	}
}

堆排序

  1. 任何一个节点的值都大于其子节点的值就是大顶堆
  2. 任何一个节点的值都小于其子节点的值就是小顶堆
  3. 堆排序思想： 将待排序的数组构建成一个大顶堆，此时已经确定了最大
    元素，最大元素与末尾元素进行交换，剩余的元素继续构建成一个大顶堆重
    复之前的操作。如果要得到倒序数组就要构建小顶堆，思想与构建大顶堆的
    思想一致
  4. 构建堆时时间复杂度为O(n)，一次重建堆的时间复杂度是O(logn)，堆排序的
    时间复杂度是O(nlogn)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    public void sort(int[] array)
    {
    	/*一开始要先构建一个大顶堆，应该从中间的元素开始，数组的每个
    	位置都已经是一个子堆的根节点了，跳关所有大小为1的子堆
    	*/
    	int N=array.length;
    	for(int i=array.length/2-1;i>=0;i--)
    	{
    		sink(array,i,N);
    	}
    	//堆排序过程，每次都与最大元素进行交换
    	for(int i=array.length-1;i>0;i--)
    	{
    		int temp=array[i];
    		array[i]=array[0];
    		array[0]=temp;
    		sink(array,0,i);
    	}
    }
    public void sink(int[] array,int k,int length)
    {
    	for(int j=2*k+1;j<length;j=2*j+1)
    	{
    		//当前节点的子节点中较大的那个节点
    		if(j+1<length&&array[j]<array[j+1])
    			j++;
    		//当前节点与子节点进行比较交换
    		if(array[j]>array[k])
    		{
    			int temp=array[k];
    			array[k]=array[j];
    			array[j]=temp;
    			k=j;
    		}
    		else
    		{
    			break;
    		}
    	}
    }

数据结构

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的
数据元素的集合
一个数据结构必须能实现以下4大功能

  1. 如何插入一条新的数据项
  2. 如何寻找某一特定的数据项
  3. 如何删除某一特定的数据项
  4. 如何迭代的访问各个数据项，以便进行显示或其他操作

数组

数组几乎能够表示一切的数据结构，数组有两种声明方式，一种是动态另一种是静
态，是只能用来存放同一种数据类型的集合。数组也叫做顺序线性表，在内存中是
一块连续的存储空间，链表是链式存储的线性表，在内存中空间不连续。线性表应
满足的条件是：有且只有一个根结点，除了头尾两个节点以外，每个节点又有一
个前节点和一个后节点。但正因为连续存储，内存空间必须一次性分配够，所以
说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时
间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面
的所有数据以保持连续，时间复杂度O(N)

1
2
3
4
//动态
int[] array=new int[3];
//静态
int[] array={1,2,3};

数组是通过索引来访问元素，如果知道元素的索引那么查找的效率就是O(1)，如果
不知道要查找元素的索引那么查找的效率就是O(n)。关联数组不是数组，是一个抽
象的数据结构，包含键值对的序列，例如哈希表

模拟ArrayList

Java集合中的ArrayList底层就是用数组实现，现在实现数据结构基本的4大功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class Array
{   
	//封装所以属性
	private int[] array;
	//数组的有效长度
	private int size;
	//数组创建后大小就固定了，扩展性较差
	public Array()
	{
		array=new int[0];
	}
	public Array(int initialCapacity)
	{
		array=new int[initialCapacity];
	}
	//返回有效长度
	public int getSize()
	{
		return size;
	}
	//遍历所有元素
	public void display()
	{
		for(int i=0;i<size;i++)
			System.out.print(array[i]+" ");
		System.out.println();
	}
	public boolean add(int value)
	{
		//暂时不考虑越界问题
		array[size++]=value;
	}
	//知道索引查找值，时间复杂度就是O(1)
	public int get(int i)
	{
		return array[i];
	}
	//知道值查找索引，时间复杂度就是O(n)
	public int find(int value)
	{
		for(int i=0;i<size;i++)
			if(array[i]==value)
				return i;
  		return -1;
	}
	//时间复杂度是O(n)
	public boolean remove(int i)
	{
		for(int j=i+1;j<size;j++)
			array[j-1]=array[j];
		size--;
		return true;
	}
	public boolean modify(int i,int value)
	{
		array[i]=value;
		return true;
	}
}

栈

栈作为一种数据结构是一种只能在一端插入和删除的特殊线性表，按照先进后出的
原则存储数据，允许插入和删除的一端是栈顶，另一端是栈底
栈这种数据结构具有记忆功能，比如浏览网页时先后进入ABC，那么返回时的网页
顺序就是CBA

模拟Stack

Java集合中的Stack底层就是用数组实现栈这种数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Stack
{
	private int[] array;
	private int size;
	int top=-1;
	public Stack(int length)
	{
		array=new int[length];
	}
	//入栈
	public void push(int value)
	{
		array[++top]=value;
		size++;
	}
	//出栈
	public int pop()
	{
		return array[top--];
		size--;
	}
	//访问栈顶元素
	public int peek()
	{
		return array[top];
	}
	public boolean isEmpty()
	{
		return top==-1;
	}
}

队列

队列是一种在前端删除后端插入的线性表，在队头删除队尾插入，双向队列在两端
都可以插入和删除

顺序队列

必须申请一片连续的存储空间，并设置两个指针进行管理，一个是队头指针front，
指向队头元素，另一个是队尾指针rear，指向下一个入队元素的存储位置
当rear==front时表示队列中没有任何元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Queue
{
	private int[] array;
	private int front;
	private int rear;
	private int size;
	public Queue(int length)
	{
		array=new int[length];
		front=0;
		rear=0;
	}
	public void insert(int value)
	{
		array[rear++]=value;
		size++;
	}
	public void remove()
	{
		front++;
		size--;
	}
}

循环队列

为了使队列空间能够重复使用，无论插入还是删除，当rear+1或者front+1超过
所分配的队列空间，就让它指向这片空间的起止位置。当rear=front时有两种
情况，一种是队列空间为空，另一种是队列空间已满，为了区别这两种情况一
般规定队列最多有MaxSize-1个元素，当队列剩下一个空位置时队列就已经满
了，因此判定队列已满的条件就变为 front=(rear+1)%MaxSize
假设用一个大小为m的数组表示循环队列，当前循环队列的元素个数是确定的：
(rear-front+m)%m

链表

链表可以实现栈和队列等数据结构，是一种物理存储单元上非连续、非顺序的存储
结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列
结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点
包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的
指针域

单向链表

只能向一个方向也就是头结点开始遍历，用head指向头结点。LinkedList底层就
是用链表实现，单链表一般用于头部插入和删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class LinkedList
{
	private int size;
	//头结点
	private Node head;
	    class Node
	{
		int value;
		Node next;
		public Node(value)
		{
			this.value=value;
		}
	}
	//在头部添加，可以看成栈入栈操作
	public void addHead(int value)
	{
		Node node=new Node(value);
		if(size==0)
			head=node;
		node.next=head;
		head=node;
		size++;
	}
	//在头部删除，可以看成栈出栈操作
	public void deleteHead()
	{
		head=head.next;
		size--;
	}
	//查找指定元素
	public Node find(int value)
	{
		Node node=head;
		while(node!=null)
		{
			if(node.value==value)
				return node;
			node=node.next;
		}
		return null;
	}
	//删除指定元素
	public boolean delete(int value)
	{
		if(size==0)
			return false;
		Node node=head;
		Node pre=head;
		while(node!=null)
		{
			if(node.value==value)
				break;
			pre=node;
			node=node.next;
		}
		if(node==head)
		{
			head=head.next;
			size--;
			return true;
		}
		else if(node==null)
			return false;
		else
		{
			pre.next=node.next;
			size--;
			return true;
		}
	}

}

双端链表

对于单向链表，如果要在尾部添加元素必须先遍历到尾部，然后在尾部插入元素，
可以添加一个指向尾部元素的指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class LinkedList
{
	private Node head;
	private Node tail;
	private int size;
	class Node
	{
		int value;
		Node next;
		public Node(value)
		{
			this.value=value;
		}
	}
	//链表头增加
	public void addHead(int value)
	{
		Node node=new Node(value);
		if(size==0)
		{
			head=node;
			tail=node;
		}
		else
		{
			node.next=head;
			head=node;
		}
		size++;
	}
	//在链表尾增加，相当于队列增加
	public void addTail(int value)
	{
		Node node=new Node(value);
		if(size==0)
		{
			head=node;
			tail=node;
		}
		else
		{
			tail.next=node;
			tail=node;
		}
		size++;
	}
	//删除头部节点，相当于队列删除
	public boolean deleteHead()
	{
		if(size==0)
			return false;
		else if(size==1)
		{
			head=null;
			tail=null;
		}
		else
		{
			head=head.next;
		}
		size--;
		return true;
	}
}

静态链表

静态链表底层使用数组实现，兼顾了顺序表和链表的优点。数据都存储在数组中，
但是存储位置是随机的，数据之间的关系通过游标来指定。插入和删除较快，但
是要提前分配一个固定的空间。静态链表中除了数据链表外，还有一条连接空闲
位置的链表，叫做备用链表，用来回收数组中未使用或之前使用过的空间，以
便添加元素时使用

双向链表

双向链表每个节点数据都有两个指针，一个指向前节点一个指向后节点

树

树是一种抽象数据结构，用来描述具有树状结构的性质的数据集合

  • 有一个根节点
  • 每个节点有零或多个子节点
  • 每一个非根节点只有一个父节点
  • 除了根节点，每个子节点可以分为多个不相交的子树

基本概念

  1. 度 对于一个节点，拥有的子树数称为节点的度，一棵树的度是所有节点度的
    最大值
  2. 层次 从一棵树的树根开始，树根所在层为第一层，根的孩子节点为第二层，
    依此类推，一棵树的深度就是树中所有节点层次最大值
  3. 有序树 树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，
    这棵树称为有序树，反之称为无序树。在有序树中，一个结点最左边的子树
    称为第一个孩子，最右边的称为最后一个孩子
  4. 森林 有多个相互独立的树组成的集合叫做森林

二叉树

每个节点最多含有两个子节点的树称为二叉树，然后由衍生出满二叉树和完全二
叉树。满二叉树就是除了最后一层外其余层的节点都有两个子节点。完全二叉树
是满二叉树更宽松的表示，允许最后一层节点有残缺，但必须都集中在左边

二叉树的存储

二叉树可以使用两种数据结构来存储，一种是数组另一种是链表

  1. 使用数组只能用来存储完全二叉树，从根节点开始，按照层次从左往右将
    树中节点存储到数组中，对于索引为i的节点，其子节点的索引分别为2*i+1
    2*i+2
  2. 用数组来表示二叉树有限制，只能表示完全二叉树，而链式存储方式可以
    存储所有类型的二叉树，三叉链表会添加一个指向父节点的指针域 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public class Node
    {
    	int val;
    	Node left;
    	Node right;
    	public Node(int val)
    	{
    		this.val=val;
    	}
    	public Node(int val,Node left,Node right)
    	{
    		this.val=val;
    		this.left=left;
    		this.right=right;
    	}
    }

二叉树的遍历

二叉树有四种遍历方式

  1. 先序遍历 根节点->左子树->右子树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    //递归实现
    public void displaypre()
    {
    	displaypre(root);
    }
    private void displaypre(Node node)
    {
    	if(node==null)
    		return ;
    	System.out.print(node.val);
    	if(node.left!=null)
    		display(node.left);
    	if(node.right!=null)
    		display(node.right);
    }
    //非递归实现，可以使用栈这种数据结构实现
    Stack<Node> stack=new Stack<>();
    if(root!=null)
    {
    	stack.push(root);
    	while(!stack.isEmpty())
    	{
    		Node node=stack.pop();
    		System.out.println(node.val);
    		if(!node.right)
    			stack.push(node.right);
    		if(!node.left)
    			stack.push(node.left);
    	}
    }
  2. 中序遍历 左子树->根节点->右子树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    public void displaymid()
    {
    	displaymid(root);
    }
    private void displaymid(Node node)
    {
    	if(node.left!=null)
    		display(node.left);
    	System.out.print(node.val);
    	if(node.right!=null)
    		display(node.right);
    }
    //非递归实现，一直遍历左节点入栈，最后取出节点，如果有右子节点继续重复上述操作
    Stack<Node> stack=new Stack<>();
    Node node=root;
    if(node!=null)
    {
    	//node!=null 防止没有左子节点的情况
    	while(!stack.isEmpty()||node!=null)
    	{
    		while(node!=null)
    		{
    			stack.push(node);
    			node=node.left;
    		}
    		if(!stack.isEmpty())
    		{
    			node=stack.pop();
    			System.out.println(node.val);
    			node=node.right;
    		}
    	}
    }
  3. 后序遍历 左子树->右子树->根节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    public void displaypost()
    {
    	displaymid(root);
    }
    private void displaypost(Node node)
    {
    	if(node==null)
    		return ;
    	if(node.left!=null)
    		display(node.left);
    	if(node.right!=null)
    		display(node.right);
    	System.out.print(node.val);
    }
    //非递归实现
    Node node=root;
    if(node!=null)
    {
    	Stack<Node> stack=new Stack<>();
    	//上一次访问的节点
    	Node pre=null;
    	while(node!=null)
    	{
    		stack.push(node);
    		node=node.left;
    	}
    	while(!stack.isEmpty())
    	{
    		node=stack.pop();
    		//根节点被访问的条件是无右子树或右子树已经被访问
    		if(node.right==null||node.right==pre)
    		{
    			System.out.println(node.val);
    			pre=node;
    		}
    		else
    		{
    			stack.push(node);
    			node=node.right;
    			while(node.left!=null)
    			{
    				stack.push(node);
    				node=node.left;
    			}
    		}
    	}
    }
    //还有一种更为简便的非递归方式
    LinkedList<Node> res=new LinkedList<>();
    Stack<Node> stack=new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()){
    	Node node=stack.pop();
    	res.addFirst(node);
    	if(node.left!=null)
    		stack.push(node.left);
    	if(node.right!=null)
    		stack.push(node.right);
    }
  • 层次遍历 从上往下从左往右
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    if(root!=null)
    {
    	LinkedList<Node> list=new LinkedList<>();
    	Node node=root;
    	list.add(node);
    	while(!list.isEmpty())
    	{
    		node=list.poll();
    		System.out.println(node.val);
    		if(node.left!=null)
    			list.add(node.left);
    		if(node.right!=null)
    			list.add(node.right);
    	}
    }

二叉查找树

二叉查找树是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的
实现符号表功能的数据结构,每个节点的值都大于左子树所有节点的值小于右子
树所有节点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
//这里采用递归实现所有功能代码，递归实现非常简单明了
public class BST{
	private Node root; //二叉查找树的根节点
	//二叉查找树的节点数目
	public int size()
	{
		return size(root);
	}
	private int size(Node node)
	{
		if(node==null)
			return 0;
		else
			return node.N;
	}
	//通过节点值得到相应的节点
	public Node get(int value)
	{
		return get(root,value);
	}
	private Node get(Node node,int value)
	{
		if(node==null)
			return null;
		//这里采用通用方法进行比较，像int这种基本类型直接比较
		int cmp=value.compareTo(node.value);
		if(cmp>0)
			return get(node.right,value);
		else if(cmp<0)
			return get(node.left,value);
		else
			return node;
	}
	//符号表最基本的功能之插入元素
	public void put(int value)
	{
		root=put(root,value)
	}
	private Node put(Node node,int value)
	{
		//一开始不存在树就创建树
		if(node==null)
			return new Node(value,1);
		int cmp=value.compareTo(node.value);
		if(cmp>0)
			node.right=put(node.right,value);
		else if(cmp<0)
			node.left=put(node.left,value);
		//更新树的节点数目
		node.N=size(node.left)+size(node.right)+1;
		return node;
	}
	//得到二叉查找树中节点值最小的节点
	public Node getmin()
	{
		if(root==null)
			return null;
		return getmin(root);
	}
	private Node getmin(Node node)
	{
		if(node.left==null)
			return node;
		return getmin(node.left);
	}
	//得到二叉查找树中节点值最大的节点
	public Node getmax()
	{
		if(root==null)
			return null;
		return getmax(root);
	}
	private Node getmax(Node node)
	{
		if(node.right==null)
			return node;
		return getmax(node.right);
	}
	//删除二叉查找树中节点值最小的节点
	public void deletemin()
	{
		if(root!=null)
			root=deletemin(root);
	}
	private Node deletemin(Node node)
	{
		if(node.left==null)
			return node.right;
		node.left=deletemin(node.left);
		x.N=size(x.left)+size(x.right)+1;
		return node;
	}
	//删除二叉查找树中节点值最大的节点
	public void deletemax()
	{
		if(root!=null)
			root=deletemax(root);
	}
	private Node deletemax()
	{
		if(node.right==null)
			return node.left;
		node.right=deletemin(node.right);
		x.N=size(x.left)+size(x.right)+1;
		return node;
	}
	//符号表最基本功能之删除
	public void delete(int value)
	{
		root=delete(root,value);
	}
	private Node delete(Node node,int value)
	{
		 if(node==null)
		 	return null;
		 int cmp=value.compareTo(node.value);
		 if(cmp>0)
		 	node.right=delete(node.right,value);
		 else if(cmp<0)
		 	node.left=delete(node.left,value);
		 else
		 {
		 	//得到要删除的节点，此时有三种情况
		 	//该节点没有右子节点
		 	if(node.right==null)
		 		return node.left;
		 	//该节点没有左子节点
		 	if(node.left==null)
		 		return node.right;
		 	//这个时候将该节点删除后需要用一个子节点替换
		 	Node t=node;
		 	//该节点右子树中的最小节点就是要替换的节点
		 	node=min(t.right);
		 	//更新右子树
		 	node.right=deletemin(t.right);
		 	//左子树不变
		 	node.left=t.left;
		 }
		 node.N=size(node.left)+size(node.right)+1;
		 return node;
	}
}

平衡查找树

任何节点的两棵子树的高度相差不大于1的树，在一些极端情况下，二叉
查找树会退化为链表，插入的时间复杂度变为O(n)，平衡树的查找能够
在对数时间结束。以下内容参考
https://www.zhihu.com/question/30527705/answer/260005525

平衡查找树(AVL树)

AVL树是最早的平衡二叉树

B树

也叫做B-树，全称是Balance-Tree(平衡多路查找树)，平衡指左边和右边分
布均匀，多路指一个父节点可以有多于两个子节点，所有叶子节点都位于同
一层用在磁盘文件组织，数据索引和数据库索引

2-3树

2-3树是B树的一种，接下来我们先来研究2-3树的一些特性

  • 2节点 一个节点两个子树
  • 3节点 两个节点三个子树
  • 查找 比如查找H，整体过程如下：先与M比较，比M小则继续在左子树查找，
    H在E和J之间，在中子树中继续查找，找到H
  • 插入 可以先和二叉树一样进行一次未命中的查找，然后把新节点挂在树的
    底部，这样就不能保证所有叶子节点到根节点距离相同。如果为命中查找结
    束于一个2-节点，那么只需要将这个2-节点转化为3-节点。如果未命中查
    找结束于一个3-节点，分析如下
  1. 向一个只含有一个3-节点的树中插入节点，首先将这个3-节点转化为4-
    节点，然后将这个4-节点转化为3个2-节点
  2. 向一个父节点为2-节点的3-节点中插入节点，同样先构建一个4-节点，
    但此时不会为中键创建一个新节点，而是将这个节点移到父节点中，于是
    父节点就变为了3-节点
  3. 向一个父节点为3-节点的3-节点中插入节点，同样先构建一个4-节点，
    然后将中键插入到父节点中，此时再构建一个4-节点，然后向上不断分解
    临时的4-节点，知道遇见一个2-节点或者一个3-节点的根

红黑树和AVL数的区别？

  1. 调整平衡的实现机制不同 红黑树根据节点颜色一些约定和旋转实现，AVL
    根据树的平衡因子(所有节点的左右子树高度差的绝对值不超过1)和旋转决定
  2. 红黑树的插入效率更高 红黑树是用非严格的平衡来换取增删节点时候旋
    转次数的降低，任何不平衡都会在三次旋转之内解决
  3. 适用性 AVL查找效率高

红黑树

刚刚学习过2-3树，思路和结构都很简单清晰，但是实现比较困难，比如需要维
护两种不同节点以及比较转换等操作。红黑树也是一种平衡二叉树，Java源码中
HashMap底层用到了红黑树，接下来看一下红黑树是如何实现2-3树的特性

  • 每个节点要么是红色要么是黑色
  • 根节点是黑色
  • 每个叶子节点都是黑色
  • 一个红节点的两个子节点是黑色
  • 任何叶子节点到根节点路径上的黑色节点数都相同
  • 红色节点都在左边，这一条只对应当前我要实现的一种红黑树
  • 3-节点就相当于一个红节点与一个黑节点相连，然后红节点连接两个黑节
    点，将红节点与父节点放在同一位置，就对应于一个2-3树
  1. 旋转 在插入节点等操作总是先默认节点是红色的，所以可能会出现红色
    节点在右边或者出现两个连续的红节点，这些情况都需要旋转。左旋就是将
    红节点由左子变为右子，右旋是将红节点由左子变为右子，这种情况对应
    连续两个红节点，右旋后两个红节点在左右子，然后直接变为黑色父变为
    红色即可
  2. 旋转操作会返回一个节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    public class Node
    {
    	int val;
    	Node left,right;
    	int N;
    	//true代表红色，false代表黑色
    	boolean color;
    	public Node(int val,int N,boolean color)
    	{
    		this.val=val;
    		this.N=N;
    		this.color=color;
    	}
    }
    //左旋操作，h相当于上图中的x
    Node rotateLeft(Node h)
    {
    	Node x=h.right;
    	h.right=x.left;
    	x.color=h.color;
    	h.color=true;
    	x.N=h.N;
    	h.N=size(h.left)+size(h.right)+1;
    	return x;
    }
    //右旋操作，h相当于上图中的y
    Node rotateRight(Node h)
    {
    	Node x=h.left;
    	h.left=x.right;
    	x.right=h;
    	x.color=h.color;
    	h.color=true;
    	x.N=h.N;
    	h.N=size(h.left)+size(h.right)+1;
    	return x;
    }
    //右旋可能导致左右子都是红，这时需要颜色转换
    void flipColors(Node h)
    {
    	h.color=true;
    	h.left.color=false;
    	h.right.color=false;
    }
  3. 挖个坑
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    //插入算法
    public void put(int val)
    {
    	root=put(root,val);
    	root.color=false;
    }
    private Node put(Node h,int val)
    {
    	if(h==null)
    		return new Node(val,1,true);
    	if(val<h.val)
    		h.left=put(h.left,val);
    	else if(val>0)
    		h.right=put(h.right,val);
    	else
    		h.val=val;
    	if(h.right&&!h.left)
    		h=rotateLeft(h);
    	if(h.left&&h.left.left)
    		h=rotateRight(h);
    	if(h.left&&h.right)
    		flipColors(h);
    	h.N=size(h.left)+size(h.right)+1;
    	return h;
    }

哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树

  • 一个节点到另一个节点之间的通路叫做路径
  • 节点的带权路径长度 从根节点到该该节点的路径长度乘以节点的权

对于有权值的n个节点组成的集合，先取出权值最小的两个节点组成一个二叉树，根
节点为左右子节点权值之和，将新节点放入节点集合中重复上述操作 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class Main{
    Node root;
    public void createTree(LinkedList<Node> list)
    {
        while(list.size()>1)
        {
            Node left=list.poll();
            Node right=list.poll();
            Node node=new Node(left.weight+right.weight);
            node.left=left;
            node.right=right;
            list.add(node);
            list.sort((o1,o2)->{
                return o1.weight-o2.weight;
            });
        }
        root=list.poll();
    }
    public void addname(Node node)
    {

    }
    public void print()
    {
        if(root.left!=null)
            print(root.left,"0");
        if(root.right!=null)
            print(root.right,"1");
        LinkedList<Node> list=new LinkedList<>();
        Node node=root;
        list.add(node);
        while(!list.isEmpty())
        {
            node=list.poll();
            System.out.println(node);
            if(node.left!=null)
                list.add(node.left);
            if(node.right!=null)
                list.add(node.right);
        }
    }
    public void print(Node node,String name)
    {
        node.name=name;
        if(node.left!=null)
            print(node.left,name+"0");
        if(node.right!=null)
            print(node.right,name+"1");

    }
    public static void main(String[] args) {
        LinkedList<Node> list=new LinkedList<>();
        list.add(new Node(7,"a"));
        list.add(new Node(5,"b"));
        list.add(new Node(2,"c"));
        list.add(new Node(4,"d"));
        list.sort((o1,o2)->{
            return o1.weight-o2.weight;
        });
        Main a=new Main();
        a.createTree(list);
        a.print();

     }
}
class Node implements Comparable
{
    String name;
    String data;
    int weight;
    Node left;
    Node right;
    public Node(int weight,String data){
        this.weight=weight;
        this.data=data;
    }
    public Node(int weight){
        this.weight=weight;
    }
    public int compareTo(Object node)
    {
        return weight-((Node)node).weight;
    }
    public String toString()
    {
        return name+" "+data+" "+weight;
    }
}

优先队列

许多应用程序都需要处理有序元素，但是不一定全部有序。例如只处理当前最大
值或者最小值，一台电脑能够同时运行多个程序，每个程序都有一个优先级，
并会总是先处理优先级高的程序，这种情况一个合适的数据结构应该支持两
中操作：删除最大值和插入元素。这就是优先队列，数组和链表是实现优先
队列的最简单方式，但是插入和删除的时间复杂度总有一个是O(N)

堆

数据结构二叉堆能很好实现优先队列的基本操作。在二叉堆的数组中，每个元素
都要保证大于等于另外两个特定元素。当一棵二叉树的每个节点都大于等于它的
两个子节点，被称为堆有序
如果用指针来表示堆有序的二叉树，每个元素都需要三个指针来找到它的上下
节点，如果使用完全二叉树的话就不需要使用指针，只需要数组就可以完成
全部操作，具体方法就是将二叉树的节点按照层次顺序放入数组中，根节点
放在索引位置1，它的子节点放在2和3，不使用0位置。这就是二叉堆

堆的算法

二叉堆中位置为k的节点的父节点位置为k/2，而它的两个子节点位置为2k和
2k+1，高效的算法能够实现在对数时间内插入和删除，一棵大小为N的完全
二叉树高度不会超过lgN

  1. 用一个长度为N+1的数组表示一个大小为N的堆，堆的操作会首先进行一些
    简单的改动，打破堆的状态，然后再遍历堆并按要求将堆恢复，这个过程叫
    有序化
  2. 有序化的过程会遇到两种情况，当某个节点优先级上升需要由下至上恢复
    堆的顺序，当某个节点优先级下降需要由上至下恢复堆的顺序
  3. 插入元素 将新元素插入到数组某位，增加堆的大小并让这个元素上浮到
    合适位置
  4. 删除最大元素 从数组顶端删除最大元素并将最后一个元素放到数组顶端，
    减少堆的大小并让这个元素下沉到合适位置
  5. 基于堆的优先队列 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    public class MaxPQ
    {
    	private int[] pq;
    	private int N=0;
    	public MaxPQ(int max)
    	{
    		pq=new int[max+1];
    	}
    	public void insert(int val)
    	{
    		pq[++N]=val;
    		swim(N);
    	}
    	public int delMax()
    	{
    		int max=pq[1];
    		pq[1]=pq[N];
    		N--;
    		sink(1);
    		return max;
    	}
    	private void swim(int k)
    	{
    		while(k>1&&pq[k]>pq[k/2])
    		{
    			int temp=pq[k];
    			pq[k]=pq[k/2];
    			pq[k/2]=temp;
    			k=k/2;
    		}
    	}
    	private void sink(int k)
    	{
    		while(2*k<=N)
    		{
    			int j=2*k;
    			if(j<N&&pq[j]<pq[j+1])
    				j++;
    			if(pq[k]>pq[j])
    			{
    				int temp=pq[k];
    				pq[k]=pq[j];
    				pq[j]=temp;
    				k=j;
    			}
    			else
    				break;

    		}
    	}
    }

描述堆的创建过程？

建堆有两种方式

  1. 自顶向下的建堆方式 这种建堆的方法具有O(n*log2n)的时间复杂度
    。从根结点开始，然后一个一个的把结点插入堆中。当把一个新的结点插入
    堆中时，需要对结点进行调整，以保证插入结点后的堆依然是大根堆
  2. 自下向上的建堆方式 这种建堆的方法具有O(n) 的时间复杂度，从第一
    个非叶子结点开始进行判断该子树是否满足堆的性质。如果满足就继续判断
    下一个点。否则，如果子树里面某个子结点有最大元素，则交换他们，并依
    次递归判断其子树是否仍满足堆性质
  3. 于是，有1/2的元素向下比较了一次，有1/4的向下比较了两次，1/8的
    ，向下比较了3次，1/2^k的向下比较了k次，其中1/2^k <= 1, k 约等于
    lg(n)

了解LFU 吗？

  1. 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将
    来一段时间内被使用的可能性也很小
  2. 需要有一个HashMap来保存key到val的映射，用来计算 get(key)
  3. 需要有一个HashMap来保存key到freq的映射，用来计算每一个key的频次
  4. 需要freq到key的映射，用来找到最小freq对应的key，可以通过一个变
    量minFreq来记录当前最小freq，避免遍历
  5. 可能会有多个key拥有相同的freq，所以freq和key是一对多的关系，那么
    就需要维护一个freq到key对应的映射关系
  6. 为了保证快速查找并删除最旧的key，就需要保证freq对应的key的映射列
    表应该是有顺序的
  7. 需要能够快速删除key列表中的任何一个key。如果频次为freq的key被访问
    了，它的频次应该变成freq+1，此时应该从freq对应的key列表中删除，并把
    key加入到freq+1对应的key列表中 => 就是需要提高它的频次
Author: 高明
Link: https://skysea-gaoming.github.io/2020/02/28/Algorithm/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
DataStructure