数组

优点

  • 下标访问的复杂度为O(1)
  • 末尾位置增加删除元素时间复杂度为O(1) 删除就是–，增加就是++

缺点

  • 非末尾元素增加位置需要大量的数据移动
  • 搜索的复杂度是O(n) 注意搜索和访问不是一个东西，搜索是遍历寻找这个值，而访问是a[0]–a[n-1]，在无序数组中采用遍历，是线性搜索；在有序数组中采用二分，复杂度为O(logn)

链表

优点

  • 内存利用率高，不需要大块连续内存
  • 插入和删除节点不需要移动其它节点，时间复杂度O(1)
  • 不需要专门进行扩容操作

缺点

  • 内存占用量大，每一个节点多出存放地址的空间
  • 节点内存不连续，无法进行内存随机访问
  • 链表搜索效率不高，只能从头节点开始逐节点遍历

内存碎片化


现在我们有100M的内存空间（堆上），内存的释放是一块一块的，谁用完了谁就被释放了，如果将中间的20M和最右边的10M手动释放掉；我们就得到了两块内存碎片；现在我们有30M的空闲空间。

如果现在进程运行需要25M的内存空间，我们能不能分配25M的数组呢？ 不能，数组的内存是绝对连续的
在内存碎片过多的情况下，无法开辟大数组，这时候就可以用链表，每一个节点都是独立new出来的

从头节点访问到最后一个节点，最后一个节点的地址域为NULL。

1
2
3
4
5
struct Node{
    Node(int data = 0) : data_(data),Next_(nullptr){} 
    int data_;
    Node *Next_;
};

结构体其实就是一个public的类，现在写了一个Node的构造函数，如果不传参默认data就是0。为什么后面要加一个大括号？因为前面在初始化，初始化已经完成了，后面是函数体{}可以是空的。
不要总去判断当前节点的下一节点是否为空，老老实实判断当前节点是否为空，除非你真的要去找末尾节点。

链表接口

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
#include <iostream>
#include <time.h>
using namespace std;

struct Node{
	Node(int data = 0):data_(data),next_(nullptr){}
	int data_;
	Node *next_;
};

class Clink{
	public:
		Clink()
		{
			//给head初始化，指向头节点 
			head = new Node();
		}
		~Clink()
		{
			Node *p = head;
			while (p!=nullptr)
			{
				head = head->next_;
				delete p;
				p = head;
			}
		}
	public:
		//尾插法 复杂度O(n) 因为要遍历整个链表 
		void InsertTail(int val)
		{
			//先找到当前链表的末尾节点
			Node *p = head;
			while(p->next_!=nullptr)
			{
				p = p->next_;
			}
			//生成新节点 
			Node *node = new Node(val);
			p->next_ = node;
		}
		// 头插法 复杂度O(1) 因为直接找到头节点的下一节点 
		void InsertHead(int val)
		{
			Node *node = new Node(val);
			node->next_ = head->next_;
			head->next_ = node;
		}
		// 链表单个节点删除 用双节点法 
		void Remove(int val)
		{
			Node *p = head->next_;
			Node *q = p; //q永远跟在p后面 
			while(p!=nullptr)
			{
				if (p->data_==val)
				{
					q->next_ = p->next_;
					delete p;
					return; 
				}
				else
				{
					q = p; 
					p = p->next_;
						
				}
			}
		}
		void RemoveAll(int val)
		{
			Node *p = head->next_;
			Node *q = head;
			while(p!=nullptr)
			{
				if (p->data_==val)
				{
					q->next_ = p->next_;
					delete p; //delete只是释放指针指向的内存，指针本身不改变 
					p = q->next_;
				}
				else
				{
					q = p;
					p = p->next_;
				}
			}
		} 
		
		// 打印链表 
		void show()
		{
			Node *p = head->next_;
			while (p!=nullptr)
			{
				cout<<p->data_<<" ";
				p = p->next_;
			}
			cout<<endl;
		}
		
		//搜索
		bool Find(int val)
		{
			Node *p = head->next_;
			while (p!=nullptr)
			{
				if (p->data_==val)
				{
					return true;
				}
				else
				{
					p = p->next_;	
				}	
			}	
		} 
	private:
		//指向链表的头节点 
		Node *head;
};

int main()
{
	Clink c;
	srand(time(0));
	for (int i = 0;i<10;i++)
	{
		int val = rand()%100;
		c.InsertHead(val);
		cout<<val<<" ";
	}
	cout<<endl;

	c.InsertHead(23);
	c.InsertHead(23);
	c.InsertTail(23);
	c.show();
	c.RemoveAll(23);
	c.show();
}

总结：

  • 数组：下标访问/随机访问多、搜索
  • 链表：增加、删除多
    不过还是要看插入哪里，如果插入中间位置都是O(n)

后续我自己rewrite发现语法出问题

1
2
3
4
5
6
7
8
public:
		mylink(){
			Node head();
			//head = new Node();
		}
		~mylink(){
			
		}

我一开始写的是没有注释的 Node head() 这样程序无法运行，为什么呢？因为这是一个函数声明，返回值为Node的函数声明！并没有创造出对象！所以我们需要new一个对象出来！
而且不要空想一个头节点，题目如果给你链表是:1,2,3,4,5。那就是这样，第一个节点就是头节点。

  • 单链表逆序 头插法
  • 单链表求倒数第k个节点 双指针，第一个指针先移动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
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
#include <iostream>
#include <time.h> 
using namespace std;

//顺序栈 c++stack push,pop, 
 
class SeqStack{
	public:
		SeqStack(int size = 10) : mtop(0),mcap(size)
		{
			mpStack = new int[mcap];
		}
		~SeqStack()
		{
			delete []mpStack;
			mpStack = nullptr;
		}
	public:
		//入栈 
		void push(int val)
		{
			if (mtop==mcap)
			{
				expand();
			}
			mpStack[mtop++] = val;
		}
		//出栈
		void pop()
		{
			if (mtop==0) throw "stack is empty!";
			mtop--;
		}
		//获取栈顶元素
		int top() const
		{
			if (mtop==0) throw "stack is empty!";
			return mpStack[mtop-1];
		}
		//栈空
		bool empty()
		{
			return mtop==0;
		}
		int size()
		{
			return mtop;
		}
	private:
		void expand()
		{
			int *p = new int[mcap*2];
			for (int i = 0;i<mcap;i++)
			{
				p[i] = mpStack[i];
			}
			delete []mpStack;
			mpStack = p;
			mcap = 2*mcap;
		}
	private:
		int *mpStack;
		int mtop; //栈顶位置 
		int mcap; //栈空间大小 
};

int main()
{
	srand(time(0));
	SeqStack stack(5);
	for (int i = 0;i<5;i++)
	{
		stack.push(rand()%10);
	}
	stack.push(10);
	while (!stack.empty())
	{
		cout<<stack.top()<<" ";
		stack.pop();
	}
}

队列

环形队列

不能用++，留下一个位置来判断是否为空

  • 入队:(rear+1)%length
  • 出队（first+1）%length
  • 满 (rear+1)%length =first
  • 空rear = rear

排序算法

  • 冒泡排序：相邻两两元素比较，值大/小的元素往下交换；缺点：数据交换次数太多
  • 选择排序：每次在剩下的数据选择最大/最小的数据和当前元素进行交换；缺点：交换次数仍然多
  • 插入排序：**如果数据趋于有序，那么插入排序是所有排序算法中效率最高的算法！**插入排序效率>冒泡&&选择，不仅没有交换，而且比较的次数也少。
  • 希尔排序：插入排序PLUS，从全局先将数据调整为趋于有序。对数据进行分组插入排序
  • 快速排序：选取一个基准数，把小于基准数的元素放到基准数左边，大于基准数的元素放在右边；然后对基准数两边的序列进行同样的操作（递归）
  • 归并排序: 二路归并

冒泡排序

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
#include <iostream>
#include <time.h>
#include <vector>
using namespace std;

void bubble(vector<int>&arr)
{
	for (int i = 0;i<arr.size();i++)
	{
		for (int j = 0;j<arr.size()-i-1;j++)
		{
			if (arr[j]>arr[j+1])
			{
				swap(arr[j],arr[j+1]);
			}
		}
	}
}

void show(vector<int> &arr)
{
	for (auto a: arr)
	{
		cout<<a<<" ";
	}
}

int main()
{
	srand(time(0));
	vector<int> arr;
	for (int i = 0;i<10;i++)
	{
		arr.push_back(rand()%100);
	}
	bubble(arr);
	show(arr);
	
}

冒泡排序就是像气泡一样，慢慢往下沉或慢慢往上浮，j循环是数组的大小-i-1;对于函数传参，我们如果定义普通的数组的话，传(int arr[],int n)，数组名就是一个指针。
复杂度：外层循环O(n)，内层循环也是一个O(n)，O(n方)
为什么j是size-1-i，因为a[j]要和a[j+1]来比较，所以有-1，每一次排序都会排好一个数，所以-i，第一次没排好，第二次排了1个少循环一次。

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
void SelectSort(vector<int> &arr)
{
	for (int i = 0;i<arr.size();i++)
	{
		int maxIndex = i;
		for (int j = i;j<arr.size();j++)
		{
			if (arr[j]>arr[maxIndex]) maxIndex = j;
		}
		swap(arr[i],arr[maxIndex]);
	}
}

存放最大值/最小值的下标，比较结束后用下标来索引交换。
复杂度O(n)O(n)，是一个*不稳定的排序算法 //5 5 3,第一个5和3交换后这个5跑去后面了。

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InsertSort(vector<int> &arr)
{
	for (int i = 1;i<arr.size();i++)
	{
		int j = i-1;
		int val = arr[i];
		for (;j>=0;j--)
		{
			if (val>=arr[j])
			{
				break;
			}
			arr[j+1] = arr[j];
		}
		arr[j+1] = val;
	}
}


为什么i要从1开始？因为之前的序列默认有序了，定义j在外面是为下面能成功访问j。
时间复杂度最坏O(n)*O(n)，最好O(n)；空间O(1)。稳定性好，

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InsertSort(vector<int> &arr)
{
	for (int gap = arr.size()/2;gap>0;gap/=2)
	{
		for (int i = gap;i<arr.size();i++)
		{
			int val = arr[i];
			int j = i-gap;
			for (;j>=0;j-=gap)
			{
				if (val>=arr[j])
				{
					break;
				}
				arr[j+gap] = arr[j];
			}
		arr[j+gap] = val;
		}
	}
}

时间复杂度O(n)*O(n)最坏，最好O(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
int Partition(vector<int> &arr,int l,int r)
{
	int val = arr[l]; //最左边的当作基准数
	//l == r的位置就是放基准数的位置 
	while (l<r)
	{
		while (l < r &&arr[r] > val)
		{
			r--;
		}
		
		if (l < r)
		{
			arr[l] = arr[r];
			l++;
		}
		while (l<r&&arr[l]<val)
		{
			l++;
		}
		if (l < r)
		{
			arr[r] = arr[l];
			r--;
		}
	}
	arr[l] = val;
	return l;
}

void QuickSort(vector<int> &arr,int begin,int end)
{
	if (begin >= end) return;
	int pos = Partition(arr,begin,end);
	QuickSort(arr,begin,pos-1);
	QuickSort(arr,pos+1,end);
}

QuickSort(a,0,a.size()-1);

函数传参的时候是要传起始位置，而不是具体的a[0]。
时间复杂度O(nlogn)，空间复杂度O(logn) 二叉树递归所占用的栈内存
是不稳定的排序

快速排序的优化

  • 排的越来越有序的时候，找一个合适的地方调用插入排序，因为插入排序是效率最高的当趋于有序的时候
  • 采用三数取中法，L，R，Mid（（l+r）/），取这三个数值在中间的数作为基准数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int medianOfThree(vector<int>& arr, int l, int r) {
    int mid = l + (r - l) / 2;
    if (arr[l] > arr[mid]) swap(arr[l], arr[mid]);
    if (arr[l] > arr[r]) swap(arr[l], arr[r]);
    if (arr[mid] > arr[r]) swap(arr[mid], arr[r]);
    swap(arr[l], arr[mid]); // 将中位数放到最左边
    return arr[l];
}

int Partition(vector<int>& arr, int l, int r) {
    int val = medianOfThree(arr, l, r);
    // 原先 Partition 的逻辑保持不变
    while (l < r) {
        while (l < r && arr[r] > val) r--;
        if (l < r) arr[l++] = arr[r];
        while (l < r && arr[l] < val) l++;
        if (l < r) arr[r--] = arr[l];
    }
    arr[l] = val;
    return l;
}

优化后的算法

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
const int INSERTION_SORT_THRESHOLD = 16;

int medianOfThree(vector<int>& arr, int l, int r) {
    int mid = l + (r - l) / 2;
    if (arr[l] > arr[mid]) swap(arr[l], arr[mid]);
    if (arr[l] > arr[r]) swap(arr[l], arr[r]);
    if (arr[mid] > arr[r]) swap(arr[mid], arr[r]);
    swap(arr[l], arr[mid]); // 中位数放到最左边
    return arr[l];
}

int Partition(vector<int>& arr, int l, int r) {
    int val = medianOfThree(arr, l, r);
    while (l < r) {
        while (l < r && arr[r] > val) r--;
        if (l < r) arr[l++] = arr[r];
        while (l < r && arr[l] < val) l++;
        if (l < r) arr[r--] = arr[l];
    }
    arr[l] = val;
    return l;
}

void InsertionSort(vector<int>& arr, int l, int r) {
    for (int i = l + 1; i <= r; ++i) {
        int key = arr[i], j = i - 1;
        while (j >= l && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void QuickSort(vector<int>& arr, int begin, int end) {
    if (end - begin + 1 <= INSERTION_SORT_THRESHOLD) return;
    int pos = Partition(arr, begin, end);
    QuickSort(arr, begin, pos - 1);
    QuickSort(arr, pos + 1, end);
}

void HybridSort(vector<int>& arr) {
    QuickSort(arr, 0, arr.size() - 1);
    InsertionSort(arr, 0, arr.size() - 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//归并过程
void Merge(vector <int> &arr,int l,int mid,int r)
{
	int *p = new int[r-l+1];  //38 62 99     75 81   4-0+1=5
	int index = 0;
	int i = l;
	int j = mid + 1;
	while (i<=mid&&j<=r)
	{
		if (arr[i]<=arr[j])
		{
			p[index++] = arr[i++];
		}
		else
		{
			p[index++] = arr[j++];
		}
	}
	while (i <= mid)
	{
		p[index++] = arr[i++];
	}
	while (j <= r)
	{
		p[index++] = arr[j++];
	}
	//再把合并好的大段有序结果，拷贝回arr[r,l]区间内 
	for (i = l,j = 0;i <=r;i++,j++)
	{
		arr[i] = p[j];
	}
	delete []p;
	 
}

void MergeSort(vector<int> &arr,int begin,int end)
{
	if (begin>=end) return;
	//要先进行递，才能进行归
	int mid = (begin + end)/2;
	MergeSort(arr,begin,mid);
	MergeSort(arr,mid + 1,end);
	//再归并，把两个小段有序的序列合并成大段
	Merge(arr,begin,mid,end); 
}

void MergeSort(vector<int> &arr)
{
	MergeSort(arr,0,arr.size()-1);
}

是一个稳定的算法

堆排序

二叉堆&大根堆&小根堆


完全二叉树的最后一层叶子节点靠左排列，用数组存放的数在逻辑上可以被视为完全二叉树，2i+
1和2i+2
大根堆和小根堆只是基于二叉堆的基础规定了当前节点和两个孩子节点值的大小关系。

  • 叶子节点（树枝的末端，没有子节点）找到第一个非叶子节点：(末位元素下标-1)/2

  • 大根堆：arr[i] > arr[i2+1]&&arr[i] > arr[i2+2]

  • 小根堆：arr[i] < arr[i2+1]&&arr[i] < arr[i2+2]
    操作堆的时候像队列/栈一样，只能操作堆顶元素

  • STL里的sort算法用的是什么排序？
    快速排序 + 插入排序 （32的时候转为插入） + 堆排序（递归深度过深）

  • 快速排序的时间复杂度不是稳定的nlogn，如何解决恶化问题
    1.转插入排序 2.三数取中，选择合适的基准数

  • 递归过深会引发什么问题？
    函数开销变大，导致栈内存溢出，程序挂掉

  • 怎么控制递归深度？如果达到递归深度了还没排完序怎么办？
    转换成非递归的排序方式，如堆排序，好坏都是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
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
#include <iostream>
#include <functional>
#include <time.h> 
using namespace std;

class PriorityQueue{
	public://using是定义类型别名，这里定义了一个Comp的比较大小函数 
		using Comp = function<bool(int,int)>; 
		PriorityQueue(int cap = 20,Comp comp = greater<int>()) //默认大根堆 
			:size_(0)
			,cap_(cap)
			,comp_(comp)
			{
				que_ = new int[cap];
			}
		PriorityQueue(Comp comp) //小根堆，通过传比较器对象实现 
			:size_(0)
			,cap_(20)
			,comp_(comp)
			{
				que_ = new int[cap_];
			}
		~PriorityQueue()
		{
			delete []que_;
			que_ = nullptr;
		}
	public:
		//入堆
		void push(int val)
		{
			if (size_==cap_)
			{
				int *p = new int[2*cap_];
				for (int i = 0;i<cap_;i++)
				{
					p[i] = que_[i];
				}
				delete []que_;
				que_ = p;
				cap_ = 2*cap_;
			}
			
			if (size_==0)
			{
				//只有一个元素不用上浮调整。 
				que_[size_] = val; 
			}
			else
			{
				//有多个元素，插入位于大小位置的下标 
				ShiftUp(size_,val);
			}
			size_++;
		}
		void pop()
		{
			if (size_ == 0)
			{
				throw "The container is empty";
			}
			size_--;
			if (size_ > 0)
			{
				//删除堆顶元素，还有剩余的元素，进行下沉
				ShiftDown(0,que_[size_]); 
			}
		 }
		bool empty() const {return size_==0;}
		int top() const
		{
			return que_[0];
		}
		int size()
		{
			return size_;
		}
		
	private:
		void ShiftUp(int i,int val)
		{
			while (i > 0) //最多计算到根节点 
			{
				int father = (i-1)/2;
				if (comp_(val,que_[father]))
				{
					que_[i] = que_[father];
					i = father;
				}
				else break;
			}
			que_[i] = val;
		}
		void ShiftDown(int i,int val)
		{
			while (i<size_/2)
			{
				int child = 2*i +1;
				if (child + 1 <size_&&comp_(que_[child+1],que_[child]))
				{
					child = child + 1; //如果右孩子的值大于左孩子，child记录右孩子的下标
					 
				}
				if(comp_(que_[child],val))
				{
					que_[i] = que_[child];
					i = child;
				 }
				 else
				 {
				 	break; //已经满足了堆的性质，提前出 
				 }
			}
			que_[i] = val;
		}
	
	private:
		int *que_; //指向动态扩容的数组 
		int size_; //元素个数
		int cap_; //数组的总空间大小
		Comp comp_; //比较器对象 
		
}; 

int main()
{
	//PriorityQueue que; //第一个构造函数 
	PriorityQueue que([](int a,int b){return a<b;});//第二个构造函数 
	srand(time(0));
	for (int i = 0;i < 30;i++)
	{
		que.push(rand()%100);
	}
	while (!que.empty())
	{
		cout<<que.top()<<" ";
		que.pop();
	}
	cout<<endl;
}

哈希表

快速的查询时要第一时间想到哈希表。

  • 有序的关联容器：set\map （红黑树实现，O(logn)）
  • 无序的关联容器：unordered_set\unordered_map （哈希表O(1)）

通过哈希函数（除留余数法实现）

  • 如何解决哈希冲突？
    1.线性探测法 2.链地址法
    3.设置哈希表的长度为素数，可以尽可能的减少哈希冲突
  • 如果你长度为8，有很多能mod8的数都会被存到同一个位置；如果是素数，则会减少一些。

4.设置哈希表装载因子（已用个数/容量）

  • 一般是0.75，超过了0.75后就要将哈希表扩容，扩容会从素数表里面找下一个质数作为新的容量，原来哈希表中的元素需要在新的哈希表中重新哈希

查找
未发生哈希冲突 O(1) 比如18%7 = 4，去看arr[4]有无18；如果发生了哈希冲突，就要往后去遍历，O(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
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
using namespace std;

enum State{
	STATE_UNUSE, 
	STATE_DELETE, //在哈希表中，我们删除元素不用置成0，而是设置状态 
	STATE_USING,
};

//不要用vector，vector会自动扩容，我们自己用指针来 

struct Bucket{
	Bucket(int key = 0,State state = STATE_UNUSE)
		:key_ (key),state_(state){}
	int key_; //存储的数据 
	State state_; //桶的当前状态 
	
};
//创建一个类，先去处理成员变量 
class HashTable
{
	public:
		HashTable(int size = primes_[0],double LoadFactor = 0.75)
			:useBucketNum_(0)
			,loadFactor_(LoadFactor)
			,primeIdx_(0)
		{
			//把用户传入的size调整到最近的比较大的素数上（因为用户可能传入非素数）	
			if (size != primes_[0])
			{
				for (;primeIdx_<PRIME_SIZE;primeIdx_++)
				{
					if (primes_[primeIdx_]>size)
					{
						break;
					}
					if (primeIdx_ == PRIME_SIZE)
					{
						primeIdx_--;
					}
				}
			}
			tableSize_ = primes_[primeIdx_];
			table_ = new Bucket[tableSize_];
		}
		~HashTable()
		{
			delete []table_;
			table_ = nullptr;
		}
	
	public:
		bool insert(int key)
		{
			double factor = useBucketNum_*1.0 / tableSize_;
			cout<<"factor:"<<factor<<endl;
			if (factor > loadFactor_)
			{
				expand();
			}
		int idx = key % tableSize_;
		int i = idx;
		do
		{
			if (table_[i].state_!=STATE_USING)
			{
				table_[i].state_ = STATE_USING;
				table_[i].key_ = key;
				useBucketNum_++;
				return true;
			}
			i = (i + 1)%tableSize_;
		}while (i!=idx);
			/*
			if (table_[idx].state_!= STATE_USING)
			{
				table_[idx].state_ = STATE_USING;
				table_[idx].key_ = key;
				return true;
			}
			//如果第一个位置是被using的，那就从idx往下找，让数组成环 
			for (int i = (idx+1)%tableSize_;i!=idx;i=(i+1)%tableSize_)
			{
				if (table_[i].state_!=STATE_USING)
				{
						
				} 		
			}*/
			//代码重复冗余，用dowhile优化，因为一开始就要做一次判断 
			return false;
		}
		
		bool erase(int key)
		{
			int idx = key % tableSize_;
			int i = idx;
			do
			{
				if (table_[i].state_==STATE_USING&&table_[i].key_==key)
				{
					table_[i].state_ = STATE_DELETE;
					useBucketNum_--;
				}
				i = (i+1)%tableSize_;
			}while (table_[i].state_!=STATE_UNUSE&&i !=idx ); //遇到了unuse说明发生冲突后也没往后插了 
			return true;
		}
		
		bool find(int key)
		{
			int idx = key % tableSize_;
			int i = idx;
			do
			{
				if (table_[i].state_==STATE_USING&&table_[i].key_==key)
				{
					return true;
				}
				i = (i+1)%tableSize_;
			}while (table_[i].state_!=STATE_UNUSE && i != idx); //遇到了unuse说明发生冲突后也没往后插了 
			return false;
		}
	
	
	private:
		void expand()
		{
			++primeIdx_;
			if (primeIdx_ == PRIME_SIZE)
			{
				throw "HashTable is large enought and it can't be expanded";
			}
			
			Bucket *newTable = new Bucket[primes_[primeIdx_]];
			for (int i = 0;i<tableSize_;i++)
			{
				if (table_[i].state_==STATE_USING) //旧表中有效的数据重新哈希 
				{
					int idx = table_[i].key_ % primes_[primeIdx_];
					int k = idx;
					do
					{
						if (newTable[k].state_!=STATE_USING)
						{
							newTable[k].state_ = STATE_USING;
							newTable[k].key_ = table_[i].key_;
							break; 
						}
						k = (k+1) % primes_[primeIdx_];
					} while(k!=idx);
				}		
			}
			delete []table_;
			table_ = newTable;
			tableSize_ = primes_[primeIdx_];
		}
	
	private:
		Bucket *table_; //指向动态开辟的哈希表
		int tableSize_; //哈希表的长度
		int useBucketNum_; //已经使用的桶的数量
		double loadFactor_; //装载因子
		
		static const int PRIME_SIZE = 10;
		static int primes_[PRIME_SIZE];//素数表
		int primeIdx_; //当前素数的下标  
};

int HashTable::primes_[PRIME_SIZE] = {3,7,23,47,97,251,443,911,1471,42773};

int main()
{
	HashTable htable;
	htable.insert(21);
	htable.insert(32);
	htable.insert(14);
	htable.insert(15);
	htable.insert(27);

	cout<<htable.find(14)<<endl;
	htable.erase(14);
	cout<<htable.find(14);
}

哈希表的应用

查重

查重或者统计重复的次数，查询的效率高但是占用内存空间较大。
找第一个重复出现的数字
用unordered_set来查，先遍历数组，然后用find函数去查询是否哈希表里是否存在有这个数（find返回的是迭代器的值，如果没找到就返回哈希表的末尾）如果没有就会insert，有的话就会输出。切记，在map和set这里尽量都用auto，不要用下标访问。
找第一个和找所有的其实就是加不加break

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
	vector <int> a;
	srand(time(0));
	for (int i = 0;i < 10000;i++)
	{
		a.push_back(rand()%10000);
	}
	unordered_set <int> s;
	for (auto val : a)
	{
		auto it = s.find(val);
		if (it!=s.end())
		{
			cout<<*it;
			break;
		}
		else s.insert(val);
	}
}

找所有重复出现的元素以及重复的次数，用unordered_map，没找到，就把这个数字插入（用emplace方法），找到了，迭代器的second++（值++）；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
	vector <int> a;
	srand(time(0));
	for (int i = 0;i < 10000;i++)
	{
		a.push_back(rand()%10000);
	}
	unordered_map <int,int> m;
	for (auto p : a)
	{
		m[p]++;
	}
	for (auto q : m)
	{
		if (q.second>1)
		{
			cout<<q.first<<" "<<q.second<<endl;
		}
	}
}

Top K问题

top K问题：大小根堆来过滤，大根堆过滤前top k小的数据；小根堆过滤前top k大的数据
用大根堆来找前k个最小的元素；用小根堆来找前k个最大的元素。
64 45 52 80 66 68 0 2 18 75
这十个先把前三个数组成一个大根堆，然后到第四个80，80比堆顶元素64大，说明一定比这个堆里的所有元素都大，所以往下继续找，一直到0，0比堆顶元素小，我们就调整，依次这样。
最后复杂度为logk * O(n)但是logk是常数级，所以最终我们以O(n)复杂度的找到topK元素。

快排分割法。

二叉树

BST树（Binary Search Tree 二叉搜索树）

  • 对于二叉树上的每一个节点：左孩子的值<父节点的值<右孩子的值
  • 每一层的节点最多的个数2^(L-1)，第三层就是4个，第四层就是8个；
  • 所有节点的个数N与层数的关系：等比数列求和 = 2^L-1 = N，2^L = N+1，两边取对数L = log2N

BST的删除操作

  • 1.没有孩子的节点 父节点地址域为nullptr
  • 2.有一个孩子 孩子写入父节点地址域
  • 3.删除的节点有两个孩子 ：找待删除 节点的前驱节点或后继节点，用前驱/后继将要删除的节点值覆盖掉，然后直接删除前驱/后继就可以了。
    前驱：左子树里最大的 后继：右子树里最小的

二叉树的递归操作


左右根

基于后序遍历，使用递归操作来判断树的层数

int GetL(Node *node)
{
if (node!=nullptr)
{
PostOrder(node->left);
PostOrder(node->right);
return left > right ? left + 1: right + 1;
}
}

基于后序遍历递归操作求层数，可以用来求节点的个数

int num(Node *node)
{
if (node == nullptr) return 0;
int left = num(node->left);
int right = num(node->right);
return left + 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
#include <iostream>
using namespace std;

void func(int arr[], int i, int length)
{
	if (i == length)
	{
		for (int j = 0; j < length; j++)
		{
			cout << arr[j] << " ";
		}
		cout << endl;
	}
	else
	{
		func(arr, i + 1, length);
		func(arr, i + 1, length);
	}
}


int main()
{
	int arr[] = { 1,2,3 };
	int len = sizeof(arr) / sizeof(arr[0]);
	func(arr, 0, len);
	return 0;
}

子集树，其实就是递归选路径，需要一个辅助数组子集树

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
void func(int arr[], int i,int length, int x[])
{
	if (i == length)
	{
		for (int j = 0; j < length; j++)
		{
			if (x[j]==1) cout << arr[j] << " ";
			
		}
		cout << endl;
	}
	else
	{
		/*x[i] = 1; //选这条路
		func(arr, i + 1, length,x);
		x[i] = 0; //不选这条路
		func(arr, i + 1, length,x);*/
		for (int k = 1;k>=0;k--)
		{
			x[i] = k;
			func(arr,i+1,length,x);
		}

	}
}