数据结构与算法 PART 1
breayhing / SIRI Lv2
  2023-03-10 17:02:00 2023-03-10 17:02   2023-03-10 17:05:19    31.8k 字  140 分钟

数据结构与算法：PART1

算法时间分析：

https://www.acwing.com/blog/content/32/%E5%A5%BD%E4%B8%9C%E8%A5%BF

理解idx:

我感觉idx相当于一个分配器，如果需要加入新的结点就用++idx分配出一个下标（最主要可以做到不重复地重新分配下标）

AcWing 835. 如何理解单(双)链表，Trie树和堆中的idx？ - AcWing

所有数据结构 学习的同时一定要理解该种数据结构的使用范围，干什么的/

科班学习顺序：（如何逐步提高写程序的性能）

基础程序设计->数据结构与算法->操作系统->编译器的优化（编译原理）

提高程序性能办法：

好的算法：正确性，可读性，健壮性，效率

程序运行时间因素
  1. 所用算法
  2. 问题的规模
  3. 书写程序所用语言->级别越高效率越低
  4. 编译程序所用的机器(mac比windows快)
  5. 机器执行所用的速度（涉及到硬件，比如老电脑和新电脑）

算法时间度量：为了完成某一问题机器所做的操作执行次数

统计方法：写代码前/写代码后

1
2
3
4
5
6
7
int i, sum=0, n=100;//执行1次
for(i=1;i<=n;i++)//执行n+1次
{
sum+=i;//执行n次
}
cout<<sum;//执行n次

冯诺依曼架构

I/O<->中央存储单元<->

CPU:解析指令

内存：存储指令和数据

程序大小相对不重要，执行操作与数据重要

空间复杂度：

通过计算算法所创建的空间大小。

基础算法

位运算
1
2
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

快排——》重要，面试常用型😍

快排本质就是使用分治思想，递归实现

最快onlogn，最慢oN2

步骤：

  1. 确定分界点
  2. 调整范围（最麻烦部分）
  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
void quick_sort(int q[], int l, int r)//记住开头不变，最后右边是j+1
{
    if (l >= r) return;//左右指针相遇时候返回

    int i = l - 1, j = r + 1, x = q[l + r >> 1];//这里x暂时设定为左右边界的中间值，原因在于后边是do while指令，因此提前ij各往外移动一个位置
     //第一步：分成子问题
    while (i < j)
    {//注意这个顺序一定不能错
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        //容易错的点：要在这里打一个if
        if (i < j) swap(q[i], q[j]);//swap函数自己补充，这里ij可以相等
    }//这样操作过一轮之后x左边都是比它小的，右边都是比它大的
    //第二步：递归处理子问题
    
    
    
    quick_sort(q, l, j), quick_sort(q, j + 1, r);//这里一定一定是j，i会出问题
    
    
    
    //这里两步的顺序一定一定记住，不然可能无限划分
    //接着对它左右两端进行同样一次的操作，递归到最后就是全部完成排序
    //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤
}

使用说明：

1
2
3
如原本为a[10]，数据为a[0]-a[9];
则排序为
    quick_sort(a, 0, 9);//注意这里很容易错误弄范围
快排合理性分析：AcWing 785. 快速排序算法的证明与边界分析 - AcWing

由于使用do-while循环,所以i和j一定会!!!自增!!!,使得循环会继续下去,但是如果采用while循环(i和j的初始化做出对应的变更),i和j在特殊情况下不自增的话,循环就会卡死

边界问题：

快排属于分治算法，最怕的就是 n分成0和n，或 n分成n和0,这会造成无限划分

1
2
3
while(q[i] < x) i++;
  while(q[j] > x) j--;
当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环
单向移动版本快排（实际使用快慢指针）
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
int partition(int arr[], int low, int high)
 {
	int pivot = arr[low]; // 待比较的基准元素
	int i = low;
	for (int j = low + 1; j <= high; j++) 
    { if (arr[j] < pivot) 
    	{ i++; 		//最终i停留的位置是要交换的位置
     		swap(arr[i], arr[j]);
		}
	} 
	swap(arr[i], arr[low]); 
	return i;
}
void quickSort(int arr[], int low, int high) {
    if (low < high) { 
    	int pi = partition(arr, low, high);
		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high);
		}
}

/*
这种排序实际上将数组分成了三个部分：比pivot小，pivot，比pivot大，因此分治部分只需要对于pi-1和pi+1进行操作就行
*/

运行逻辑：指针j运行快，i运行慢，j只会在遇到比基准元素大的时候跳过

正常流程：如果j指向的都是比pivot小的元素，ji同步运动，指针一直向右走

image

如果j右边是比pivot大的元素，即i右边紧挨着就是更大的元素，j跳过，i停留不移动

image

然后让i++，刚好就到了大的元素，进行交换

结束情况：j遍历完成，i最后右移一次，停止

image

接着就是分治了

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insertionSort(int arr[], int n) {

int i, key, j; 
    for (i = 1; i < n; i++) 
    {
		key = arr[i];
        j = i - 1;
// 如果大于key需要向后移动一位
		while (j >= 0 && arr[j] > key)
        {//直接插入是一直插入到对比结束
			arr[j + 1] = arr[j]; j = j - 1;
		} 
        arr[j + 1] = key;
}
}

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
int binarySearch(int a[], int item, int low, int high) 
{ 
    if (high <= low) { return (item > a[low]) ? (low + 1) : low;} 
 	int mid = (low + high) / 2; 
    if (item == a[mid]) { return mid + 1;}
    if (item > a[mid]) { return binarySearch(a, item, mid + 1, high);}
	return binarySearch(a, item, low, mid - 1);

}//二分搜索部分
//注意二分一定有解，但是答案不一定有解
void insertionSort(int a[], int n) 
{
    int i, loc, j, k, selected; 
    for (i = 1; i < n; ++i) 
    {
         j = i - 1;
		selected = a[i];
		// 寻找应该插入的位置
		loc = binarySearch(a, selected, 0, j);
        //这里直接找到，后面的while循环就不需要再考虑对比，直接上就行
		// 移动后面所有的数据
        while (j >= loc) 
        { 
            a[j + 1] = a[j];
         	j--;
        }
        a[j + 1] = selected;
	}

}

希尔排序

模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int shellSort(int arr[], int n) {
// 从大gap开始，逐步减少gap
for (int gap = n / 2; gap > 0; gap /= 2) 
	{ 
    	for (int i = gap; i < n; i += 1) 
		{
// i 是直接插入排序算法中待插入的元素int temp = arr[i];
// 向前查找，并同时移位
			int j;
			for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
			{ 
    			arr[j] = arr[j - gap];
			}
// 把i元素放入合适的位置
			arr[j] = temp;
		}
	} 
    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
26
27
28
29
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;//最后拆分成单元素的时候就返回
    int mid = l + r >> 1;//二分
    
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
//以上先疯狂二分，将整个数组全部拆分成最小部分，然后下面部分开始递归合并
    int k = 0, i = l, j = mid + 1;
   	分别作用：
        k用于tmp数组，因此从0开始
        i从最左，j从中间开始向右
    
    
    while (i <= mid && j <= r)//这里由于递归，每一个小数组都归并好了，归并最后的大数组
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//归并，结果合并到tmp，
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];//赋值剩下的i
    while (j <= r) tmp[k ++ ] = q[j ++ ];//赋值剩下的j

    for (i = l, k = 0; i <= r; i ++, k ++ ) q[i] = tmp[k];
    k代表临时数组的值
      
    
    //赋值回去，使得q同步变得有序，用于小数组递归回去用
    //憋想着省去这一步，不然小数组无法被弄成有序，最后归并会失败
}

使用举例：

几个注意点：

  • tmp一开始就声明（不然爆内存）
  • merge里面j=mid+1（这里弄错之后排序都不对劲）
  • merge函数中i与j的范围记得别被错
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
#include<iostream>
using namespace std;
const int N=1e5+10;
int array[N];
int tmp[N];
void merge(int l,int r)
{
    int mid=(l+r)/2;
    int k=0,i=l,j=mid+1;//j的赋值容易不对劲
    while(i<=mid&&j<=r)
    {
        if(array[i]<=array[j])tmp[k++]=array[i++];//这里判断的时候还是加‘=’
        else tmp[k++]=array[j++];
    }
    while(i<=mid){tmp[k++]=array[i++];}
    while(j<=r){tmp[k++]=array[j++];}
    for(i=l,j=0;i<=r;i++,j++)//这里的范围也容易搞混
    {//注意归并排序中所有都是<=
        array[i]=tmp[j];
    }
}
void mergesort(int l,int r)
{
    if(l>=r)return;
    int i=l-1;
    int j=r+1;
    int mid=(i+j)/2;//这里有一个特别狠的二分
    
    mergesort(l,mid);
    mergesort(mid+1,r);//这里需要+1
    merge(l,r);
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>array[i];
    }
    mergesort(0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<array[i]<<' ';
    }
    return 0;
}
有趣应用：逆序对

788. 逆序对的数量 - AcWing题库

timsort（优化后归并）

这个就看苏老师的ppt课件

(105条消息) Timsort——自适应、稳定、高效排序算法_码到sucess的博客-CSDN博客_timsort

核心：提取降序数组升级为升序

数组本质都是部分有序的,

image

因此第一步：将所有部分降序数组全部翻转（这里直接逆序就好）

这一步模板：

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
void reverse(int q[],int l,int r)
{
    for(int i=l,j=r;i<=j;i++,j--)swap(q[i],q[j]);
}
void array_reverse(int q[],int N)
{
    if(N==1&&N==0)return;
    int i=1,l=0,tmp=0,stage_judge;
    if(q[0]<=q[1])stage_judge=1;//升序标记
    else  stage_judge=0;
    while(i<N)
    {
        if(q[i]>q[i+1])
        {
            if(stage_judge==1)stage_judge=0;
            ++i;
        }
        else if(q[i]<=q[i+1])
        {
            if(stage_judge==0)
            {
                if(tmp!=l-1)++l;
                reverse(q,l,i);
                tmp=i;
                stage_judge=1;
            }
            ++i;//前进一个
            l=i;//l=前进一位之后的i
        }
    }
}
核心：栈处理归并

先将所有已知的升序排列的压入总栈，

这一步：

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
void stack_check(int N)//对栈进行检验,并且要的是归并两个连续短区间
{
    int stack_pos1,stack_pos2,stack_pos3;
    int stack_length1,stack_length2,stack_length3;//1最顶，3最底层
    pop(stack_pos1,stack_length1);
    pop(stack_pos2,stack_length2);
    pop(stack_pos3,stack_length3);
    if(stack_length2<stack_length1||stack_length3<stack_length1+stack_length2)//x>y或者x+y>z
    {
        if(stack_length1>stack_length3)
        {
                push(stack_pos1,stack_length1);
                merge(stack_pos3, stack_length3,stack_pos2, stack_length2 );//对yz进行归并

        }
            else
        {
                    push(stack_pos3,stack_length3);
                    merge(stack_pos2,stack_length2,stack_pos1,stack_length1);//对xy进行归并
        }
           // cout<<endl<<endl<<"idx: "<<stack_idx<<endl;
        for(int i=0;i<N;i++)
        {
            cout<<q[i]<<" ";
        }
        cout<<endl;
        if(stack_idx>=2)stack_check(N);//递归检测
    }
    else//按照原先顺序再压进去
    {
        push(stack_pos3,stack_length3);
        push(stack_pos2,stack_length2);
        push(stack_pos1,stack_length1);
        cout<<endl<<endl;
    }
    return;
}
核心：最小分区长度在排序之前预先计算

➢ 归并过程低效的主要原因是大分区和小分区合并

1
2
3
4
5
6
7
8
9
10
while(stack_idx>=1)//输出阶段,这里就是检测是否正确归并入栈，没有归并
   {
        pop(stack_pos1,stack_length1);
        pop(stack_pos2,stack_length2);
       if(stack_pos1>stack_pos2)merge(stack_pos2,stack_length2,stack_pos1,stack_length1);
       else merge(stack_pos1,stack_length1,stack_pos2,stack_length2);
       for(int i=0;i<N;i++)
       {
           cout<<q[i]<<" ";
       }
timsort模板（自己写的！）
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
#include<iostream>
using namespace  std;
const int M =10010;
int q[M];
int tmp[M];
int pos_stack[M];//存储下标
int length_stack[M];//存储长度
int stack_idx=-1;
void push(int pos,int length )
{
    pos_stack[++stack_idx]=pos;
    length_stack[stack_idx]=length;
}
void pop(int &tmp_pos,int &tmp_length)//给两个数赋值然后弄出去
{
    tmp_pos= pos_stack[stack_idx];
    tmp_length= length_stack[stack_idx];
    --stack_idx;
    return;
}
void reverse(int q[],int l,int r)
{
    for(int i=l,j=r;i<=j;i++,j--)swap(q[i],q[j]);
}
void array_reverse(int q[],int N)
{
    if(N==1&&N==0)return;
    int i=1,l=0,tmp=0,tem_l=0,stage_judge;
    if(q[0]<=q[1])stage_judge=1;//升序标记
    else  stage_judge=0;
    while(i<N)
    {
        if(q[i]>q[i+1])
        {
            if(stage_judge==1)
            {
                stage_judge=0;//之前是升序这里突然降序了
            }
            ++i;
        }
        else if(q[i]<=q[i+1])
        {
            if(stage_judge==0)
            {
                if(tmp!=l-1)++l;
                reverse(q,l,i);
                tmp=i;
                stage_judge=1;
            }
            ++i;//前进一个
            l=i;//l=前进一位之后的i
        }
    }
}
void merge(int pos1,int length1,int pos2,int length2)
{
    int r=pos2+length2-1;//最右端
    int l=pos1;//最左端
    //归并部分
    int mid=pos1+length1-1;
    int k = 0, i = l, j = pos2 ;
    while (i <= mid && j <= r)//这里由于递归，每一个小数组都归并好了，归并最后的大数组
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//归并，结果合并到tmp，
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];//赋值剩下的i
    while (j <= r) tmp[k ++ ] = q[j ++ ];//赋值剩下的j
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    push(pos1,length1+length2);//合并完之后进行压栈
}
void stack_check(int N)//对栈进行检验,并且要的是归并两个连续短区间
{
    int stack_pos1,stack_pos2,stack_pos3;
    int stack_length1,stack_length2,stack_length3;//1最顶，3最底层
    pop(stack_pos1,stack_length1);
    pop(stack_pos2,stack_length2);
    pop(stack_pos3,stack_length3);
    if(stack_length2<stack_length1||stack_length3<stack_length1+stack_length2)//x>y或者x+y>z
    {
        if(stack_length1>stack_length3)
        {
                push(stack_pos1,stack_length1);
                merge(stack_pos3, stack_length3,stack_pos2, stack_length2 );//对yz进行归并

        }
            else
        {
                    push(stack_pos3,stack_length3);
                    merge(stack_pos2,stack_length2,stack_pos1,stack_length1);//对xy进行归并
        }
           // cout<<endl<<endl<<"idx: "<<stack_idx<<endl;
        for(int i=0;i<N;i++)
        {
            cout<<q[i]<<" ";
        }
        cout<<endl;
        if(stack_idx>=2)stack_check(N);//递归检测
    }
    else//按照原先顺序再压进去
    {
        push(stack_pos3,stack_length3);
        push(stack_pos2,stack_length2);
        push(stack_pos1,stack_length1);
        cout<<endl<<endl;
    }
    return;
}
//归并搞定
int main() {
    int N;
    cin >> N;
    int stack_pos1,stack_pos2,stack_pos3;
    int stack_length1,stack_length2,stack_length3;
    for (int i = 0; i < N; i++) {
        cin >> q[i];
    }
    array_reverse(q, N - 1);//没问题了,别动！
    int l=0;
    for(int i = 0; i < N; i++) {
        if(q[i]>q[i+1])
        {
            push(l,i-l+1);

            l=i+1;
        }
    }//这里完成将栈压入
    //接下来就是找最大的，然后合并
    cout<<endl<<endl;
    for(int i=0;i<N;i++)
    {
        cout<<q[i]<<" ";
    }
    cout<<endl;
    if(stack_idx>=2)stack_check(N);
    while(stack_idx>=1)//输出阶段,这里就是检测是否正确归并入栈，没有归并
   {
        pop(stack_pos1,stack_length1);
        pop(stack_pos2,stack_length2);
       if(stack_pos1>stack_pos2)merge(stack_pos2,stack_length2,stack_pos1,stack_length1);
       else merge(stack_pos1,stack_length1,stack_pos2,stack_length2);
       for(int i=0;i<N;i++)
       {
           cout<<q[i]<<" ";
       }
   }
    return 0;
}//23         2 4 7 8 23 19 16 14 13 12 10 20 18 17 15 11 0 5 6 1 3 21 22

二分

二分本质并不是单调性：有单调性一定可以二分解，可以二分解的题目不一定满足单调性，本质：可以将原本区间分成两个部分

二分一定有解（自己的二分的性质是一定有边界的），但题目可能会无解（看例题）

整数二分比实数二分蛋疼很多：整数有边界问题很恶心

当出现最小值最大（最右端）或最大值最小（最左端）或求最大值、最小值时，就可以考虑一下二分了

整数模板（两种）

应用：

1：找大于等于数的第一个位置 （满足某个条件的第一个数）
2：找小于等于数的最后一个数 （满足某个条件的最后一个数）
3.查找最大值 （满足该边界的右边界）、
4.查找最小值 (满足该边界的左边界)

然后每次使用这这两个模板的时候，先想是找这个区间的左端点还是还是右端点，然后选择用模板，最后再去写判断条件。

设置红绿交界点是要求的位置

image

  1. 最后收敛到整个数组中满足条件的最右边的点
  2. 最后收敛到数组中满足条件的最左边的点

image

记忆方式：有减必有加

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
bool check(int x) {/* ... */} // 检查x是否满足某种性质

//核心在于判断l=mid还是r=mid

//收敛到最右边的点
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：情况1
int SR(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;//需要补上l+r+1，防止死循环
        if (check(mid)) l = mid;
        else r = mid - 1;//有减，前面必定有加
    }
    return l;
}


//收敛到最左边的点
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：情况2
int SL(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;//这里是（l+2）/2
        if (check(mid)) r = mid;    // check()判断mid是否满足性质：
        else l = mid + 1;
    }
    //
    return l;//这里最终l和r相等，不需要考虑别的
}

整数经典例题：789. 数的范围 - AcWing题库

经典：二分模板最终一定有解，题目不一定有解（最后的判断不满足题目）

解答：

image

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
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];

int SL(int l, int r, int x) {//最终结果是最左边满足条件的
  while (l < r) {
    int mid = l + r >> 1;
    if (q[mid] >= x) r = mid;
    else l = mid + 1 ;
  }
  return l;
}

int SR (int l, int r, int x) {
  while (l < r) {
    int mid = l + r + 1 >> 1;//有+
    if(q[mid] <= x) l = mid;
    else r = mid - 1;//有-
  }
  return r;
}

int main() { int n,m;
    scanf ("%d%d",&n,&m);
    for(int i=0;i<n;++i) scanf ("%d",&q[i]);
    while ( m-- ) {
        int x;
        scanf ("%d",&x);
        int l = SL(0, n - 1, x);//查找左边界 并返回下标l
        //这里最后的L就是最左边第一个满足>x的数字，也就是满足二分得到的结果（最接近x且>=x）
        //因此下一步可以直接判断是否直接=x
        if (q[l]!=x) cout <<"-1 -1"<<endl;//如果找不到  返回-1 -1
        else {
            cout << l << ' '; //如果找到了  输出左下标
            cout << SR(0, n - 1, x) << endl; //输出右下标
        }
    }
    return 0;
}

同样的例题：（爷跟你拼了）

519. 跳石头 - AcWing题库

照样使用二分（虽然是比较复杂的二分）：二分,贪心O(NlogL)

思路：使得选手们在比赛过程中的最短跳跃距离尽可能长，当出现最小值最大（最右端）或最大值最小（最左端）或求最大值、最小值时，就可以考虑一下二分了。验证答案具有单调性：拿走的石头越多，最短跳跃距离越大，这就叫答案的单调性

核心原理：

  • 二分答案
    二分答案就是把一组数据每次分成两部分，就是把大问题转化成小问题。例如猜数游戏，猜1-100的一个数，就先猜50，若小了，就猜75，若大了，就猜25，就这样一直猜下去，最终找到答案。而我们每一次猜的这个答案就是所求范围内的数据的中间数据，这就是二分答案。这个二分的中间数据就是指要求的内容。
  • 如果长度 LenLen 可以满足，那么当长度小于 LenLen 时也可以满足，所以我们可以二分出最大的 LenLen。也就是在所有可满足的Len中寻找最右端的答案（这里指从0到最大），因此使用模板SR（再看上一道题实际上一个原理）
  • 剩下的问题是如何判断给定 LenLen 的情况下，能否最多拿走 M块石头，使得所有相邻两块石头之间的距离不小于 LenLen。这一步可以贪心来做。从前往后扫描，并记一下上一块石头的位置。
  • 如果当前石头和上一块石头的距离小于 LenLen，则将当前石头拿走
  • 如果当前石头和上一块石头的距离大于等于 LenLen，则将上一块石头更新成当前这块。（和上一条是贪心时候的两种解法）
  • 这里给出贪心证明：如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头，这样总共拿走的石头数量不变，所以当前选法也是一组最优解。
  • check函数：我们遍历一遍每一块石头，累计出有多少块石头之间的间隔<=mid,如果超过m个，就不合法，如果小于等于m，就合法。(累计间隔小也就是需要搬走多少个石头)
  • 扫描结束后判断拿走的石头数量是否小于等于 M。（判断这个答案能不能执行，能说明答案mid还能猜测更大，更新l，不能说明mid猜测过大了，更新r）

时间复杂度分析
总共二分 O(logL)O(logL) 次，每次贪心的计算是 O(N)O(N)，因此总时间复杂度是 O(NlogL)O(NlogL)。

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50005;
int a[N];
int n,m,s;

bool check(int x) //check函数判断这个最短跳跃距离x是否合法
{
    int cnt=0,last=0; //last表示的是上一块石头的位置,cnt用来计数
    for(int i=1;i<=n;i++)   //枚举每一块石头 
    {
        //不移动走石头，就实时更新上一块石头位置，如果移动，就不更新
        if(a[i]-last<x) cnt++;//如果这一块石头和上一块石头的距离比x小,计数+1。而且如果石头移走，last还是上一块石头的位置。
        else last=a[i]; //否则这块石头就不必移走，last=这块石头的位置。
    }
    if(cnt>m) return false; //cnt如果超过m个，就不合法。
    else return true;
}

int main()
{
    cin>>s>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[n+1]=s;//将终点的距离也算进去

    n=n+1;//注意这里的n需要加一，check函数需要用

    int l=1,r=s; //注意l和r都是最短跳跃距离的边界，而不是石头的边界。 
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;//答案猜小了
        else r=mid-1;//答案猜大了
    }
    cout<<l<<endl;
}

https://www.acwing.com/blog/content/21312/

https://www.acwing.com/solution/content/118815/

https://leetcode.cn/leetbook/read/illustration-of-algorithm/59bjss/

https://www.acwing.com/solution/content/120802/

浮点模板

浮点好处在于不用考虑整数二分中的边界问题，因此直接用

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;//这里就不用多考虑
    }
    return l;
}

例题：790. 数的三次方根 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include<cstdio>
using namespace std;
double x;
int main () {
    cin >> x;
    double l = -1000,r = 1000;//这里一开始范围设定大，直接从0开始
    while (r - l >= 1e-7) {
        double mid = (l + r) / 2;
        if (mid * mid * mid <= x) l = mid;  //如果是小于等于的话，就可以说明答案会更大
        //比较重要的一步，c++里面几次方就直接弄，别用mid^3,配合c++primer食用
        else r = mid;
    }
    printf ("%.6lf",l);
    return 0;
}
二分改进：
插值查找

应用范围：表长较大，关键字分布均匀

关键不同：

二分mid固定为0.5，插值查找mid参数动态变化

1
mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;
斐波那契查找

(104条消息) 七大查找之斐波那契查找_非常规自我实现的博客-CSDN博客_fibonacci查找

前缀和（应用广泛）

数据结构应用：字符串哈希表kmp，自动机kmp，

前缀和+哈希表=LZW压缩->文本压缩
压缩部分：
解压缩部分：

离散化：整数离散化

如果使用哈希，会有额外的空间开销

特点：值域范围大，但是个数少（比如要访问到数组的10^9的位置，但个数只有10^5）也就是对于一个函数a->b，实际上只需要映射a，不需要操作b（当然高级玩家也可以继续弄b）。一般有两个问题：

  1. a数组里面可能有重复元素，因此需要去重，（去重是最重要的）
  2. 如何算出a[i]离散化后的值，保序离散化（a数组本身下标有序的），映射后一定也要是有序的，a[i].由于a有序，可以使用二分

需要使用的知识点：

  • vector
  • pair
离散化模板：(c++版本)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//alls存储的是最开始的下标
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
    //前缀和从1开始相对方便
}

AcWing 802. 区间和 - AcWing

分析：

使用离散化原因：

  1. 存储下标过大，不能开这么大的下标
  2. 使用数轴，会存在负值，不能使用下标
  3. 哈希表不能像离散化缩小数组的空间，可能导致遍历-e9~1e9。此处的含义就是假如我们需要计算1e-9和1e9区间内的值，那我们需要从前到后枚举，无论该值是否存在。因为哈希表不能排序，因此不能提前知道哪些数周上的点不存在，会枚举多次（如最后query的时候，从1到1e9，使用哈希表就要遍历才知道是否有点，时间开销太大），

离散化本质：映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量，也就是如何能够将不连续的点映射到连续的数组的下标。

本题解法：(离散化) O((n+2∗m)log(n+2∗m))

  1. 开辟额外数组存放原来 的下标标志
  2. 对原来的数轴下标进行排序再去重，原因：考虑前缀和思想，我们需要求出的区间内的和的两端断点不一定有元素，提前加如需要求前缀和的两个端点，有利于我们进行二分搜索，其实二分搜索里面我们一般假定有解的，如果没解的话需要特判，所以提前加入了这些元素，从而导致可能出现重复元素
  3. 最多使用n+2m次操作，最多使用的下标跨度为3*10^5,

首先用而二分写好映射后对应的数组下标，复杂度log(n + 2 * m)

1
2
3
4
5
6
7
8
9
10
11
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

全解：

关于unique和erease可以看

[(100条消息) C++ 之vector元素去重unique()_sandalphon4869的博客-CSDN博客_unique vector](https://blog.csdn.net/sandalphon4869/article/details/98209093?ops_request_misc=%7B%22request%5Fid%22%3A%22166674706816800184111752%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=166674706816800184111752&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-98209093-null-null.142^v59^pc_rank_34_1,201^v3^control_1,213^v1^t3_control1&utm_term=vector unique&spm=1018.2226.3001.4187)

auto:(100条消息) c++ auto基本用法_lwgkzl的博客-CSDN博客_auto用法

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

typedef pair<int, int> PII;//pair可以同时存储两个数据，可以理解成半封装的结构体
const int N = 300010;//最多涉及的下标长度
int a[N], s[N];
int n, m;

vector<int> alls;//存储下标值
vector<PII> add, query;//分别存储询问和加

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;//为了最终的映射从1开始
}
vector<int>:: iterator unique(vector<int> &a)
{//这里是手动实现unique，非c++语言需要手动
    //作用为自动去重
    int j = 0;
    for(int i = 0; i < a.size(); i ++)
        if(!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];
    return a.begin() + j;
}

int main()
{

    cin >> n >> m;

    for(int i = 0; i < n; i ++ )
    {
        int x, c;//x是下标
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }

    for(int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
        //全部存储后alls组成为x,x,x,x,x,l1,r1,l2,r2等等
    }

//直接unique(a)不加其它参数就是默认直接从头到尾，
    sort(alls.begin(), alls.end());//对原来的数组下标进行从小到大
    vector<int>::iterator pos = unique(alls);
     //pos是去重以后vector中没有重复元素的下一个位置的迭代器
    //从容器的开始到返回的迭代器位置的元素是不重复的元素，而从返回的迭代器位置到vector.end()的元素都是没有意义的（这东西就是原来排序后的东西，没变过）。
    //比如1 2 3 3 4 4 5 5unique后为1 2 3 4 5   5 5 5（别管这三个什么，没意义）

    alls.erase(pos, alls.end());//删除重复元素

    for(auto item : add)//add是一个vector<PII> add，为方便初始化这么用
    {
        int x = find(item.first);//第一个值是要加的数的下标
        a[x] += item.second;//对应的数组位置加该数
    }

    for(int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
    //这里用前缀和方法求所有的前缀

    for(auto item : query)
    {
        int l = find(item.first), 
        r = find(item.second);//两个都是
        cout << s[r] - s[l - 1] << endl;
        //这里最后就是对应过来的减去后的值，
    }

    return 0;
}
//这些数据是验算用的
3 3//m。n
1 2
3 6
7 5
1 3
4 6
7 8

补充auto：

1
2
3
4
5
6
7
8
9
10
11
int main(){
    vector<int>v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    for(auto i : v){//这一步就是迭代器从begin走到end
        cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

区间合并：不同于离散化

应用：很多区间，如果有交集就合并成一个更长的区间

区间合并算法：快速地进行多个区间的合并,当然可以进行一些特殊处理，比如对于端点就进行统一归并

步骤：
  1. 按区间左端点进行排序
  2. 扫描过程中，对于所有有交集的区间进行合并。

左边端点设置成start，右边设置成end，可能有的关系：

image
  1. 左右都在内部：原本区间不变
  2. 仅一部分在内部：新的ed会边长（左端点不会更新，因为是按照左端点从小到大的顺序进行区间的扫描的）
  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
#include<algorithm>


void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());//这里是因为pair是默认按照左端点排序的

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)//情况3：两个区间无法合并
        {
            if (st != -2e9) res.push_back({st, ed});//区间1放进去res数组
            st = seg.first, ed = seg.second;//维护区间2
        }
        else ed = max(ed, seg.second);//情况12，可以合并，进行更新

     //考虑循环结束时的st,ed变量，此时的st,ed变量不需要继续维护，只需要放进res数组即可。
    //因为这是最后的一个序列，所以不可能继续进行合并。
    if (st != -2e9) res.push_back({st, ed});//说的就是你，最后一个序列，if就是防一下空序列

    segs = res;//这样回复的就是答案segs
}

//最大原因：排过序了，不用担心复用
//排过序之后，不可能有区间2包含区间1，只能是1包含后面的
//本质，遍历，每一次如果两个区间没有相交的部分（无法合并），那么就将一个区间推入作为答案，同时更新左右端点

y总：

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
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;
vector<PII> segs;

void merge(vector<PII>&segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());//先对于全部区间进行排序
    int l = -2e9,r = -2e9;//小就完事了
    for(auto item:segs)//定义了一个迭代器，这里是一个遍历的过程
    {//! 第一段区间一定是  ed< item.first
        if(r < item.first)//当前区间右端点严格小于枚举区间的左边
        {//情况1：两个区间无法合并
            if(l != -2e9) res.push_back({l,r});//! 第一次在这里初始化
            //区间1放进去res数组
            l = item.first;//! 第一段区间从这里开始即seg[0].first
            //维护区间2
            r = item.second;//第一段区间的。seg[0].second
        }//todo 这个循环结束之后还会剩下一个区间
        else r = max(r,item.second);//第二种情况，说明有交集，右端点更新成维护的区间的右端点以及最大值
    }//! 如果不是空的  那我们就加上一段
    if(l != -2e9) res.push_back({l,r});//最后一个区间判断一下，防止空区间
    segs = res;//区间更新变成res
}
int main()
{
    int n;
    cin >> n;

    while(n--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        segs.push_back({l,r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

数据结构

链表

有限性：数据元素个数有穷

相同性：数据元素的类型是同一的

顺序性：相邻的数据元素之间存在序偶关系

前言：

  • 链表当中利用结构体制造链表的速度都是非常慢的，会消耗很多的时间，而正常面试中需要使用到链表时候大小都是有限制的，一般是十万或者百万的级别，而单单是new这些节点就会导致超时，在笔试题中最好不要用结构体指针，可以优化比如提前构建好多个节点，但已经类似于数组模拟链表了.算法题中绝对绝对不要考虑内存泄漏的问题

  • 使用结构体去构建链表的另一个问题在于键入指令会很麻烦

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //数组版本
    int next[N],prev[N],valu[N]
    void delete(int k)
    {
        next[prev[k]]=next[k];//向右跳过中间
        prev[next[k]]=prev[k];//向左跳过中间
    }
    //结构体版本
    struct Node
    {
    	int valu,next,prev;
    }nodes[N];
    void delete(int k)
    {
        nodes[nodes[k].prev].next=nodes[k].next;
        nodes[nodes[k].next].prev=nodes[k].prev;
    }
    //两种类型相比第二种整体结构易于理解但是在使用过程中语句特别长而且不太容易理解

ps:算法题中大部分操作都是头插法

链表制造方式
  1. 结构体+指针（c++需要使用new，费时间）
  2. 数组模拟（这里是静态数组，用空间换时间）

小tips：邻接表本质就是n个单链表拼起来，正常一个head对应一条链表，这个就是开了一个组，head[i]对应第i条链表

数组模拟链表

  1. 单链表：邻接表（实际上n个链表），主要应用在于存储图和树
  2. 双链表：优化某些问题
单链表制作

826. 单链表 - AcWing题库

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
//通用版本的静态链表  
//e[n]:某个点的值，ne[n]:某个点的指针，使用下标关联起来
const int n =1000010;

//e[i]节点i
//ne[i]节点i的next指针指向的值
//idx存储已经用过哪一个点
int head,e[n],ne[n],idx;
/*
这个的灵魂在于idx,有了idx可以保证无论新插的节点是头插还是尾插都没区别，都会用来计数，然后在对第k个进行操作的时候直接就定位到了idx
*/
void initial()
{
    head=-1;//让head指向一个空的位置
    idx=0//idx数量实际上就是链表当中总共节点的数量
}
void add_to_tail(int x)//尾插
{
    e[idx]=x;
    if(head==-1//当是第一次插入时特殊处理
    {
        ne[idx]=head;
        head=idx;
        idx++;
        return;
    }
    int i=head;
    if(head!=-1)while(ne[i]!=-1)i=ne[i];//最后ne[i]=-1
    ne[idx]=-1;
    ne[i]=idx;
    idx++;
}
void add_to_head(int x)//头插
{
    e[idx]=x;//保存x的值到一个新的位置
    ne[idx]=head;//更新指向，新元素指向原先head的位置，也就是-1（第一次跑）
    head=idx;//head头节点更新位置，更新到新元素的下标
    idx++;//下一个新的元素
}
void add(int k,int x)//注意和头插的区别在于位置变换的是ne[k]
{
    k=k-1；//千万注意注意这里要改一下
        //否则会出范围的
        
        
    e[idx]=x;//先保存
    ne[idx]=ne[k];//指向原先k的位置
    ne[k]=idx;
    idx++;//说明加
}
void delete(int k)//tm惊为天人的简洁版本
{//这里是删除第k个添加的，并不是按照值来删除
    k=k-1；//千万注意注意这里要改一下
        //同样会出范围
        
        
    ne[k]=ne[ne[k]];//我tm直接更新ne[k]指向的位置，中间数直接损失指引
}
void dele(int a)//这个是删除某一个特定值
       {//一个问题是如果只有一个元素需要特判
           if(e[head]==a)head=ne[head];//直接清空就行
           else for(int i=head;ne[i]!=-1;i=ne[i])//多个元素时候的删除操作
           {
               if(e[ne[i]]==a)//这里关系是跳过中间
               {
                   ne[i]=ne[ne[i]];
               }
          }
       }
void print()
{
    for(int i=head;i!=-1;i=ne[i])//灵魂在于这里每一次索引更新：i=ne[i]（因为静态数组里面下标所在位置不固定了）
    {
        cout<<e[i]<<' ';
        cout<<endl;
    }
}

双链表制作
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
#include<iostream<
using namespace std;
const int M=20010;
int r[M],prev[M],e[M],index;
void initial()
{
   //双链表相对单链表的初始化不同
   r[0]=1;//最左端指向最右端
   l[1]=0;//最右端指向最左端
   index=2;//另一个好处就是非常直白，双数肯定是向右的，单数向左的
}
void add_to_right(int x,int k)//第k个的右边插入
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    //新节点的延申部位都搞定了，开始双向连接
    l[r[k]]=idx;
    r[k]=idx//
    idx++;
}
//向右插就是
  add_to_right( x, k+1)//k+1因为index从2开始计数
//聪明的方法，在左边插入直接调用add_to_right(x,l[k]),也就是在k的左边节点调用向右插，结果就是第k个节点左边插入
add_to_right( x, l[k+1])//同理
//如果是最左端或者最右端更简单
//最左端
 add_to_right( x, 0)
 //右端
add_to_right( x, l[1])      
void dele(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
void print()
{
    for(int i=r[0];i!=1;i=r[i])//灵魂在于这里每一次索引更新：i=ne[i]（因为静态数组里面下标所在位置不固定了）
    {
        cout<<e[i]<<' ';
        cout<<endl;
    }
}


//使用的时候的api：
	add_to_right( x, k+1)
    add_to_left(x,k+1)
	dele(k+1)
     第k个插入的数左边插入：add_to_right(x,l[k+1])
     第k个插入的数右边插入：add_to_right(x,k+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
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
//双向链表制作
#include<stdlib.h>
#include<stdio.h>
struct Node{
	char data;
	struct Node* next;
	struct Node* pre; 
};
struct Node*p;
struct Node*head;
struct Node*tail;
void Home()
{
	p=head;
}

void End()
{
	p=tail->pre;
}

void Left()
{
	if(p==head) return;
    p=p->pre;
}

void Right()
{
	if(p->next==tail) return;
	p=tail->pre;
}

void Back()
{   
	if(p==head) return;
	struct Node*tmp=(struct Node*)malloc(sizeof(struct Node));
	tmp=p;
	tmp->pre->next=tmp->next;
	tmp->next->pre=tmp->pre;
	free(tmp);
}
	

int main(){
	char s[50010];
	int i;
	struct Node*head=(struct Node*)malloc(sizeof(struct Node));
	struct Node*tail=(struct Node*)malloc(sizeof(struct Node));
	struct Node*p=head;
	head->next=tail;
	tail->pre=head;
	tail->next=NULL;
	head->pre=NULL; 
	
	
	scanf("%s",s);
	
	
	for(i=0;s[i]!='\0';i++)
	{
			
		if(s[i]=='{') Home();
		else if(s[i]=='}') End();
		else if(s[i]=='<') Left();
		else if(s[i]=='>') Right();
		else if(s[i]=='#') Back();
		else
			{
			struct Node*q=(struct Node*)malloc(sizeof(struct Node));
			q->data=s[i];
			q->pre=p;
			q->next=p->next;
			p->next->pre=q;
			p->next=q;
			p=p->next;
			}	
			
	}
	
	
	for(p=head->next;p!=tail;p=p->next)
	{
		printf("%c",p->data);
	}	

}
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
#include<iostream>
#include<string>
using namespace std;
const int M=100090;
int nex[M];
int pre[M];
int valu[M];
int idx;
void initial(void)
{
   //双链表相对单链表的初始化不同
   nex[0]=1;//最左端指向最右端
   pre[1]=0;//最右端指向最左端
   idx=2;//另一个好处就是非常直白，双数肯定是向右的，单数向左的
}
void add_to_right(int x,int k)
{
    valu[idx]=x;
    nex[idx]=nex[k];
    pre[idx]=k;
    //新节点的延申部位都搞定了，开始双向连接
    pre[nex[k]]=idx;
    nex[k]=idx;//
    idx++;
}
//更聪明的方法，在左边插入直接调用add_to_right(x,prev[k]),也就是在k的左边节点调用向右插

void dele(int k)
{
    nex[pre[k]]=nex[k];
    pre[nex[k]]=pre[k];
}
int main()
{
    int tem;
    int index;
    int n;
    cin>>n;
    initial();
    for(int i=0;i<n;i++)
    {
        string a;
        cin>>a;
        if(a=="D")
        {
            cin>>index;
            dele(index+1);
        }
        if(a=="L")
        {
            cin>>tem;
            add_to_right(tem,0);
        }
        if(a=="R")
        {
            cin>>tem;
            add_to_right(tem,pre[1]);
        }
        if(a=="IL" )
        {
            cin>>index>>tem;
            add_to_right(tem,pre[index+1]);
        }
        if(a=="IR" )
        {
            cin>>index>>tem;
            add_to_right(tem,index+1);
        }
    }
    for(int i=nex[0];i!=1;i=nex[i])
    {
        cout<<valu[i] <<" ";
    }
    return 0;
}


链表递归与双指针

应用：力扣19题

方法：未知链表长度情况下通过递归获取长度

注意这种递归本质上是逆序进行扫描，从null扫描到head（不是空节点头，而是存放第一个值的头）

读取顺序讲解：

以1234，2示例如有a,b,c,d四个节点，分别存放1，2，3，4（a是头4是尾，4->next=NULL）

那么调用函数length时候会先一直向下扫描（因为未满足条件之前不会进行return），扫描到d的下一个节点null这时返回1->到达节点d，（因为有pos=length(node->next,n)+1,+1导致从节点null返回d时候pos变成1）返回2（到达节点c），返回3（到达节点b），注意这时候满足倒序扫描到第三个了，也就是要删除的节点再向上回溯了1位,因此删除节点c,即node->next=node->next->next**(b指向c变成b指向d)**

好处：时间少（只用扫描一次），空间少（没有额外开辟指针）

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public://尝试递归解决

    int length(ListNode *node,int n)//这一段千万千万注意是倒序，倒叙进行读取！！！
    {
        if(node==NULL)return 0;//递归停止
        int pos=length(node->next,n)+1;
        if(pos==n+1)//进行判断了，说明在第几层递归
            node->next=node->next->next;
        return pos;//递归层层回溯
    }
    
    
    
    
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int pos =length(head,n);
        if(pos==n)return head->next;//链表总长度刚好等于倒退长度，即处理头节点情况
        return head;//
    }
};

参考网址：【反转链表】：双指针，递归，妖魔化的双指针 - 反转链表 - 力扣（LeetCode）

同样利用递归实现链表逆序：（有那么一点点费脑子）
image

原理：链表自身带有递归属性（一个大问题可以拆解成小问题）

将链表拆分成头节点和剩余节点，同理继续拆解，一直拆解到最后的尾节点和前面的一堆“头”节点,最后一个节点不需要进行翻转

image

image

这里就是对于子问题，将子链表进行翻转，就可以得到整个链表的反转，也就是递归的第一步

1
2
3
4
5
public ListNode reverseList(ListNode head) {
    // 调用递推公式反转当前结点之后的所有节点
    // 返回的结果是反转后的链表的头结点
    ListNode newHead = reverseList(head.next);
}

这里假设后续子链表已经全部完成翻转，那么只需要对“头节点”完成翻转

image

image

也就是

1
2
head->next->neat=head;
head->next=NULL;

完善之后就是有

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
    // 调用递推公式反转当前结点之后的所有节点
    // 返回的结果是反转后的链表的头结点
    ListNode newHead = reverseList(head.next);
    //到这里已经是假设后面的链表部分已经全部反转完成，也就是只需要处理头节点和剩余部分的关系
    head.next.next = head;
    head.next = null;
    return newHead;//注意哦，这里返回的是newhead，因为newhead是反转之后的链表的头节点，即最尾部的节点
}

再加上约束条件（递归终止条件）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
if (head == NULL || head->next == NULL) {//返回条件/结束递归条件
            return head;
        }
   */

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {//返回条件/结束递归条件
            return head;
        }
        ListNode* ret = reverseList(head->next);//这里递归，ret会在走到链表末端开始翻转
        head->next->next = head;
        head->next = NULL;
        return ret;//
    }
};
/*执行起来大概是这么一个既视感

双指针实现逆序

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {//终止条件，最后的指针pre走到末尾停止
            ListNode* temp = pre->next;
            pre->next = cur;//开始反置指针指向
            //cur和pre整体向前移动一个位置
            cur = pre;
            pre = temp;
        }
        return cur;
    }
};

原理：一开始创建两个指针pre和cur，pre指向head，cur指向null，tem有点类似指针交换数值中的tem，指向正常链表顺序的下一个节点（这里就是head->next），

有序链表的拼接（又是递归/bushi）

时间复杂度：O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {//终止条件：l1走到末尾了
            return l2;
        }
        if (l2 == NULL) {//终止条件：l2走到末尾了
            return l1;//剩下的都弄上去就是
        }
        
        //分割线
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);//对l1的剩余部分进行一个递归操作
            //重点部分mergeTwoLists(l1->next, l2)，对l1后面的元素处理
        
            return l1;//因为L1的这个元素小，因此把它拎出来
        }
        l2->next = mergeTwoLists(l1, l2->next);//对l2的剩余部分进行递归操作，l2->next同理
      
        return l2;//同理
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
解释的一个部分

关于return L1的个人理解: 递归的核心在于,我只关注我这一层要干什么,返回什么,至于我的下一层(规模减1),我不管,我就是甩手掌柜.

好,现在我要merge L1,L2.我要怎么做?

- 显然,如果L1空或L2空,我直接返回L2或L1就行,这很好理解.//上方的两个NULL情况
- //如果L1第一个元素小于L2的? 那我得把L1的这个元素放到最前面,至于后面的那串长啥样 ,我不管. 我只要接过下级员工干完活后给我的包裹, 然后把我干的活附上去(令L1->next = 这个包裹)就行
- 这个包裹是下级员工干的活,即merge(L1->next, L2)

我该返回啥?

- 现在不管我的下一层干了什么,又返回了什么给我, 我只要知道,假设我的工具人们都完成了任务, 那我的任务也就完成了,可以返回最终结果了
- 最终结果就是我一开始接手的L1头结点+下级员工给我的大包裹,要一并交上去, 这样我的boss才能根据我给它的L1头节点往下找,检查我完成的工作
回文链表判断：（映射，递归，翻转）

映射到数组上再对数组进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);//使用迭代器更加节省时间一些，如果是数组会报错
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};

优雅递归

遍历节点的方式可是我看不懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    ListNode* frontPointer;//这个是前指针
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) {
                return false;
            }
            if (currentNode->val != frontPointer->val) {
                return false;
            }
            frontPointer = frontPointer->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

解释：currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。

复杂度分析

时间复杂度：O(n)O(n)，其中 nn 指的是链表的大小。
空间复杂度：O(n)O(n)，其中 nn 指的是链表的大小。我们要理解计算机如何运行递归函数，在一个函数中调用一个函数时，计算机需要在进入被调用函数之前跟踪它在当前函数中的位置（以及任何局部变量的值），通过运行时存放在堆栈中来实现（堆栈帧）。在堆栈中存放好了数据后就可以进入被调用的函数。在完成被调用函数之后，他会弹出堆栈顶部元素，以恢复在进行函数调用之前所在的函数。在进行回文检查之前，递归函数将在堆栈中创建 nn 个堆栈帧，计算机会逐个弹出进行处理。所以在使用递归时空间复杂度要考虑堆栈的使用情况。
这种方法不仅使用了 O(n)O(n) 的空间，且比第一种方法更差，因为在许多语言中，堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 1000（可以增加，但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小。

快慢指针

很优雅**但是我照样看不懂***没想到吧老子看懂了哈哈哈哈哈哈哈

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
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);//返回慢的那一半
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);//对中间开始往右的第一个开始翻转

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);//为了保证链表本身不变，实际上可以省略（大概）
        return result;
    }

    ListNode* reverseList(ListNode* head) {//是你最爱的双指针翻转法
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {//快慢指针，快的走俩，慢的走1，在中点停止
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

zhan（栈）不是B站那个

前言：

栈属于一种FILO数据结构，类似阉割版本的顺序表，在计算机中有非常广泛的应用

例：使用递归时，编译器自身对于递归指令的使用就是一种栈，或者计算中缀表达式（通过将中缀表达式转换为后缀表达式，再对后缀表达式进行栈运算就可以得出结果）->全部利用栈的FILO结构

栈制造方式
  • 数组栈->非常非常easy
  • 链表栈->参考链表，但是阉割
栈做非降路径问题

离散数学组合数学里面的东西，如果对一个栈仅允许出栈入栈操作，对输入固定长度字母求所有的输出模式，其实本质就是一个非降路径，只需要计算从(0,0)到(n,n)的不经过y=x+1的所有路径

中缀表达式转换后缀表达式

(104条消息) 中缀表达式转后缀表达式的方法_說詤榢的博客-CSDN博客_中缀表达式转后缀表达式

正则表达式分析

分析：

  • 使用栈来求：中缀表达式可以拆分成一棵中缀树，后缀类似拆分成后缀树，如（1+1）（2+2），中缀中根节点是，叶节点是+，叶子是1 1 2 2，如果用树的思想去做应该使用树的中序遍历，但是问题在于不好处理运算符的优先级问题，而改造成后缀表达式就会方便很多，如同上例子换成后缀表达式变成了1 1 + 2 2 + *，然后使用栈来进行运算，数字压栈，运算符出栈两个进行运算后再次压栈，这样就可以避开运算符优先级的处理问题（相对更好理解一些而且不需要搭建树，可以使用栈来搞）
  • 使用递归来求：已知将该表达式抽象成为一棵树，那么对每个子树使用递归求值可以不断削减树的层数，最后获得根树的值（**很牛逼但是很麻烦，要提前接触到树**）

这里使用栈来进行一个中缀表达式的计算

先看下只有 + 和 * 的。

输入长度为n的字符串，例如：1+2+345

输出表达式的值，即：63

应该用什么数据结构？

栈。

应该先计算哪一步？

实际应该先计算1+2。

“表达式求值”问题，两个核心关键点：

（1）双栈，一个操作数栈，一个运算符栈；

（2）运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：

如果栈顶的运算符优先级低，新运算符直接入栈

如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈

仍以1+2+345举例，看是如何利用上述两个关键点实施计算的。

首先，这个例子只有+和*两个运算符，所以它的运算符表是：

image

这里的含义是：

（1）如果栈顶是+，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；

（2）如果栈顶是+，即将入栈的是*，栈顶优先级低，直接入栈；

（3）如果栈顶是*，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；

（4）如果栈顶是， 即将入栈的是，栈顶优先级高，需要先计算，再入栈；

有了运算符表，一切就好办了。

image

一开始，初始化好输入的字符串，以及操作数栈，运算符栈。

image

一步步，扫描字符串，操作数一个个入栈，运算符也入栈。

image

下一个操作符要入栈时，需要先比较优先级。

栈内的优先级高，必须先计算，才能入栈。

image

计算的过程为：

（1）操作数出栈，作为num2；

（2）操作数出栈，作为num1；

（3）运算符出栈，作为op；

（4）计算出结果；

image

（5）结果入操作数栈；

image

接下来，运算符和操作数才能继续入栈。下一个操作符要入栈时，继续比较与栈顶的优先级。

栈内的优先级低，可以直接入栈。

image

字符串继续移动。

image

又要比较优先级了。

image

栈内的优先级高，还是先计算（3*4=12），再入栈。

image

不断入栈，直到字符串扫描完毕。

image

不断出栈，直到得到最终结果3+60=63，算法完成。

总结

“表达式求值”问题，两个核心关键点：

（1）双栈，一个操作数栈，一个运算符栈；

（2）运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：
如果栈顶的运算符优先级低，新运算符直接入栈

如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈

这个方法的时间复杂度为O(n)，整个字符串只需要扫描一遍。

运算符有+-/()~^&都没问题，如果共有n个运算符，会有一个nn的优先级表。

正则表达式代码

代码：

上 代 码

虽然但是接下来这个代码是中缀计算的

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
#include <iostream>
#include <stack>//stl库中使用栈
#include <string>//
#include <unordered_map>//一个目前不太懂的头文件，回头看primer自己理解吧
using namespace std;

stack<int> num;//存储数字的栈
stack<char> op;//存储运算符的栈

//优先级表
unordered_map<char, int> h{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };


void eval()//求值
{
    int a = num.top();//第二个操作数
    num.pop();

    int b = num.top();//第一个操作数
    num.pop();

    char p = op.top();//运算符
    op.pop();

    int r = 0;//结果 

    //计算结果
    if (p == '+') r = b + a;
    if (p == '-') r = b - a;
    if (p == '*') r = b * a;
    if (p == '/') r = b / a;

    num.push(r);//结果入栈到num中
}

int main()
{
    string s;//读入表达式
    cin >> s;

    for (int i = 0; i < s.size(); i++)//调用了string的函数s.size()
    {
        if (isdigit(s[i]))//判断数字入栈
        {
            int x = 0, j = i;//计算数字
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';//将string型的数字转换为int？
                j++;
            }
            num.push(x);//数字入栈
            i = j - 1;
        }
        //左括号无优先级，直接入栈
        else if (s[i] == '(')//左括号入栈
        {
            op.push(s[i]);
        }
        //括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的
        else if (s[i] == ')')//右括号
        {
            while(op.top() != '(')//一直计算到左括号
                eval();
            op.pop();//左括号出栈
        }
        else
        {
            while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低，则先计算
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算
    cout << num.top() << endl;//输出结果
    return 0;
}

单调栈（瞳孔地震型题解）😢

使用单调递增栈

麻烦地方：超时

考虑方式有些类似双指针

思路：暴力->优化暴力

队列里面是否有元素没用

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
const int N=10010;
int n;
int stk[N],tt;
int main()
{
    cin>>n;//总共要输入几次数
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x)tt--;//如果栈内元素只要比待进入元素小就弹出
        if(tt)cout<<stk[tt]<<" ";//弹出后输出第一个栈顶元素
        else cout<<-1<<" ";//栈空后输出-1
        stk[++tt]=x;//一轮走下来以后新的元素入栈
    }
    return 0;
}

队列

FIFO构造

队列构造方式：

数组构造（也是hin简单就是了）😒

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
//模板用栈直接改都可以
const int M=200600;

int bottom=0;//队列底部，弹出时候bottom+1
int line[M]={0};
int top=0;//队列头部，增加时候top+1
void insert(int x)//入队
{
    
    line[top]=x;
    ++top;
}
void pop(void)
{
    bottom++;//底部上移
}
void query(void)
{
   cout<<line[bottom]<<endl;
   return;
}
void empty(void)
{
    if(top==bottom)cout<<"YES\n";
    else cout<<"NO\n";
    return;
}
循环队列：

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;//如果到达某一特定值那么就重置变成队头

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)//不为空
{

}
单调队列~~~~~~~(～￣▽￣)～滑动窗口经典（配合单调栈食用）

😶‍🌫️准备好开始头疼

思路同单调栈：从暴力解决入手接着开始优化

可以使用队列对窗口进行维护（标准的入列和出列）

优化：队列中是否有没用的元素，对没用的元素进行删除看能否得到单调性，如3，-1，-3，在-3入列的时候就有3>-3，则最小值一定不会是3而且-3存在时间更久，因此使用单调栈的同样原理可以求出单调最小，并且是一个单调递增的最小

可以使用STL标准库来写或者说使用栈和队列数组模拟去写，而相对而言使用数组有很大的好处在于数组速度快，在比赛或者笔试时候会慢一些，在IDE中可能会有O2或者O3优化

再看一遍单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
const int N=10010;
int n;
int stk[N],tt;
int main()
{
    cin>>n;//总共要输入几次数
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x)tt--;//如果栈内元素只要比待进入元素大就弹出
        if(tt)cout<<stk[tt]<<" ";//弹出后输出第一个栈顶元素
        else cout<<-1<<" ";//栈空后输出-1
        stk[++tt]=x;//一轮走下来以后新的元素入栈
    }
    return 0;
}

image

解题思路（以最大值为例）：

由于我们需要求出的是滑动窗口的最大值。

如果当前的滑动窗口中有两个下标 i 和 j ，其中i在j的左侧（i<j），并且i对应的元素不大于j对应的元素（nums[i]≤nums[j]），则：

当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中。这是由于 i 在 j 的左侧所保证的。

因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将nums[i]永久地移除。

因此我们可以使用一个队列存储所有还没有被移除的下标，这里是q。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组nums中对应的值是严格单调递减的。

当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。

为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果新元素大于等于队尾元素，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。

由于队列中下标对应的元素是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。

窗口向右移动的时候。因此我们还需要不断从队首弹出元素保证队列中的所有元素都是窗口中的，因此当队头元素在窗口的左边的时候，弹出队头。

每一个窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
hh = 0; tt = -1;          //头在左尾在右                         // 重置！
    for (int i = 0; i < n; ++ i)
        //注意这个栈可以想成朝着右边（tt，正常栈操作），但是底部可以操作（hh，向右缩）
    {
        //窗口终点是i，那么起点就是i-k+1
        if (i - k + 1 > q[hh]) ++ hh;//窗口左边向右移动一个
        
        //这里操作下来要是从大到小的排列
        
        while (hh <= tt && a[i] >= a[q[tt]]) -- tt;//右边已经有更大的了，之前的小的a[q[tt]]可以不用考虑了，就操作tt
        q[++ tt] = i;//窗口右边向右移动一个
        //i+1>=k这里就是一个特判，因为一开始窗口没有值，只有窗口全部充满之后才有后面的操作
        if (i + 1 >= k) printf("%d ", a[q[hh]]);//这里知道栈的底部（也就是q[hh]）对应的下标是该窗口中没有删除而且是最大的
    }

判断最小

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
int a[N]={0};
int q[N]={0};
int hh=0;
int tt = -1;//尾部是1
int n, k;//hh是头，tt是尾，
//

//头在左尾在右



    cin >> n >> k;//k是窗口大小
    for (int i = 0; i < n; ++ i)
    {
        //这里是关于窗口的维护
        scanf("%d", &a[i]);//数组a存放了所有的数字
        if (i - k + 1 > q[hh]) ++ hh;       
        //数组q存放的是下标
        // 若队首出窗口，hh加1，即整体向前移动一格
        
        //这里开始跟单调栈的原理相同
        /*
        hh<=tt是队列不为空
        a[i] <= a[q[tt]]这里就是单调栈的如果新来的a[i]不是栈里面最大的就弹栈，--tt
        */
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调，tt减1
        q[++ tt] = i;                                  // 下标加到队尾，新元素入栈，上面入的是元素本身这里入的是元素下标
        
        if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 这里确定过栈中的都是最小的元素了因此直接输出
        //输出结果
    }
    cout << endl;//换行

全部代码！

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
# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], tail = -1;
int head=0;
//a存储正常原数组的值
//注意注意q存储的是a的“下标”，“下标”而不是“值”
int main()
{
    int n, k;//hh是头，tt是尾
    cin >> n >> k;
    for (int i = 0; i < n; ++ i)//输出最小，每一次循环里面q[head]的值也就是a[q[head]]总是窗口中最小的
    {
        //i-k+1就是窗口头部位置
        scanf("%d", &a[i]);
        if (i - k + 1 > q[head]) ++ head;                  // 若队首出窗口，head加1
        while (head <= tail && a[i] <= a[q[tail]]) -- tail;    // 若队尾不单调，tail持续减1
        q[++ tail] = i;                                  // 下标加到队尾,尾部进入窗口
        if (i-k + 1 >= 0) printf("%d ", a[q[head]]);       // 输出结果(只有窗口形成之后才会输出)
    }
    cout << endl;
    head = 0; tail = -1;                                   // 重置！
    for (int i = 0; i < n; ++ i)
    {
        if (i - k + 1 > q[head]) ++ head;				//判断头部是否出窗口
        while (head <= tail && a[i] >= a[q[tail]]) -- tail;
        q[++ tail] = i;
        if (i + 1 >= k) printf("%d ", a[q[head]]);
    }
    return 0;
}

串

KMP

(100条消息) 数据结构KMP算法配图详解（超详细）_哈顿之光的博客-CSDN博客_kmp算法难吗是什么级别（好好看好好学）

模板y总

注意kmp算法的下标要从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
for(int i=1;i<=n;i++)//一开始就是1开始弄的
{
    cin>>p[i];
}

或者邪教读取法:cin>>n>>p+1>>m>>s+1

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )//与匹配部分基本一样一样
{//一点细节，这里是子串p
    while (j && p[i] != p[j + 1]) j = ne[j];//也是回溯
    if (p[i] == p[j + 1]) j ++ ;//匹配成功子串向前走
    ne[i] = j;//欸，这里不一样了，
    //ne数组其实也是一样样的，i=2是因为实际上1是肯定是0（前面都没字符自然是0），ne数组也是从1开始
}

// kmp匹配
for (int i = 1, j = 0; i <= n; i ++ )//
{//一点细节，下面是长串s
    while (j && s[i] != p[j + 1]) j = ne[j];//不相等的时候递归回退，与代码随想录是一种方法
    if (s[i] == p[j + 1]) j ++ ;//如果匹配成功，子串也向前一位走
    if (j == m)
    {
        j = ne[j];//回溯到前一次
        // 匹配成功后的逻辑
    }
}


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
#include<iostream>
using namespace std;
const int N=100010,M=1000010;
char p[N],s[M];
int ne[N];
int n,m;
int main()
{
	cin>>n>>p+1>>m>>s+1;
	for(int i=2,j=0;i<=n;i++)
	{
		while(j&&p[i]!=p[j+1])j=ne[j];
		if(p[i]==p[j+1])j++;
		ne[i]=j;
	}
	for(int i=1,j=0;i<=m;i++)
	{
		while(j&&s[i]!=p[j+1])j=ne[j];
		if(s[i]==p[j+1])j++;
		if(j==n)
		{
			cout<<i-n<<' ';//就是输出下标
			j=ne[j];
		}
	}
	return 0;
}

关键：特殊数组next的构造，前缀表

image

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了

前缀表：字符串的最长

前缀：不包含尾字符的所有子串

后缀：相较于前缀，不包含首字母的所有子串

因此如果仅有单个字符则其前缀为0

特性：

目前讲解的构造方法

例：子串aabaabaaf，前缀表010120(aabaaf)

  • 前缀形式：010120
  • 全部后移方式：-1 0 10120
  • 整体减一方式：-1 0 -1 0 1 -1

共同点：最后都应当保持封闭，虽然理解有出入但本质相同

代码随想录方法：前缀不减形式

prev,latter;

prev:前缀末尾位置，同时代表prev包括prev之前子串最长相等前后缀的长度，也表示前缀末尾

latter:后缀末尾位置

初始化

1
2
3
4
5
prev=0;
latter=1;
next[0]=0;
//初始化latter

开始处理前后缀不同情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//prev和latter一直不相等
for(latter=1;latter<slength;latter++)//后缀指针只管往前走就完事
{
    //这里if是出错的根源
    while(s[prev]!=s[latter]&&prev>0)//注意这里因为有-1存在所以一定小心越界，
    {
        prev=next[prev-1];//prev冲突时候是一个连续回退的过程，如果使用if就错了，使用while循环回退
    }
    //只要s[latter]!=s[prev]时候prev应该向前回退
    //原因：使用前缀表在进行kmp对比的时候如果遇到冲突，也是看冲突位置前一位的表进行跳转
    
    分界线：前后缀相同的情况
        if(s[prev]==s[latter])
        {
            prev++;//代表prev之前最长相等前缀可以更新
           
           //latter因为有for循环，因此自然向前有++操作
        }
    	 next[latter]=prev;//更新next数组的值
    
    
}

这里则是全部操作的部分

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
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
//这里是返回第一个找到的下标
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);//获取next数组
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) {
            while(j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];//一样进行回溯
            }
            if (haystack[i] == needle[j]) {
                j++;
            }//使用循环，直接对prev进行+就行
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }

image

注意这里是文本串和模式串不匹配时候的操作（这里next数组采用正常前缀表）

数据结构作业出错原因

要求每一个都求出来

问题在于：当每一次满足条件后进行清零操作，本质上同一次两者不等时候的回溯操作（prev到上一位最接近的前缀位置）,如果使用prev=0就会出现可能错过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
例：
    ababa  aba 001
    //正确解
    if(prev==sublength)
        {
            cout<<endl<<latter-sublength+1<<endl;
            prev=next[prev-1];//回溯
        }
	//在第一次解的时候prev=3;latter=2(因为latter在一次循环之后才会有增操作)
	/*
	使用回溯prev=1,sub[prev]=b那么就接着从latter=3.T[latter]=b无缝开始向前对比
	*/

/错误
    if(prev==sublength)
        {
            cout<<endl<<latter-sublength+1<<endl;
            prev=0;//这样就会是错误结果
        }
automata~有限状态自动机

参考：

代码（构建自动机状态表）
1
2
3
4
5
6
7
8
9
10
11
12
dfa[0][P[0]] = 1; //初始化第一行
// dfa[状态][下一个字符] for(int X = 0, j = 1; j < plen; j++) {

// 计算 dfa[j][]

for(int c = 0; c < R; c++) { // R 为字符种类数量

dfa[j][c] = dfa[X][c];

} dfa[j][P[j]] = j + 1; X = dfa[X][P[j]]

}

image

image

聪明版本自动机

已知ascii码总共就128个，直接开一个大表就行

1
int dfa[256][256]=0;//这样直接省略后续一系列初始化，使用int转换字符串传入就行，非常省心
TRIE树（有些类似哈夫曼树编码）

类似但和哈夫曼树没有关系

又称字典树、单词查找树

应用：快速存储和查找字符串集合的数据结构

如何存储：构建串树

从根节点开始存储每一个字符，开始逐个向下进行创建，在单词的末尾打上一个标记表示该单词走到结尾了

image

TRIE树本质是一颗N叉树，有多少种字符一个节点就最多有多少条边

image

如何查找

从单词的首字母开始向下走，走到标记表示到头了

构建TRIE树

这里使用了数组模拟树的知识

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
#include <iostream>

using namespace std;

const int N = 100010;

int son[N][26];
//这里是26因为只有小写字母
//二维是可以有多少个分支，一维的意义是来自哪一个双亲节点
int cnt[N], idx;//idx是下标为0的点，是根节点和空节点，表示当前要插入的节点是第几个,每创建一个节点值+1
   // cnt[]存储以某节点结尾的字符串个数（同时也起标记作用）
char str[N];//存储要插入/查询的单词

void insert(char *str)
{
    int p = 0; //类似指针，指向当前节点
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';//u表示是具体哪一个字母
        //p表示的是第几个结点，u表示的是哪个字母，如果s[p][u]不为空就证明有以这个字母为值的子结点
        //它代表的值就是指向了该子结点，即说明了第几个结点是它的子结点
         //如s[2][1]=3，表示结点2有一个值为b（第二个数字代表的是a～z）的子结点，是结点3
        if (!son[p][u]) son[p][u] = ++ idx;//不存在就创建节点
        //令p指向子结点
        p = son[p][u];
    }
    //不管是未存在过的新插入还是已有字典再增加一个，都是以这个结点为末尾的字符串次数加1
    cnt[p] ++ ;//结束时的标记，也是记录以此节点结束的字符串个数
    //这一步重要！
    
    
}

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )//走到该单词为0
    {
        int u = str[i] - 'a';//获得对应子节点的编号
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];//返回以p为结尾的单词数量
}

int main()//这里有I是插入字符串，其它是查找该字符串
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);//前一次输入被覆盖
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

TRIE树的其它应用

https://www.acwing.com/blog/content/32/%E5%A5%BD%E4%B8%9C%E8%A5%BF

启示：字典树不单单可以高效存储和查找字符串集合，还可以存储二进制数字

思路：利用二叉树

对所有的aiaj建立一个串数组，对于每一个固定的ai，每一次尽量与和当前不同的分支向下走，走到底这样一定就可以得到最优解

即顺序：所有值的二进制表示建立树->遍历一次，每一个ai进行寻找对应的最大的值，最后遍历一次之后获得答案

算法复杂度：

（建立树）+n（每一个ai只需要在已经建立好的树再从头到尾走一次就好）

代码：

insert函数改：

每个数看作一个31位长度的二进制数，最高位是0往0走，最高位1往1走，然后和类似TRIE的操作，但是构建的是一颗二叉树（一定概率变成斜树）

1
2
3
4
5
6
7
8
9
10
11
void insert(int x)
{
    int p=0;  //根节点
    for(int i=30;i>=0;i--)//从最大位开始建立
    {
        int u=x>>i&1;   /////取X的第i位的二进制数是什么  x>>k&1(前面的模板)
        if(!son[p][u]) son[p][u]=++idx; ///如果插入中发现没有该子节点,开出这条路
        p=son[p][u]; //指针指向下一层
    }//与上面不一样这里就不需要标记
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int search(int x)
{
    int p=0;int res=0;
    for(int i=30;i>=0;i--)
    {                               ///从最大位开始找
        int u=x>>i&1;
        if(son[p][!u]) ////如果当前层有对应的不相同的数
        {   ///p指针就指到不同数的地址

          p=son[p][!u];
          res=res*2+1;//右移，因为树右儿子是1
             ///*2相当左移一位  然后如果找到对应位上不同的数res+1 例如    001
        }                                                   ///       010 
        else////   --->011                                                                           
            //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
        {
            p=son[p][u];
            res=res*2+0;//左移，因为树左儿子是1
        }
    }
    return res;
}
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
#include<iostream>
#include<algorithm>
using namespace std;
int const N=100010,M=31*N;//M表示树的节点个数，每个数最多有31个长度，因此建立
int n;
int a[N];
int son[M][2],idx;
//M代表一个数字串二进制可以到多长

void insert(int x)
{
    int p=0;  //根节点
    for(int i=30;i>=0;i--)//这里相等i>=0
    {
        int u=x>>i&1;   /////取X的第i位的二进制数是什么  x>>k&1(前面的模板)
        if(!son[p][u]) son[p][u]=++idx; ///如果插入中发现没有该子节点,开出这条路
        p=son[p][u]; //指针指向下一层
    }
}
int search(int x)
{
    int p=0;int res=0;
    for(int i=30;i>=0;i--)
    {                               ///从最大位开始找
        int u=x>>i&1;
        if(son[p][!u]) ////如果当前层有对应的不相同的数
        {   ///p指针就指到不同数的地址

          p=son[p][!u];
          res=res*2+1;
             ///*2相当左移一位  然后如果找到对应位上不同的数res+1 例如    001
        }                                                       ///       010 
        else                                            ////          --->011                                                                           //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
        {
            p=son[p][u];
            res=res*2+0;
        }
    }
    return res;//最后返回是十进制形态的答案
}
int main(void)
{
    cin>>n;
    idx=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }
    int res=0;
    for(int i=0;i<n;i++)
    {   
        res=max(res,search(a[i]));  ///search(a[i])查找的是a[i]值的最大与或值
    }
    cout<<res<<endl;
}

跳表——同样面试——但是不用手搓

一些参考的博客：

(101条消息) 十分钟弄懂什么是跳表，不懂可以来打我_愤怒的可乐的博客-CSDN博客_跳表

优点：将链表查找的时间复杂度改造成log，据说可以取代红黑树

跳表属于对链表的改进

有点相似kmp？通过一些手段加快跳跃的速度

想法：链表中增加一些“超级链接”

特点：
  • 跳表结合了链表和二分查找的思想
  • 由原始链表和一些通过“跳跃”生成的链表组成
  • 第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
private class Node {
    //保存值
    E data;
    //保存了每一层上的节点信息，可能为null
    List<Node> forwards;

    Node(E data) {
        this.data = data;
        forwards = new ArrayList<>();
        //事先把每一层都置为null，虽然空间利用率没那么高，但是简化了实现
        //也可以通过自定义列表(比如B树实现中用到的Vector)来实现，就可以不用下面的操作
        for (int i = 0; i <= maxLevel; i++) {
            forwards.add(null);
        }
    }

    @Override
    public String toString() {
        return data == null ? " " : "" + data;
    }

    /**
     * 得到当前节点level层上的下一个(右边一个)节点
     *
     * @param level
     * @return
     */
    Node next(int level) {
        return this.forwards.get(level);
    }

}

TRIE树的其它

散列表——哈希表-面试很重要

特点：查找与删除，查找全部在常数时间内完成

应用：

  • 操作系统
  • 数据库
  • 编译器
  • 计网
  • 图像检索（最初始用于人脸识别等）
线性表总结：

image

哈希定义，应用

本质：给定一个输入给出一个唯一的序列号输出，将一个比较大的空间映射到一个比较小的空间，将一个复杂的数据结构映射到一个小的

应用举例：

  • 输入n个数10^5，数的范围+-10^9,选择一些数字插入，选择另外一些数字查询
  • 文本压缩和解压缩

定位的过程：元素通过哈希函数转换成唯一的整数（必须快速计算）image

第一步：将一个元素映射成一个整数

哈希模板（正常+字符串版本）
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
(1) 拉链法
    int h[N], e[N], ne[N], idx;
	const int  N=1e5+3;
    // 向哈希表中插入一个数
    void insert(int x)//这么理解：就是正常的数组模拟链表，但是加入哈希函数
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];//就是把head换成了h[k],因为原先是单链，现在多链
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;//首先哈希
        for (int i = h[k]; i != -1; i = ne[i])
            {if (e[i] == x)
                return true;}

        return false;
    }

(2) 开放寻址法
    const int N=2e5+3;//开放寻址的大小要放大的
    int h[N];
	const int null=0x3f3f3f3f;
    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)//这里易错，是&&
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

分配索引值

这里对字符进行处理，每一种字符都视为一种对应的数字，不同的位数有不同的加权值

1
2
3
4
5
6
7
8
9
10
unsigned int hash(char *key)
{ unsigned int hash_val = 0;
 while(*key != '\0') 
 { hash_val = (hash_val << 5) + *key++;
//这里使用<<实际上就是直接×2^5
  //每一次移动5位（这样子硬件便于实现，参考计组）
} return hash_val;

}

缺点：虽然时间非常高效，但是空间浪费非常大（毕竟不能载满）

减少索引值：

方法1：忽略一部分元素，将另一部分直接视为索引值

好处：快，坏处：难于分配索引值

方法2：折叠，使用不同方式将原数据拆分，再合并在一起

方法3：余数运算，可以元素值除以某一特殊数字，余数用作索引值，

1
2
3
4
5
6
unsigned int hash(char *key, unsigned int H_SIZE) 
{ unsigned int hash_val = 0; while(*key != '\0') { hash_val = (hash_val << 5) + *key++;

} return hash_val % H_SIZE;//这里缩了一下

}
字符串哈希——>字符串前缀哈希法

作用有些类似kmp，字符串也可以用哈希表做->一个集合到另一个集合的映射

实际上是字符串的前缀哈希法，对前缀进行哈希

问题：

  • 如何定义某一个前缀的哈希值，可以将字符串视为p进制的一个数，每一位上的字母（acscii）视为对应的数字，但是不能映射成0->相同的字符串映射结果会相同->AA等等
  • 哈希字符串假定人品足够不存在碰撞，没有考虑冲突情况，经验值：p取131或13331时候，q取2^64，几乎99%情况不会出现冲突

好处：可以利用最前的哈希计算出所有子串的哈希，

已知h[r],h[l],

h[r]中r为第0位，h[l-1]中l-2为第0位

操作

  1. h[l-1]与h[r]对齐，即向后移动多少位
  2. h[r]-h[l-1]就能求出来了

小技巧：使用unsigned long long 存储所有h，相当于对所有数取模了(因为溢出就相当于取模)

总结：左移高位对齐

之后对前缀全部处理完之后，就能用o1时间计算任意子串哈希值

预处理：h[i]=h[i-1]*p+str[i] (第i位字母)

牛逼的地方：比kmp牛逼：可以快速判断，快过o(n),是处理字符串的利器

代码核心部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

完整代码：

841. 字符串哈希 - AcWing题库

AcWing 841. 字符串哈希 【公式助理解】 - AcWing

image

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
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned long long ULL;//也就是取模2^64，
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];

// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
ULL query(int l,int r){
    return h[r] - h[l-1]*p[r-l+1];
    //为求l到r的哈希值
    //已知h[r],h[l-1]，也就是1到l-1，1到r的哈希值
    //因为字符串视为一个p进制的数，因此越左边权重越高，为高位，右边是低位
    //h[r]中r是第0位，h[1]为r-1位
    //h[l-1]l-1是第0位，h[1]为l-2位
    //两者相差r-1-l+2=r-l+1位
    //本质就是高位对齐，h[r]与h[l-1]对齐，
}
int main(){
    int n,m;
    cin>>n>>m;
    string x;
    cin>>x;

    //字符串从1开始编号，h[1]为前一个字符的哈希值
    p[0] = 1;
    h[0] = 0;
    //以上是初始化，第0位实际上不加入计算
    for(int i=0;i<n;i++){
        p[i+1] = p[i]*P;            
        h[i+1] = h[i]*P +x[i];      //前缀和求整个字符串的哈希值
        //这里x也是从第一位开始，也就是0
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}

哈希碰撞处理（面试高频）😍😍😍😍😍

可以把离散化看成一种特殊的哈希方式

哈希表属于期望算法，可以将哈希表的链长视为一个常数，

碰撞：两个相同的索引放在相同的索引位置

碰撞可能性很大->定义域很大值域比较小

拉链法（Open Hashing）

原理：如果多个索引值最终哈希值相同，使用链表的形式另外存储相同的值

添加，直接添加链

查找：对应位置在链表遍历一下

删除：算法题中一般不会进行删除节点，而是会开 一个数组打一个标记（如bool标记）

数学上取质数，而且举例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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 取大于1e5的第一个质数，而且要离2的整次幂尽可能远， 取质数冲突的概率最小

//* 开一个槽 h
//图论中存点的方式和数组的链法一样，都是一个数组一个链
int h[N], //哈希表
//经典数组实现链表
e[N], 
ne[N], 
idx;  //邻接表

void insert(int x) {
    // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    int k = (x % N + N) % N;//k就是对应的哈希值，这一步实现了映射。接下来是写入
    //(x%N+N)这一步为了最后一定是一个正数，如果是负数数组无法写入
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {//这里是遍历对应到的链表
        //同时由于初始化是-1，开始哈希数组也要初始化为-1
        if (e[i] == x) {
            return true;
        }
    }
    return false;
}

int n;

int main() {
    cin >> n;

    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示
    //

    while (n--) {
        string op;//字符串的话编译器会自动忽略空格，换行符等，不容易出错
        //有些脏数据会增加额外空格
        int x;
        cin >> op >> x;
        if (op == "I") {
            insert(x);
        } else {
            if (find(x)) {
                puts("Yes");
            } else {
                puts("No");
            }
        }
    }
    return 0;
}

缺点：消耗空间

开放地址法 Open Addressing

思路：只用一个一维数组来模拟哈希表，因此形式会相对简洁，但是一般来说一维数组的长度应该是需要的数组大小的2~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
#include <cstring>
#include <iostream>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3f
//这个数只要不在原本数据范围内就行

int h[N];

int find(int x) {//这一个函数同时实现查找和插入功能
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x) {
        t++;//这一步是线性探测，可以使用平方或者伪随机优化
        if (t == N) {//如果到头了，就返回从头找
            t = 0;
        }
    }
    return t;  //如果这个位置是空的, 则返回的是他应该存储的位置
}

int n;

int main() {
    cin >> n;

    memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3f

    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") {
            h[find(x)] = x;//妙啊
        } else {
            if (h[find(x)] == null) {
                puts("No");
            } else {
                puts("Yes");
            }
        }
    }
    return 0;
}

杜鹃哈希😎

感觉：拆东墙补西墙，但是很牛逼

优点：只要两个表中间有元素，一定可以通过哈希函数在顺序表中直接找到不用探测，非常高效

原因：所有索引位置都是哈希函数得到

失败时：
  • 没有足够空间，路径无限循环
  • 转移链表过长

缺点：元素过多时候插入元素困难

(101条消息) 杜鹃散列_EmberWn的博客-CSDN博客_杜鹃散列

【散列】杜鹃散列详情与C++实现代码 - awst_lee - 博客园 (cnblogs.com)

Cuckoo hash算法分析 - 可酷可乐 - 博客园 (cnblogs.com)

Cuckoo hashing - Wikipedia（科学上网看）

杜鹃哈希举例：

坏消息：根本看不懂

好消息：不用看了

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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
//为杜鹃散列生成泛型HashFamily接口,用来发出多簇散列函数到杜鹃散列表
template<typename AnyType>
class CuckooHashFamily {
public:
	size_t hash(const AnyType& x, int which)const;
	int getNumberOfFunctions();
	void generateNewFunctions();
};
 
/**
* 杜鹃散列法的非正式字符串散列
*/
template<int count>
class StringHashFamily {
private:
	std::vector<int> MULTIPLIERS;
	UniformRandom r;
 
public:
	StringHashFamily() :MULTIPLIERS(count) {
		generateNewFuntions();
	}
	int getNumberOfFunctions()const {
		return count;
	}
	void generateNewFuntions() {
		for (auto& mult : MULTIPLIERS)
			mult = r.nextInt();
	}
 
	size_t hash(const string& x, int which)const {
		const int multiplier = MULTIPLIERS[which];
		size_t hashVal = 0;
		for (auto ch : x)
			hashVal = multiplier * hashVal + ch;
		return hashVal;
	}
};
 
//杜鹃散列类接口，允许(由HashFamily模板参数类型指定)任意个数的散列函数
template<typename AnyType, typename HashFamily>
class HashTable {
private:
	struct HashEntry {
		AnyType element;
		bool isActive;
 
		HashEntry(const AnyType&e=AnyType(),bool a=false)
			:element{e},isActive{a}{}
		HashEntry(AnyType&&e,bool a=false)
			:element{std::move(e)},isActive{a}{}
	};
 
	/**
	* 杜鹃散列的插入例程使用不同的算法，
	* 该算法随机选择要逐出的项，
	* 但不再试图重新逐出最后的项。
	* 如果存在太多的逐出项则散列表将尝试选取新的散列函数(再散列)，
	* 而若有太多的再散列则散列表将扩张
	*/
	bool insertHelper1(const AnyType& xx) {
		const int COUNT_LIMIT = 100;
		AnyType x = xx;
 
		while (true) {
			int lastPos = -1;
			int pos;
 
			for (int count = 0; count < COUNT_LIMIT; ++count) {
				for (int i = 0; i < numHashFunctions; ++i)
					pos = myhash(x, i);
					
				if (!isActive(pos)) {
					array[pos] = std::move(HashEntry{ std::move(x),true });
					++currentSize;
					return true;
				}
			}
 
			//无可用位置，逐出一个随机项
			int i = 0;
			do {
				pos = myhash(x, r.nextInt(numHashFunctions));
			} while (pos == lastPos && i++ < 5);
 
			lastPos = pos;
			std::swap(x, array[pos].element);
		}
 
		if (++rehashes > ALLOWED_REHASHES) {
			expand();		//使散列表扩大
			rehashes = 0;	//重置rehashes的计数
		}
		else
			rehash();		//表大小相同，散列函数都是新的
	}
	bool insertHelper1(AnyType&& x) {
		const int COUNT_LIMIT = 100;
 
		while (true) {
			int lastPos = -1;
			int pos;
 
			for (int count = 0; count < COUNT_LIMIT; ++count) {
				for (int i = 0; i < numHashFunctions; ++i)
					pos = myhash(x, i);
 
				if (!isActive(pos)) {
					array[pos] = std::move(HashEntry{ std::move(x),true });
					++currentSize;
					return true;
				}
			}
 
			//无可用位置，逐出一个随机项
			int i = 0;
			do {
				pos = myhash(x, r.nextInt(numHashFunctions));
			} while (pos == lastPos && i++ < 5);
 
			lastPos = pos;
			std::swap(x, array[pos].element);
		}
 
		if (++rehashes > ALLOWED_REHASHES) {
			expand();		//使散列表扩大
			rehashes = 0;	//重置rehashes的计数
		}
		else
			rehash();		//表大小相同，散列函数都是新的
	}
	bool isActive(int currentPos)const {
		return currentPos != -1 && array[currentPos].isActive;
	}
 
	/**
	* 使用特定函数计算x的散列代码
	* 选取适当的散列函数，然后把它换算成合法的数组下标
	*/
	size_t myhash(const AnyType& x, int which)const {
		return hashFunctions.hash(x, which) % array.size();
	}
 
	/**
	* 查找所有散列函数的位置
	* 返回查阅所有的散列函数以返回包含项x的下标，若找不到则返回-1
	*/
	int findPos(const AnyType& x)const {
		for (int i = 0; i < numHashFunctions; ++i) {
			int pos = myhash(x, i);
 
			if (isActive(pos) && array[pos].element == x)
				return pos;
		}
		return -1;
	}
 
	/**
	* 创建一个大数组但使用那些相同的散列函数
	*/
	void expand() {
		rehash(static_cast<int>(array.size() / MAX_LOAD));
	}
 
	/**
	* 保留数组的大小不变，创建一个新的数组
	* 该数组使用那些新选出的散列函数填充
	*/
	void rehash() {
		hashFunctions.generateNewFuntions();
		rehash(array.size());
	}
 
	void rehash(int newSize) {
		std::vector<HashEntry> oldArray = array;
 
		//创建新的双倍大小的空散列表
		array.resize(nextPrime(newSize));
		for (auto& entry : array)
			entry.isActive = false;
 
		//复制整个表
		currentSize = 0;
		for (auto& entry : oldArray)
			if (entry.isActive)
				insert(std::move(entry.element));
	}
 
	constexpr static const double MAX_LOAD=0.4; //最大装填因子
	static const int ALLOWED_REHASHES = 5; //最大散列次数
 
	vector<HashEntry>array;
	int currentSize;
	int numHashFunctions;
	int rehashes;
	UniformRandom r;
	HashFamily hashFunctions;
 
public:
	explicit HashTable(int size = 101) :array(nextPrime(size)) {
		numHashFunctions = hashFunctions.getNumberOfFunctions();
		rehashes = 0;
		makeEmpty();
	}
 
	//清空杜鹃散列表
	void makeEmpty() {
		currentSize = 0;
		for (auto& entry : array)
			entry.isActive = false;
	}
 
	/**
	* 搜索杜鹃散列表的例程
	* 如果找到x则返回true
	*/
	bool contains(const AnyType& x)const {
		return findPos(x) != -1;
	}
 
	/**
	* 从散列表中删除x
	* 若项x被找到且被删除则返回true
	*/
	bool remove(const AnyType& x) {
		int currentPos = findPos(x);
		if (!isActive(currentPos))
			return false;
 
		array[currentPos].isActive = false;
		--currentSize;
		return true;
	}
 
	//杜鹃散列表中公有插入方法
	bool insert(const AnyType& x) {
		if (contains(x))
			return false;
 
		if (currentSize >= array.size() * MAX_LOAD)
			expand(); 
 
		return insertHelper1(x);
	}
	bool insert(AnyType&& x) {
		if (contains(x))
			return false;
 
		if (currentSize >= array.size() * MAX_LOAD)
			expand(); 
 
		return insertHelper1(std::move(x));
	}
 
	int size() const
	{
		return currentSize;
	}
 
	int capacity() const
	{
		return array.size();
	}
};

树

最后通过看大神的代码才恍然大悟，二叉树的建立，需要按照一棵满二叉树来建立

问题来了，我们的节点不够满二叉树的，这就是关键，空节点也需要补上！

使用数组构造一棵二叉树也是同理！

完全二叉树的构建（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
#include<iostream>
using namespace std;
const int M=1010;//完全二叉树
int tree[M]={0};//全部初始化成0方便判断
int judge=1;//判断是否继续读入
int real_depth(int n)
{
    int ans=0;
    while(n!=0)
    {
        ans++;
        n=n/2;
    }
    return ans;
}
void DLR(int i)//
{
    if(tree[i]!=0)
    {
        cout<<tree[i]<<" ";
        DLR(i*2);
        DLR(i*2+1);
    }
}
void LDR(int i)//中序遍历
{
    if(tree[i]!=0)
    {
        
        DLR(i*2);
        cout<<tree[i]<<" ";
        DLR(i*2+1);
    }
}
void LRD(int i)//后序遍历
{
    if(tree[i]!=0)
    {

        DLR(i*2);
        DLR(i*2+1);
        cout<<tree[i]<<" ";
    }
}
int main()
{
    int n;
    cin>>n;
    int node_num=1;
    for(int j=0;j<n;j++ )//计数是第几组
    {

        int node;
        cin>>node;
        tree[1]=node;
        int i=1;
        if(node==0||node==-1)continue;
        while(judge==1)
        {
            cin>> node;
            //cout<<"node:  "<<node<<endl;
            ++i;
            //cout<<"i: "<<i<<endl;
            if(node==-1)//实现了深度搞定，接下来是前序遍历
            {
                cout<<real_depth(i-1) <<" ";
                break;
            }
            else
            {
                if(tree[i/2]!=0)
                {
                    tree[i]=node;
                }
                if(tree[i/2]==0)
                {
                    while(tree[i/2]==0)i=i/2;//回退到上层节点是有数字
                    i=i/2;
                    //cout<<"back: "<<i<<endl;
                    while(tree[i*2])i=i*2;
                    i=i*2;
                    //cout<<"go: "<<i<<endl;
                    tree[i]=node;
                }
            }
            node_num=i;
        }
        DLR(1);//完全二叉树记得要从节点1开始，也就是初始的节点
       cout<<endl;
       for(int i=1;i<=node_num;i++)
       {
           tree[i]=0;//清零
       }
    }
}

树的恢复

(105条消息) 先序遍历中序遍历还原二叉树_May Hacker的博客-CSDN博客_先序遍历中序遍历还原树

由先序和中序恢复二叉树

理论基础：

105. 从前序与中序遍历序列构造二叉树 - 力扣（Leetcode）

背也要背会的模板:

[(105条消息) 根据先序中序还原二叉树_BugMaker-shen的博客-CSDN博客_由先序和中序恢复二叉树](https://blog.csdn.net/qq_42500831/article/details/105984986?ops_request_misc=&request_id=&biz_id=102&utm_term=先序 + 中序 恢复二叉树&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-0-105984986.142^v63^control,201^v3^control_1,213^v2^t3_control1&spm=1018.2226.3001.4187)

原理：使用递归

image

🙏🙏🙏🙏🙏🙏🙏🙏🙏感谢这位西电的朋友助我脱离苦海，感谢感谢

可以直接用那种：😭😭😭😭（数据结构放假是机考！机考！机考！我giao！！！）

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
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Node{
    char data;
    Node* left;
    Node* right;
    Node(char data){
        this->data = data;
        this->left = nullptr;
        this->right = nullptr;
    }
};

vector<char> getCharArray(string str){
    //这一步就是为了利用vector有现成的构造函数，能省很多步骤
    vector<char> res;
    for(char c : str){
        //
        /*
        这里的for(char c:str)就是定义一个遍历字符c，让它分别等于字符串数组str里面的各个字符，然后执行下面的语句，当c被赋值为str里面所有字符各一次后，就会退出这个循环。

这相当于JAVA的强for循环的语法结构。相当于C++的：
for( int i = 0; i < s.length(); i++)
{ s[i]…
}
        */
        res.push_back(c);
    }
    return res;
}

Node* getTree(vector<char>& preOrder, vector<char>& inOrder){
    if(preOrder.empty()){
        return nullptr;
    }
    Node* root = new Node(preOrder[0]);
    //构造根结点，并且将root指针指向前序的第一个节点，即总根节点
    vector<char>::iterator mid = find(inOrder.begin(), inOrder.end(), preOrder[0]);//遍历一次找到前序在
    int left_nodes = mid - inOrder.begin();//接下来进行分区处理
    vector<char> left_inOrder(inOrder.begin(), mid);//中序的左子树
    //这里直接用了vector的构造，将inOrder赋值过去，最后一个mid不会复制
    vector<char> right_inOrder(mid+1, inOrder.end());//中序的右子树
    vector<char> left_preOrder(preOrder.begin()+1, preOrder.begin()+1+left_nodes);//前序的左子树，就省去根节点了
    vector<char> right_preOrder(preOrder.begin()+1+left_nodes, preOrder.end());//前序右子树
    root->left = getTree(left_preOrder, left_inOrder);//新树的左子树
    root->right = getTree(right_preOrder, right_inOrder);//新树右子树
    return root;//返回一个节点指针
}

void postOrder(Node* root){//后续遍历
    if(root == nullptr){
        return ;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->data;
}

int main(){
    string pre_str;
    string in_str;
    while(cin >> pre_str >> in_str){
        vector<char> preOrder = getCharArray(pre_str);//string转换成vector向量形式
        vector<char> inOrder = getCharArray(in_str);//
        Node* root = getTree(preOrder, inOrder);
        postOrder(root);
        cout<<endl;
    }
    return 0;
}


LeetCode解法：

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
class Solution {
private:
        TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return NULL;

        int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
        TreeNode* root = new TreeNode(rootValue);

        if (preorderEnd - preorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割前序数组
        // 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
        // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
        int rightPreorderEnd = preorderEnd;

        cout << "----------" << endl;
        cout << "leftInorder :";
        for (int i = leftInorderBegin; i < leftInorderEnd; i++) {
            cout << inorder[i] << " ";
        }
        cout << endl;

        cout << "rightInorder :";
        for (int i = rightInorderBegin; i < rightInorderEnd; i++) {
            cout << inorder[i] << " ";
        }
        cout << endl;

        cout << "leftPreorder :";
        for (int i = leftPreorderBegin; i < leftPreorderEnd; i++) {
            cout << preorder[i] << " ";
        }
        cout << endl;

        cout << "rightPreorder :";
        for (int i = rightPreorderBegin; i < rightPreorderEnd; i++) {
            cout << preorder[i] << " ";
        }
        cout << endl;


        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0 || preorder.size() == 0) return NULL;
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());

    }
};

并查集——面试涉及——竞赛频率也高😍

面试官一般都习惯去问一些代码短但是思路精巧的（便于手写代码）

提前学习知识：链表，线性表

全名：归并查找集合，即判断两个元素是否属于同一个集合

836. 合并集合 - AcWing题库

可选方法：

  • 建两个哈希表分别找
  • 建两个跳表分别找

在集合经常动态变化时候，查找方法效率并不高

并查集应用：

快速处理下列问题：

  1. 将两个集合合并
  2. 询问两个元素是否属于同一个集合中

并查集能在近乎O（1）的时间复杂度之内快速支持以上两种操作

正常：合并元素方式，至少需要对线性表/链表整个进行一次遍历，耗时高

基本原理：

每一个集合使用一棵树来维护（不一定是二叉树，可能是三叉树，B+树等），每一个集合的编号就是根节点的编号，树中对于每一个点都存储其父节点（用p[x]表示x的父节点），在求某个元素是否属于某一个集合的时候，就在该元素向上遍历，知道到达根节点，最后判断根节点的编号是否是所需编号

解决问题与流程：

  1. 如何判断树根，

    1
    if(p[x]==x)//对于树根编号等于自身

  2. 如何求x的集合编号:

    1
    2
    while(p[x]!=x)x=p[x]//多么熟悉的链表的遍历操作，因此是链表实现
        //这一步实际上的时间复杂度会高，因为还是会向上进行一个遍历，时间和树的高度有关，因此树最好高度越低越好

  3. 如何合并两个集合：加一条边，将一个树插入到另一棵树身上就可以

    image 
    1
    2
    //假设p[x]是x集合编号，p[y]是y的集合编号，那么只需要
    p[x]=y
写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int find(int x)//核心的函数
    //加上路径压缩，会自动找到根节点
{
    //if(p[x]!=x)x=p[x];
    if(p[x]!=x)p[x]=find(p[x]);
    //易错：p[x]=find(p[x])这里要更新的
    //易错：这里是if不能是循环while
    
    
    /*
    上面两句分别是普通版本和加过路径优化的版本
    第一个就是普通循环进行查找
    第二局是调用递归，每一次在寻找的时候都会对当前的节点进行更新，初次执行会慢，之后速度会飞升
    */
    return p[x];//最后返回一个根节点
}
void merge(int x,int y)
{
        p[x]=y;//核心函数二：合并     
}

全代码：

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
#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    /*
    经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
    p[x]=x;
    */
    return p[x];
    //找到了便返回祖宗节点的值
}
void merge(int x ,int y)//这里是把x的头并到y了
{
    p[find(x)]=find(y);//这里进行操作使用上一步的find函数
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op=='M') merge(a,b);//集合合并操作
        else
        if(find(a)==find(b))
        //如果祖宗节点一样,就输出yes
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

并查集优化：路径压缩

并查集最牛逼的优化方式，另一种优化基本写代码时候不会使用

原理：一旦在向上走的时候找到了根节点，将该路径所有节点都指向根节点，即只需要搜索一次，之后的重复操作速度就会提高，可以视为O（1）优化

优化：加权合并

防止树越来越高

记录每棵树元素的个数作为树的权重

堆：完全二叉树的操作

应用：

  • 构造优先队列

（不用stl）手搓一个堆，堆的基本

  • 插入一个数
  • 求这个集合当中的最小值
  • 删除最小值
  • 删除任意一个元素（stl无法直接实现）
  • 修改任意一个元素（stl无法直接实现）
堆的基本结构：

堆属于一棵完全二叉树（指除了最后一排其他都是均匀分布，即所有节点都不是非空），最后一层节点从左到右依次排列

小根堆的性质：每一个点都是小于等于左右儿子（即递归定义），则根节点就是最小值

大根堆：相反

凡是完全二叉树都是用一维数组存储的

1号点是根节点

x的左儿子下标：2x,

x的右儿子下标：2x+1

stl里面的堆就是优先队列

特点：

  • 时间复杂度非常稳定，不依赖原始记录状态
  • 是一种不稳定的排序方法（记录比较与交换跳跃进行）
基本函数：

down(x)：如果某一个点的值变大，就将该值向下压

up(x)：如果一个点的值变小，向上升

两个函数的执行次数都和二叉树的深度成正比，也就是logn

这里的x实际上是所处的位置

由基本函数构成堆的几种操作：

  1. 插入一个数
1
2
heap[++size]=x;//这一步将堆数组的最后再一个换成需要的数
up(size);
  1. 求最小值
1
heap[1];//是小根堆，则就最上面的就是最小的
  1. 删除最小值(也就是最顶部的根节点的删除)

思路：用堆底部的最后一个元素覆盖掉第一个元素，然后进行down（1)

原理：存储结构是一个一维数组，删除尾部节点很容易（直接size–就行），但删除头部却很麻烦

覆盖掉之后再使用向下函数down会让顶部元素下沉到正确位置

1
2
3
heap[1]=heap[size];
size--;
down(1);
  1. 删除任意一个元素,和删除头部不太一样在于不确定改变值之后是大还是小

简单粗暴好使的办法：管他呢，down一次，up一次，因为up和down实际上只会执行一次

1
2
3
4
heap[k]=heap[size];
size--;//
down(k);
up(k);
  1. 修改任意一个元素的值：同删除一个元素的操作
1
2
3
heap[k]=x;
down(k);
up(k);
构建小细节：

不同于其它的一般采用下标从0开始，对于树形结构，因为树的性质有左儿子=根/2，如果从0开始左儿子也是0，不方便，因此堆排序实际上是从1开始

开始构建：
构建堆

可以用插入的方式操作，但每一次插入都是logn，实际上不好

有时间复杂度为on的方式

1
for(int i=size/2,i>0;i--)down(i);
构建up

妙啊（发出抱大佬大腿的声音）😍

1
2
3
4
5
6
7
8
void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])//不管u是左右儿子，都不重要，直接/2指向的双亲都是同一个
    {
        swap(u, u / 2);
        u >>= 1;//u变成原先的二分之一
    }
}
构建down
1
2
3
4
5
6
7
8
9
10
11
12
13
void down(int u)
{
    int t=u;
    if(u*2<=size&&h[u*2]<h[t])t=u*2;//先判断有没有左儿子，然后判断左儿子小
    if(u*2+1<=size&&h[u*2+1]<=h[t])t=u*2+1;//判断右儿子和大小
    //最后t存的就是根，左右儿子三者之中最小的值下标
    if(u!=t)//不等，说明有可能还要继续递归进行对比
    {
        swap(h[u],h[t]);
        down(t);//递归向下继续弄
    }
    
}
模拟堆

难点：支持随机的修改和删除,题中要求是第i个，但是i对应的下标会随着操作变化下标跟着变化，需要实时更新。因此映射也要交换好

解法：使用映射,老牛逼了

image 
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
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
//ph从左到右，hp从右到左、
//交换数的时候，指针也要交换
// 交换两个点，及其映射关系
void heap_swap(int a, int b)//针对这一道题开发的映射关系转换
{
    swap(ph[hp[a]],ph[hp[b]]);//指针交换
    swap(hp[a], hp[b]);//逆指针交换
    swap(h[a], h[b]);//数值交换
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
解题技巧：

当题中有明确给出第i个操作数，要考虑如何通过更新操作数的下标

image
堆排序：onlogn

一般升序使用大顶堆，降序采用小顶堆

举例：对数组进行从小到大排序，输出前m小的数

思路：本题可以使用堆排序，构造小顶堆，然后输出堆顶，输出后把堆顶和堆尾交换。尾部边界缩小，重复执行m次即可。

注意点：

  • 和完全二叉树一样下标从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
#include <iostream>
using namespace  std;
const int M=100100;
int h[M];
int size;
void big_down(int u)//最后大的会向下走
{
    int t=u;
    if(u*2<=size&&h[u*2]<h[t])t=u*2;//先判断有没有左儿子，然后判断左儿子小
    if(u*2+1<=size&&h[u*2+1]<=h[t])t=u*2+1;//判断右儿子和大小
    //最后t存的就是根，左右儿子三者之中最小的值下标
    if(u!=t)//不等，说明有可能还要继续递归进行对比
    {
        swap(h[u],h[t]);
        big_down(t);//递归向下继续弄
    }
}
void small_down(int u)//最后小的会向下走
{
    int t=u;
    if(u*2<=size&&h[u*2]>h[t])t=u*2;//先判断有没有左儿子，然后判断左儿子小
    if(u*2+1<=size&&h[u*2+1]>=h[t])t=u*2+1;//判断右儿子和大小
    //最后t存的就是根，左右儿子三者之中最小的值下标
    if(u!=t)//不等，说明有可能还要继续递归进行对比
    {
        swap(h[u],h[t]);
        small_down(t);//递归向下继续弄
        注意这里向下的还是t
    }
}
int main()
{

    cin>>size;
    for(int i=1;i<=size;i++)//二叉树的读入范围
    {
        cin>>h[i];
    }
    for (int i = size / 2; i; i -- ) small_down(i);
    for(int i=1;i<=size;i++)cout<<h[i]<<' ';
    cout<<endl;
    for (int i = size / 2; i; i -- ) big_down(i);
    for(int i=1;i<=size;i++)cout<<h[i]<<' ';
    cout<<endl;

    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
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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];//保存数组
int n, m;//n个点，求前m小
int r ;//堆的右边界
void down(int u)//调整函数
{
    //t记录最小点的编号
    int t = u;

易错部分：这里前面都是u最后对比是t，修改大小也是修改u
    if(2 * u <= r && a[2 * u] < a[t]) t = 2 * u;

    if(2 * u + 1 <= r && a[2 * u + 1] < a[t]) t = 2 * u + 1;

    //如果待调整点不是最小的
    if(u != t)
    {
        //和最小的交换
        swap(a[u], a[t]);

        //递归处理
        down(t);
    }
}


因为堆是一棵二叉树构建起来的，因此是从1
int main()
{
    cin >> n >> m;
    r = n;//开始时，右边界是数组边界

    //读入数据
    for (int i = 1; i <= n; i ++ )
    {
        int x;
        cin >> a[i];
    }

    //从第一个非叶节点开始，从右到左，从下到上处理每个节点
   for(int i = n /2 ; i ; i--)//创建小根堆
   {
       //注意问题在于它小得没有规律
       down(i);//因为叶子节点没办法继续向下了，因此从叶子向上一层开始操作
   }

    //输出m个最小值
    while (m -- )
    {
        //堆顶保存的最小值，输出堆顶
        cout << a[1] << " ";

        //将堆顶和右边界交换
        swap(a[1], a[r]);

        //右边界左移
        r--;

        //从新处理堆顶
        down(1);
    }
}

哈夫曼树

下面这个关于编码的，很重要

(108条消息) 【数据结构——哈夫曼树及其应用】_FEI..的博客-CSDN博客_哈夫曼树的parent怎么求

哈夫曼编码:字母

核心：无前缀编码，从根节点到叶子节点的路径代表编码，只要字母在叶子节点，对应编码就是无前缀

贪心算法
  • 从底向上建立一棵无前缀编码树
  • 频次低的树在最下面
自己写的代码(输入字符串进行编码并输出)：
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
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
typedef struct
{
    int weight;//结点的权值
    int parent, lchild, rchild;//双亲、左孩子、右孩子的下标
}HTnode,*HuffmanTree;
void Select(HuffmanTree& HT,int &s1,int &s2,int n)
{
    s2=1,s1=2;//两个过大的数进行比对
    for (int i = 1;i <= n;++s1)//在1到n之间的点进行寻找
    {
        if(HT[s1].parent==0&&HT[s2].parent==0)//当
        {
            break;
        }
        if(HT[s1].parent==0)//当
        {
            s2=s1;
        }
        if(s2==s1)++s1;
    }
    for (int i = 1;i <= n;++i)//在1到n之间的点进行寻找
    {
        if(HT[i].weight<=HT[s1].weight&&HT[i].parent==0)//当
        {
            s1=i;//连着更新两次，s1是最小的，s2是次小的
        }
    }
    for (int i = 1;i <= n;++i)//在1到n之间的点进行寻找
    {
        if(HT[i].weight<=HT[s2].weight&&HT[i].parent==0&&i!=s1)//当
        {
            s2=i;
        }
    }
}
void CreateHuffmanTree(HuffmanTree& HT, int n,int word[])//构造哈夫曼树，n为带权值的叶子结点个数
{
    //使用了以获取的word数组存取已有的数量
    /*初始化*/
    int s1,s2;
    if (n <= 1)
        return;
    int m = 2 * n - 1;//m为哈夫曼树中总结点的个数
    HT = new HTnode[m + 1];//0号单元未用，所以需要开辟m+1个单元，HT[m]表示根结点
    for (int i = 1;i <= m;++i)//将1-m号单元的双亲，左右孩子的下标都初始化为0
    {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    int word_select=0;
    for (int i = 1;i <= n;++i)
    {
        for(;word[word_select]==0;word_select++);
//        cout<<(char)word_select <<" word="<<word[word_select]<<endl;
        HT[i].weight=word[word_select];//输入前n个单元中叶子结点的权值
//        cout<<i<<"个单元叶子节点的权值： "<<HT[i].weight<<endl;
//这一句是输入测试，ok了
        word_select++;//到下一个防止连续搞
    }//到这一步都没问题，叶子节点权值都录入了
    /*初始化工作结束，下面开始创建哈夫曼树*/
//    cout<<"n=:"<<n<<endl;
    for (int i = n + 1;i <= m;++i)
    {//通过n-1次的选择、删除、合并来创建哈夫曼树
        Select(HT,  s1, s2,n);//选择两个其双亲域为0且权值最小的结点
//        cout<<i-15<<"次操作之后 " <<"s1 now="<<s1<<" HT[s1].weight="<<HT[s1].weight;
//        cout<<"  s2 now ="<<s2<<" HT[s2].weight="<<HT[s2].weight<<endl;
        HT[s1].parent = i;HT[s2].parent = i;//得到新结点i,将s1\s2的双亲域由0改为i
        HT[i].lchild = s1;HT[i].rchild = s2;//s1、s2分别作为i的左右孩子
        HT[i].weight = HT[s1].weight + HT[s2].weight;//i的权值为左右孩子的权值之和
//        cout<<"  HT now ="<<i<<" HT[i].weight="<<HT[i].weight<<endl;
    }
}
typedef char** HuffmanCode;
////动态分配数组存储哈夫曼编码表
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)//完全没有开始写的
{//从叶子到根逆向求每个字符的哈夫曼编码，储存在编码表HC中
    HC = new char* [n + 1];//分配n个字符编码的头指针矢量
     char *cd = new char[n];//分配临时存放编码的动态数组空间
     int start;
     int c;
     int f;
    cd[n - 1] = '\0';//编码结束符
    for (int i = 1;i <= n;++i)//逐个字符求哈夫曼编码
    {
        start = n - 1;//start开始时指向最后，即编码结束符的位置
        c = i;f = HT[i].parent;//f指向结点c的双亲结点
        while (f != 0)//从叶子结点开始向上回溯，直到根结点
        {
            --start;//回溯一次，start向前指一个位置
            if (HT[f].lchild == c)
                cd[start] = '0';//结点c是f的左孩子，则生成代码0
            else
                cd[start] = '1';//结点c是f的右孩子，则生成代码1
            c = f;f = HT[f].parent;//继续向上回溯
        }//求出第i个字符的编码
        HC[i] = new char[n - start];//为敌i个字符编码分配空间
        strcpy(HC[i], &cd[start]);//将求得的编码从临时空间cd复制到HC当前行中
    }
    delete cd;//释放临时空间
}
char out[128]={'\0'};
int word[128]={0};//作为字母
int main() {
    string ans="";
    string temp;
    while (getline(cin, temp)) {
        if (temp == "0") {
            break;
        }
        ans+=temp;
    }//读入阶段
    int length=ans.size();
    for(int i=0;i<length;i++)
    {
        int idx=(int)(ans[i]);
        word[idx]++;
    }
    int node_num=0;
    for(int i=1;i<=128;i++)
    {
        if(word[i]!=0)
        {
            ++node_num;
            out[node_num]=(char)i;
//            cout <<(char)i << ": "<< word[i] << endl;
            //这里获得了对应的编码
        }
    }
    HuffmanTree HT;
    CreateHuffmanTree(HT,node_num,word);
    HuffmanCode HC;
    CreatHuffmanCode(HT,HC,node_num);
    for(int i=1;i<=node_num;i++)
    {
        cout<<out[i]<<":"<<HC[i]<<endl;
    }
    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
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
// C++ program for Huffman Coding
#include <iostream>
#include <cstdlib>
using namespace std;

// This constant can be avoided by explicitly
// calculating height of Huffman Tree
#define MAX_TREE_HT 100

// A Huffman tree node
struct MinHeapNode {

	// One of the input characters
	char data;

	// Frequency of the character
	unsigned freq;

	// Left and right child of this node
	struct MinHeapNode *left, *right;
};

// A Min Heap: Collection of
// min-heap (or Huffman tree) nodes
struct MinHeap {

	// Current size of min heap
	unsigned size;

	// capacity of min heap
	unsigned capacity;

	// Array of minheap node pointers
	struct MinHeapNode** array;
};

// A utility function allocate a new
// min heap node with given character
// and frequency of the character
struct MinHeapNode* newNode(char data, unsigned freq)
{
	struct MinHeapNode* temp
		= (struct MinHeapNode*)malloc
(sizeof(struct MinHeapNode));

	temp->left = temp->right = NULL;
	temp->data = data;
	temp->freq = freq;

	return temp;
}

// A utility function to create
// a min heap of given capacity
struct MinHeap* createMinHeap(unsigned capacity)

{

	struct MinHeap* minHeap
		= (struct MinHeap*)malloc(sizeof(struct MinHeap));

	// current size is 0
	minHeap->size = 0;

	minHeap->capacity = capacity;

	minHeap->array
		= (struct MinHeapNode**)malloc(minHeap->
capacity * sizeof(struct MinHeapNode*));
	return minHeap;
}

// A utility function to
// swap two min heap nodes
void swapMinHeapNode(struct MinHeapNode** a,
					struct MinHeapNode** b)

{

	struct MinHeapNode* t = *a;
	*a = *b;
	*b = t;
}

// The standard minHeapify function.
void minHeapify(struct MinHeap* minHeap, int idx)

{

	int smallest = idx;
	int left = 2 * idx + 1;
	int right = 2 * idx + 2;

	if (left < minHeap->size && minHeap->array[left]->
freq < minHeap->array[smallest]->freq)
		smallest = left;

	if (right < minHeap->size && minHeap->array[right]->
freq < minHeap->array[smallest]->freq)
		smallest = right;

	if (smallest != idx) {
		swapMinHeapNode(&minHeap->array[smallest],
						&minHeap->array[idx]);
		minHeapify(minHeap, smallest);
	}
}

// A utility function to check
// if size of heap is 1 or not
int isSizeOne(struct MinHeap* minHeap)
{

	return (minHeap->size == 1);
}

// A standard function to extract
// minimum value node from heap
struct MinHeapNode* extractMin(struct MinHeap* minHeap)

{

	struct MinHeapNode* temp = minHeap->array[0];
	minHeap->array[0]
		= minHeap->array[minHeap->size - 1];

	--minHeap->size;
	minHeapify(minHeap, 0);

	return temp;
}

// A utility function to insert
// a new node to Min Heap
void insertMinHeap(struct MinHeap* minHeap,
				struct MinHeapNode* minHeapNode)

{

	++minHeap->size;
	int i = minHeap->size - 1;

	while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {

		minHeap->array[i] = minHeap->array[(i - 1) / 2];
		i = (i - 1) / 2;
	}

	minHeap->array[i] = minHeapNode;
}

// A standard function to build min heap
void buildMinHeap(struct MinHeap* minHeap)

{

	int n = minHeap->size - 1;
	int i;

	for (i = (n - 1) / 2; i >= 0; --i)
		minHeapify(minHeap, i);
}

// A utility function to print an array of size n
void printArr(int arr[], int n)
{
	int i;
	for (i = 0; i < n; ++i)
		cout<< arr[i];

	cout<<"\n";
}

// Utility function to check if this node is leaf
int isLeaf(struct MinHeapNode* root)

{

	return !(root->left) && !(root->right);
}

// Creates a min heap of capacity
// equal to size and inserts all character of
// data[] in min heap. Initially size of
// min heap is equal to capacity
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size)

{

	struct MinHeap* minHeap = createMinHeap(size);

	for (int i = 0; i < size; ++i)
		minHeap->array[i] = newNode(data[i], freq[i]);

	minHeap->size = size;
	buildMinHeap(minHeap);

	return minHeap;
}

// The main function that builds Huffman tree
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)

{
	struct MinHeapNode *left, *right, *top;

	// Step 1: Create a min heap of capacity
	// equal to size. Initially, there are
	// modes equal to size.
	struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);

	// Iterate while size of heap doesn't become 1
	while (!isSizeOne(minHeap)) {

		// Step 2: Extract the two minimum
		// freq items from min heap
		left = extractMin(minHeap);
		right = extractMin(minHeap);

		// Step 3: Create a new internal
		// node with frequency equal to the
		// sum of the two nodes frequencies.
		// Make the two extracted node as
		// left and right children of this new node.
		// Add this node to the min heap
		// '$' is a special value for internal nodes, not used
		top = newNode('$', left->freq + right->freq);

		top->left = left;
		top->right = right;

		insertMinHeap(minHeap, top);
	}

	// Step 4: The remaining node is the
	// root node and the tree is complete.
	return extractMin(minHeap);
}

// Prints huffman codes from the root of Huffman Tree.
// It uses arr[] to store codes
void printCodes(struct MinHeapNode* root, int arr[], int top)

{

	// Assign 0 to left edge and recur
	if (root->left) {

		arr[top] = 0;
		printCodes(root->left, arr, top + 1);
	}

	// Assign 1 to right edge and recur
	if (root->right) {

		arr[top] = 1;
		printCodes(root->right, arr, top + 1);
	}

	// If this is a leaf node, then
	// it contains one of the input
	// characters, print the character
	// and its code from arr[]
	if (isLeaf(root)) {

		cout<< root->data <<": ";
		printArr(arr, top);
	}
}

// The main function that builds a
// Huffman Tree and print codes by traversing
// the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)

{
	// Construct Huffman Tree
	struct MinHeapNode* root
		= buildHuffmanTree(data, freq, size);

	// Print Huffman codes using
	// the Huffman tree built above
	int arr[MAX_TREE_HT], top = 0;

	printCodes(root, arr, top);
}

// Driver code
int main()
{

	char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
	int freq[] = { 5, 9, 12, 13, 16, 45 };

	int size = sizeof(arr) / sizeof(arr[0]);

	HuffmanCodes(arr, freq, size);

	return 0;
}
/*
结果输出：
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
*/

AVL树

平衡二叉树：

(110条消息) AVL树的详细实现(C++)_code_peak的博客-CSDN博客_c++实现avl树

avl树的各种延申应用：伸展树，B树，字典树

  1. 1. 数据结构与算法：PART1
    1. 1.0.1. 算法时间分析：
    2. 1.0.2. 理解idx:
      1. 1.0.2.0.0.1. 科班学习顺序：（如何逐步提高写程序的性能）
      2. 1.0.2.0.0.2. 提高程序性能办法：
      3. 1.0.2.0.0.3. 程序运行时间因素
      4. 1.0.2.0.0.4. 冯诺依曼架构
      5. 1.0.2.0.0.5. 空间复杂度：
  • 1.0.3. 基础算法
    1. 1.0.3.0.1. 位运算
  • 1.0.3.1. 快排——》重要，面试常用型😍
    1. 1.0.3.1.0.1. 模板：
    2. 1.0.3.1.0.2. 快排合理性分析：AcWing 785. 快速排序算法的证明与边界分析 - AcWing
  • 1.0.3.1.1. 单向移动版本快排（实际使用快慢指针）
    1. 1.0.3.1.1.1.
  • 1.0.3.2. 插入排序
  • 1.0.3.3. plus:折半插入排序（插入+二分）——》稳定又好使
    1. 1.0.3.3.0.1. 代码：
  • 1.0.3.4. 希尔排序
    1. 1.0.3.4.0.1. 模板
  • 1.0.3.5. 归并排序（另一个重要排序，也背下来）😃
    1. 1.0.3.5.0.1. 模板：
    2. 1.0.3.5.0.2. 有趣应用：逆序对
  • 1.0.3.6. timsort（优化后归并）
    1. 1.0.3.6.0.1. 核心：提取降序数组升级为升序
    2. 1.0.3.6.0.2. 核心：栈处理归并
    3. 1.0.3.6.0.3. 核心：最小分区长度在排序之前预先计算
    4. 1.0.3.6.0.4. timsort模板（自己写的！）
  • 1.0.3.7. 二分
    1. 1.0.3.7.0.1. 整数模板（两种）
    2. 1.0.3.7.0.2. 整数经典例题：789. 数的范围 - AcWing题库
    3. 1.0.3.7.0.3. 519. 跳石头 - AcWing题库
    4. 1.0.3.7.0.4. 浮点模板
  • 1.0.3.7.1. 二分改进：
    1. 1.0.3.7.1.1. 插值查找
    2. 1.0.3.7.1.2. 关键不同：
    3. 1.0.3.7.1.3. 斐波那契查找
  • 1.0.3.8. 前缀和（应用广泛）
    1. 1.0.3.8.1. 前缀和+哈希表=LZW压缩->文本压缩
      1. 1.0.3.8.1.1. 压缩部分：
      2. 1.0.3.8.1.2. 解压缩部分：
  • 1.0.3.9. 离散化：整数离散化
    1. 1.0.3.9.0.1. 离散化模板：(c++版本)
  • 1.0.3.10. 区间合并：不同于离散化
    1. 1.0.3.10.0.1. 步骤：
    2. 1.0.3.10.0.2. 代码模板
  • 1.0.4. 数据结构
    1. 1.0.4.1. 链表
      1. 1.0.4.1.0.1. 前言：
      2. 1.0.4.1.0.2. 链表制造方式
      3. 1.0.4.1.0.3. 单链表制作
      4. 1.0.4.1.0.4. 双链表制作
      5. 1.0.4.1.0.5. 链表递归与双指针
      6. 1.0.4.1.0.6. 同样利用递归实现链表逆序：（有那么一点点费脑子）
      7. 1.0.4.1.0.7.
      8. 1.0.4.1.0.8. 双指针实现逆序
      9. 1.0.4.1.0.9. 有序链表的拼接（又是递归/bushi）
      10. 1.0.4.1.0.10. 回文链表判断：（映射，递归，翻转）
  • 1.0.4.2. zhan（栈）不是B站那个
    1. 1.0.4.2.0.1. 前言：
    2. 1.0.4.2.0.2. 栈制造方式
    3. 1.0.4.2.0.3. 栈做非降路径问题
    4. 1.0.4.2.0.4. 中缀表达式转换后缀表达式
    5. 1.0.4.2.0.5. 正则表达式分析
    6. 1.0.4.2.0.6. 正则表达式代码
    7. 1.0.4.2.0.7. 单调栈（瞳孔地震型题解）😢
  • 1.0.4.3. 队列
    1. 1.0.4.3.0.1. 队列构造方式：
    2. 1.0.4.3.0.2. 循环队列：
    3. 1.0.4.3.0.3. 单调队列~~~~~~~(～￣▽￣)～滑动窗口经典（配合单调栈食用）
  • 1.0.4.4. 串
    1. 1.0.4.4.1. KMP
      1. 1.0.4.4.1.1. 模板y总
      2. 1.0.4.4.1.2. 前缀表：字符串的最长
      3. 1.0.4.4.1.3. 代码随想录方法：前缀不减形式
      4. 1.0.4.4.1.4. 数据结构作业出错原因
    2. 1.0.4.4.2. automata~有限状态自动机
      1. 1.0.4.4.2.1. 代码（构建自动机状态表）
      2. 1.0.4.4.2.2. 聪明版本自动机
    3. 1.0.4.4.3. TRIE树（有些类似哈夫曼树编码）
      1. 1.0.4.4.3.1. 如何存储：构建串树
      2. 1.0.4.4.3.2. 如何查找
      3. 1.0.4.4.3.3. 构建TRIE树
    4. 1.0.4.4.4. TRIE树的其它应用
      1. 1.0.4.4.4.1. 思路：利用二叉树
      2. 1.0.4.4.4.2. 算法复杂度：
      3. 1.0.4.4.4.3. 代码：
  • 1.0.4.5. 跳表——同样面试——但是不用手搓
    1. 1.0.4.5.0.1. 一些参考的博客：
    2. 1.0.4.5.0.2. 特点：
    3. 1.0.4.5.0.3. 核心思想：
  • 1.0.4.5.1. 实现
    1. 1.0.4.5.1.1. 构建过程：
    2. 1.0.4.5.1.2. TRIE树的其它
  • 1.0.4.6. 散列表——哈希表-面试很重要
    1. 1.0.4.6.0.1. 线性表总结：
    2. 1.0.4.6.0.2. 哈希定义，应用
    3. 1.0.4.6.0.3. 哈希模板（正常+字符串版本）
    4. 1.0.4.6.0.4. 分配索引值
    5. 1.0.4.6.0.5. 减少索引值：
  • 1.0.4.6.1. 字符串哈希——>字符串前缀哈希法
  • 1.0.4.7. 哈希碰撞处理（面试高频）😍😍😍😍😍
    1. 1.0.4.7.0.1. 拉链法（Open Hashing）
    2. 1.0.4.7.0.2. 开放地址法 Open Addressing
  • 1.0.4.8. 杜鹃哈希😎
    1. 1.0.4.8.0.1. 失败时：
  • 1.0.4.9. 树
    1. 1.0.4.9.0.1. 完全二叉树的构建（0作为空节点，会有空间浪费）
  • 1.0.4.10. 树的恢复
    1. 1.0.4.10.1. 由先序和中序恢复二叉树
      1. 1.0.4.10.1.1. 背也要背会的模板:
  • 1.0.4.11. 并查集——面试涉及——竞赛频率也高😍
    1. 1.0.4.11.0.1. 并查集应用：
    2. 1.0.4.11.0.2. 基本原理：
    3. 1.0.4.11.0.3. 写法：
  • 1.0.4.11.1. 并查集优化：路径压缩
    1. 1.0.4.11.1.1. 优化：加权合并
  • 1.0.4.12. 堆：完全二叉树的操作
    1. 1.0.4.12.0.1. 堆的基本结构：
    2. 1.0.4.12.0.2. 基本函数：
    3. 1.0.4.12.0.3. 构建小细节：
  • 1.0.4.12.1. 开始构建：
    1. 1.0.4.12.1.1. 构建堆
    2. 1.0.4.12.1.2. 构建up
    3. 1.0.4.12.1.3. 构建down
  • 1.0.4.12.2. 模拟堆
    1. 1.0.4.12.2.1. 解题技巧：
  • 1.0.4.12.3. 堆排序：onlogn
  • 1.0.4.12.4. 代码：
    1. 1.0.4.12.4.1. 模拟堆（直接造小根堆）
    2. 1.0.4.12.4.2. 堆排序（整体）
  • 1.0.4.13. 哈夫曼树
    1. 1.0.4.13.1. 哈夫曼编码:字母
      1. 1.0.4.13.1.1. 贪心算法
      2. 1.0.4.13.1.2. 自己写的代码(输入字符串进行编码并输出)：
  • 1.0.4.14. AVL树