0%

发表于 更新于 分类于 Valine：

*1 你能在你最喜欢的那天吃到你最喜欢的糖果吗（Mid）

1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

解法：前缀和+区间交集

原理：

favoriteDay内吃糖的总数区间 X = [favoriteDay + 1， (favoriteDay + 1) * dailyCap]，即左边界为每天只吃一个，右边界为每天吃到最大

可以吃到favoriteType的区间 Y = [sum[favoriteType - 1] + 1, sum[favoriteType]]，即最少只吃到一个，最多吃到最后一个（吃完）

只要两区间有交集，总有吃法使得在favoriteDay当天吃到favoriteType类的糖。

边界情况：当favoriteType == 0时，Y的左边界为1，即只要吃一个糖就能吃到第0类

阅读全文 »

发表于 更新于 分类于 Valine：

28 汉明距离综合（Mid）

477. 汉明距离总和（Middle）

思路：用乘法法则，计算所有数字在每一位上的汉明距离差，再求总和

乘法法则：集合A有n种选择，集合B有m种选择，从A、B各选一个有nm种可能，在此处，因为在第i位上为1的数字和为0的数字汉明距离为1，因此组合后所有可能性即为第i位上的汉明距离数

阅读全文 »

发表于 更新于 Valine：

title: C++ Trick Methods

tags: C++

categories: C++

C++ Trick Methods

介绍c++中一些简化编码/提高效率/单纯有趣的函数

阅读全文 »

发表于 更新于 分类于 Valine：

lambda表达式

参考：http://c.biancheng.net/view/3741.html

背景

lambda 表达式是 C++11 最重要也最常用的一个特性之一，C# 3.5 和 Java 8 中就引入了 lambda 表达式。

lambda表达式有如下优点：

  • 声明式编程风格：就地匿名定义目标函数或函数对象，不需要额外写一个命名函数或者函数对象。以更直接的方式去写程序，好的可读性和可维护性。
  • 简洁：不需要额外再写一个函数或者函数对象，避免了代码膨胀和功能分散，让开发者更加集中精力在手边的问题，同时也获取了更高的生产率。
  • 在需要的时间和地点实现功能闭包，使程序更灵活。
阅读全文 »

发表于 更新于 分类于 Valine：

[TOC]

0 起步

基本数据类型：变量，强制转换，符号常量（define），const

顺序结构：赋值，scanf/printf，getchar/putchar，typedef，math函数

  • 区分double型的scanf和printf
    image-20210309090058765

    image-20210309090139568

  • 常用math函数

    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
    #include <math.h>

    // 规范
    double fabs(double x);	// 取绝对值
    double round(double x);	// 四舍五入，返回的double需用(int)取整
    double floor(double x);	// 向下取整
    double ceil(double x);	// 向上取整
    // 以上两个函数对负数也有效，如floor(-5.2) = -6

    // 计算
    double pow(double r, double p);	// 返回r^p
    double sqrt(double x);	// 返回x的算术平方根
    double log(double x);	// 返回以e为底的对数
    // 换底公式处理任何底的对数: log_a(b) = log(b) / log(a)

    // 三角函数
    double sin(double x); 
    double cos(double x); 
    double tan(double x);	
    // 参数要求弧度制 如1/3 * pi

    // 反三角函数
    double asin(double x);
    double acos(double x);
    double atan(double x);

选择结构：if，switch

循环结构：while，do while，for，break/continue

数组：memset，字符数组，string.h头文件，

1
2
#include <cstring>
memset(数组名, 值, sizeof(数组名));	// 值只能0或-1，因为是按字节赋值

sscanf/sprintf（字符串格式转换）

1
2
3
4
5
6
7
8
9
10
11
// 将数据输入到字符串
int n = 12345;
char str[6];
sprintf(str, "%d", n);
// 执行后str为"12345"

// 从字符串中提取输入
char str[6] = "12345";
int n;
sscanf(str, "%d", &n);
// 执行后n = 12345

函数：嵌套、递归

指针：指针与数组、引用&

  • 引用不产生副本，而是给原变量起别名
  • 指针引用（如int* &r），在需要改指针存储的unsigned int型地址本身时使用

结构体：访问元素./->，构造函数

输入字符串汇总：

1
2
3
4
5
6
7
8
9
10
11
12
13
char str[MAXN];

scanf("%s", str);		// scanf读入一个char[]

while((str[i]=getchar())!='\n')		// getchar读入一行char[]
    i++;

gets(str);	// gets读入一行char[]

cin.getline(str, MAXN);	// cin读入一行char[], 读取直到遇到\n为止

string str2;
getline(cin, str2);	// cin读入一行string

文件输入

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
#include <stdio.h>
// 打开文件，如果没有则新建
char fileName[10] = "tmp.txt";
char mode[3] = "r+";	// r只读，w只写，r+可读可写
FILE *fp = fopen(filename, mode);

// 文件关闭
int fclose( FILE *fp );	// 错误返回EOF

// 文件读
// fgetc
while ((c = fgetc(fp)) != EOF)		// 返回读取的字符
    ...
//fgets
char buff[maxn];
while (fgets(buf, maxn, fp))	 // 读一行存进buf，也可以用char*接收返回值
    ...
// fscanf
int n;
while (fscanf(fp, "%d", &n) != EOF)	// 注意结合sscanf理解“流”
    ...

// 文件写
fputc( int c, fp);
fputs(str, fp);		// 末尾无\n，puts有
fprintf(fp, "%s", str);

// 其他
rewind(fp);		// 文件指向开头
int fseek(FILE *stream, long int offset, int whence);	// 文件指针移动
// whence可以是：SEEK_SET开头，SEEK_CUR当前，SEEK_END末尾

C语言字符判断函数

1
2
3
4
5
6
7
8
9
10
11
12
#include <ctype.h>

isalpha(c);	// 是否为字母
isdigit(c);	// 是否为数字
isalnum(c);	// 是否为英文或数字
isupper(c);	// 是否为大写
islower(c);	// 是否为小写

// 是否为分割文本的空白符（空格' '和水平制表符'\t'）
isblank(c);	
// 是否为空白符（' '、水平制表符'\t'、换行符'\n'、垂直制表符'\v'、换页'\f'以及回车'\r'。）
isspace(c);

1 算法初步

1.1 排序

c++ sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>
using namespace std;

sort([首元素地址], [尾元素的下一个地址], [比较函数cmp(非必填)]);	// 默认升序
// 简单cmp函数
// bool cmp(e1, e2)
// {
// 		return e1 < e2; // 小元素在前、升序
// }

// 使用lambda表达式写cmp
// 对索引数组indices排序
sort(indices.begin(), indices.end(), [&](int i, int j){
    return tasks[i][0] < tasks[j][0];   
});

c qsort

1
2
3
4
5
6
7
8
#include <stdlib.h>

int cmpfunc (const void * a, const void * b)
{
   return ( *([类型]*)a - *([类型]*)b );
}

qsort([数组], n, sizeof([类型]), cmp);

写cmp函数的原则：

  • 希望元素按什么顺序排列，就直接按照大小次序返回即可；

1.2 递归

典例：全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// dfs(0)
void dfs(int index)
{
	// 递归边界
    if (index == n - 1)
	{
		for (int i = 0; i < n; i++)
		{
			printf("%d", a[i]);
		}
		putchar('\n');
	}
	
    // 递归式
	for (int i = 1; i <= n; i++)
	{
		if (!flag[i])
		{
			a[index] = i;	// 常用技巧: 用层数做数组下标记录结果
			vis[i] = true;
			dfs(index + 1);
			vis[i] = false;
		}
	}
}

n皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 核心思想：排列 + 判断方案是否合法

void dfs(int index)
{
	if (index == n)
	{
		// 方案数
        cnt++;
        // 打印方案
		for (int i = 0; i < n; i++)
		{
			printf("%d", ans[i]);
			(i == n - 1)? putchar('\n') : putchar(' ');
		}
		return;
	}
	
	for (int i = 1; i <= n; i++)	// 枚举待选择的位置：index下标放入i 
	{
		if (!vis[i])
		{
			bool flag = true;
			for (int pre = 0; pre < index; pre++)	// 枚举已有的位置 
			{
				// 如果在对角线上
                if (abs(index - pre) == abs(i - ans[pre]))
				{
					flag = false;
					break;
				}
			}
			// 若这种方案目前合法 
			if (flag)	
			{
				vis[i] = true;
				ans[index] = i;
				dfs(index + 1);
				vis[i] = false;
			}
		}
	}	
}

1.3 贪心

局部最优推得全局最优

  • 简单贪心：分布背包
  • 区间贪心
    • 活动选择、区间选点问题

1.4二分

  • 查找序列是否存在满足条件的元素（常规二分

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 严格递增序列
    int solve(int left, int right, int x)
    {
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (A[mid] == x)	return mid
            else if (A[mid] > x) right = mid - 1;
            else	left = mid + 1;		// A[mid] < x
        }
        return -1;	// 查找失败
    }

  • 查找序列第一个满足条件的元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // 序列从左到右先不满足，后满足
    // 若存在，返回的是元素的位置
    // 若不存在，返回的是“假设存在，它应在的位置”
    int solve(int left, int right)
    {
        int mid;
        while (left < right)	// 此时才有区间
        {
            mid = (left + right) / 2;
            if (条件成立)	// 满足条件，则第一个满足的在[left, mid]之间
                right = mid		// 因为mid也满足，所以不是mid-1
            else
                left = mid + 1;
        }
        return left;	// left==right时退出循环
    }

    对于左开右闭的区间(left, right]，二分条件就是while ((left + 1 < right)

    对于左闭右开[left, right)，二分条件是while (left < right - 1)

  • 二分拓展

    • 计算单调函数f(x)=0的根（近似）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      const double eps = 1e-5

      // f(x)递增
      double f(double x)
      {
          return ...; // 函数值
      }
      double solve(double left, double right)
      {
          double mid;
          while (right - left > eps)
          {
              mid = (left + right) / 2;
              if (f(mid) > 0) 	// 若递减，把>改为<
                  right = mid;	// 往[left, mid]逼近
              else 
                  left = mid;		// 往[mid, right]逼近
          }
      }

    • 快速幂（求$a^b\%m$，O(logb)）

      递归写法

      1. 如果b是奇数（$b \& 1$），$a^b = a * a^{b - 1}$
      2. 如果b是偶数，$a^b = a^{b/2} * a^{b / 2}$
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      typedef long long LL;

      // O(logb)
      LL binaryPow(LL a, LL b, LL m)
      {
          if (b == 0) return 1;
          if (b & 1)	// 奇数
              return a * binaryPow(a, b - 1, m) % m;
          else
          {
              LL mul = binaryPow(a, b / 2, m);
              return mul * mul % m;
          }
      }

      迭代写法：

      b可以写成若干二次幂的和，如$2^{13} = 2^{(1101)_2} = 2^8 2^4 2^1$

      当二次幂$i$号位被选中（中间的式子），那么$a^{2i}$就被选中（右边的式子）

      1. 判断b的二进制末尾是否为1，是则令ans*a
      2. a自乘，相当于进入下一位的判断和计算
      3. b右移一位，和2的作用类似
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      LL binaryPow(LL a, LL b, LL m)
      {
          LL ans = 1;
          while (b)
          {
              if (b & 1)	// b的二进制末尾为1
              {
                  ans = ans * a % m;	// 用b的二进制计算幂
              }
              a = a * a % m;
              b >>= 1;		// b右移一位
          }
          
          return ans;
      }

​ 注：任何正整数对1取模一定为0

1.5 Two Pointer

Two Pointer即双指针，用两个指针（或下标）一同访问一个序列，加快速度

1.5.1 归并排序

two pointer思想：merge中，两个数组两个指针

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
// 合并数组
void merge(int A[], int L1, int R1, int L2, int R2)		// [L1,R1]是左半边，L2=R1+1
{
    int i = L1, j = L2;
    int temp[MAXN], index = 0;
    
    while (i <= R1 && j <= R2)		// 合并
    {
        if (A[i] <= A[j])
            temp[index++] = A[i++];
        else
            temp[index++] = A[j++];
    }
    while (i <= R1)
        temp[index++] = A[i++];		// 加入剩余元素
    while (j <= R2)
        temp[index++] = A[j++];		// 加入剩余元素
    
    for (i = 0; i < index; i++)
        A[L1 + i] = temp[i];		// 合并后的序列赋值回A
    
}

// 归并排序O(nlogn)
void mergeSort(int A[], int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);		// 排左子区间
        mergeSort(A, mid + 1, right);	// 排右子区间
        merge(A, left, mid, mid + 1, right);	// 合并
    }
}

1.5.2快排

two pointer思想：partition中，一个数组、首尾双指针

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 <stdlib.h>
#include <time.h>

int randPartition(int left, int right)
{
	// 随机轴 
    // rand()生成一个[0, RAND_MAX]的数
    // [0, RAND_MAX]->[0, 1]->[0, right-left]->[left, right]
	int p = (int)round(1.0 * rand() / RAND_MAX * (right - left) + left);
	swap(A[left], A[p]);
	
    // 切分，左边比轴小，右边比轴大
	int temp = A[left];
	while(left < right)
	{
		while (left < right && A[right] > temp) right--;	// 右往左找比轴小的
		A[left] = A[right];	
		while (left < right && A[left] <= temp) left++;		// 左往右找比轴大的
		A[right] = A[left];	
	}
	A[left] = temp;		// left = right
	return left;
}

void quickSort(int L, int R)
{
	int pivot;
	if (L < R)
	{
		pivot = randPartition(L, R);	// 切分
		quickSort(L, pivot - 1);	// 排左区间
		quickSort(pivot + 1, R);	// 排右区间
	}
}

int main()
{
    ...
    srand((unsigned)time(NULL));	// 随机种子 
    // time返回自1970-01-01来经过的秒数，参数为接受该值的指针（和返回值一致）
    // 不需要存下该值，所以为NULL
    ...
}

1.6 其他高效技巧

  • 打表

  • 递推（有时思考一下递推式比简单暴力高效很多）
    “有几个PAT”：计算一个给定字符串包含多少个PAT

    暴力计算会超时，但利用组合的思想，计算A左边的P数，乘以A右边的T数，就能得到一个A形成的PAT个数

    例如 APPAPT，中间的A左边2个P，右边1个T，总共能形成2*1=2个PAT，将所有A的结果相加得到最终结果

  • 随机选择算法（求第K大的数）
    此处有文字游戏：如1 2 3 4 5 6，有两种理解：1）第一大 1，第二大 2；2）第一大 6，第二大 5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 期望时间O(n)
    void randSelect(int A[], int left, int right, int K)
    {
    	int p = randPartition(left, right);	// 使用快排的randPartition
    	int M = p - left + 1;	// 位置p在[left,right]中排在第M位
    	
    	if (K == M) 
            return A[p];	// 找到第K大元素
    	else if (K < M) 
            return randSelect(A, left, p - 1, K);	// 在左子区间
    	else 
            return randSelect(A, p + 1, right, K - M);	// 在右子区间的第K-M位
    }

2 数学问题

简单数学

  • 数字黑洞

最大公约数和最小公倍数

1
2
3
4
5
6
// 最大公约数
int gcd(int a, int b)
{
    if (b == 0) return a;
    else return gcd(b, a % b);
}
1
2
3
4
5
6
//最小公倍数
int lcm(int a, int b)
{
    return a * b / gcd(a, b);
    // 可能溢出，也可写为 return a / gcd(a, b) * b
}

分数四则运算

素数

素数：不能被其他数整除的数（n%i!=0）

求素数表

  • 遍历1-sqrt(n)，复杂度为O(n * sqrt(n))

  • 质数筛

    • 埃氏(O(nloglogn))：对每个质数，筛去其倍数

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void prime()
      {	
      	// i既可能是待存质数，同时也作为筛 
      	for (int i = 2; i <= MAXN; i++)
      	{
      		if (!vis[i]) 
      		{
      			p[++p[0]] = i;	// p[0]为cnt
      			for (int j = i + i; j <= MAXN; j += i)
      				vis[j] = true;
      		}	 
      	}
      }

    • 欧拉筛(O(n))：在埃氏筛的基础上，每个合数只被其最小质因子筛去，避免重复

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      void prime()
      {
      	for (int i = 2; i <= MAXN; i++)
      	{
      		// 存质数 
      		if (!vis[i])
      			p[++p[0]] = i;
      		
      		// 筛：筛去i * p[j]
      		for (int j = 1; j <= p[0] && i * p[j] <= MAXN; j++)
      		{
      			vis[i * p[j]] = true;
      			if (i % p[j] == 0)	// 以后会由质因子筛到，避免重复 
      				break;
      		}
      	}	
      }

      关键语句if ((i % p[j]) == 0) break;的理解：

      1. 当$i \% p[j]$时，令$i = k \times p[j]$，继续往下执行，即筛$i \times p[j+1]$，而此时有$i \times p[j+1] = p[j] \times k \times p[j+1]$，即$i \times p[j+1]$会在$i’=k \times p[j+1]$时由$p[j]$筛掉，此时属于重复操作，违背由最小质因子筛去的法则。对于$p[j+2], … p[j+m]$类同，因而中断循环

      注意！！！i % p[j]== 0才表示p[j]整除i！！！

大整数运算

由于大整数运算从低位开始，而字符串读入从高位，因此在转换时要记得反置

  • 大整数结构体

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct BigN
    {
    	int num[MAXN];
    	int len;
    	
        // 初始化函数
    	BigN()
    	{
    		memset(num, 0, sizeof(d));
    		len = 0;
    	}
    };

  • 加法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    BigN add(BigN a, BigN b)
    {
    	BigN c;
    	int carry = 0;	// 进位
    	int res;
    	
    	for (int i = 0; i < a.len || i < b.len; i++)
    	{
    		res = a.num[i] + b.num[i] + carry;
    		c.num[c.len++] = res % 10;
    		carry = res / 10;
    	}
    	
        // 末尾进位
    	if (carry != 0)
    	{
    		c.num[c.len++] = carry;
    	}
    	
    	return c;
    }

  • 减法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 假设a > b，如果a < b需交换a、b并在前面加-号
    BigN sub(BigN a, BigN b)
    {
    	BigN c;
    	for (int i = 0; i < a.len || i < b.len; i++)
    	{
    		if (a.num[i] < b.num[i])
    		{
    			a.num[i] += 10;
    			a.num[i+1] -= 1;	// 由于a > b，if不会在i=len时成立，所以不会越界 
    		}
    		c.num[c.len++] = a.num[i] - b.num[i];
    	}
    	
    	while (c.len > 1 && c.num[c.len-1] == 0) 	// 去除高位0但保留至少1位数
            c.len--;
    	return c;
    }

  • 高精度与低精度的乘法

    1. 从低位遍历大整数，每位与低精度相乘，并加上已有进位
    2. 取个位数为结果，多位
    3. 循环直至遍历所有位，记得考虑最后的进位
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    BigN mult(BigN a, int b)
    {
        BigN c;
        int carry = 0;
        
        for (int i = 0; i < a.len; i++)
        {
            int temp = a.num[i] * b + carry; // 每位与低精度相乘，并加上已有进位
            c.num[c.len++] = temp % 10;	// 取个位数为结果
            carry = temp / 10;	// 高位为进位
        }
        
        while (carry != 0)	// 最后的多位进位
        {
            c.num[c.len++] = carry % 10;
            carry /= 10;
        }
    }

  • 高精度与低精度除法
    注意：唯一从字符串反置后的高位开始遍历的计算（加减乘都是从低位），实际就是直接按输入的序

    1. 商的位数和被除数（左边）的位数一一对应
    2. 遍历被除数的每一位，余数（初始化为0）和每次选取的位组成新的临时被除数
    3. 若除不了（小于除数），结果为0，进入下一位；若能除，记录商，更新余数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    BigN divide(BigN a, int b, int& r)
    {
        BigN c;
        c.len = a.len;	// 商和被除数每一位一一对应
        int temp = 0;
        
        for (int i = a.len - 1; i >= 0; i--)	// 从高位开始遍历
        {
            temp = temp * 10 + a.num[i];	// 本次选择的位与上一位遗留的余数组合
            if (temp < b)	c.num[i] = 0;	// 不够除，该位为0
            else	// 够除
            {
                c.num[i] = temp / b;	// 商
                temp = temp % b;	// 该位遗留的余数
            }
        }
        r = temp;	// 最终余数
        
        while (c.len > 1 && c.num[c.len - 1] == 0) c.len--;	// 去除高位0但至少保留1位
    }

组合数

  • 求n!中有多少个质因子pO(logn)
    结论：n!中有$\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^3}+…$个质因子p

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int cal(int n, int p)
    {
        int ans = 0;
        while (n)
        {
            ans += n / p;
            n /= p;
        }
    }

    可用于计算n!末尾有多少个0：计算质因子5的个数

  • 求组合数$C_{n}^{m}$

    1. 定义计算（阶乘）（long long也只能承受n<20的数据）

    2. 递推公式：$Cn^m = C{n-1}^m + C_{n-1}^{m-1}$，$C_n^0 = C_n^n = 1$

      1
      2
      3
      4
      5
      long long C(long long n, long long m)
      {
          if (m == 0 || n == m) return 1;
          else return C(n-1, m) + C(n-1, m-1);	// 可以储存计算结果防止重复计算
      }

    3. 用定义，边除边乘，$C_{n+m-i}^{i}=\frac{(n-m+1)(n-m+2)…(n-m+i)}{12…i}$一定是整数

      1
      2
      3
      4
      5
      6
      7
      8
      9
      long long C(long long n, long long m)
      {
          long long ans = 1;
          for (long long i = 1; i <= m; i++)
          {
              ans = ans * (n - m + i) / i;
          }
          return ans;
      }

C++标准模板库STL

  • 注1：
    无特殊说明，一般

    1
    2
    #include <[STL名字]>
    using namespace std;

    即可使用

  • 注2：
    STL嵌套，如果出现>>，记得在中间加空格：> >，否则c++11会将其识别为移位

  • 注3：
    STL的find()一般用if (stl.find(x) != stl.end())进行判断，string特殊，可以用string::npos

  • 注4： 计算value在stl中的个数

    1
    count(stl.begin(), stl.end(), value);

  • 注5：C++11新特性！

    • 引入emlace_front、empace 和 emplace_back进行构造插入

      1
      2
      3
      4
      5
      6
      //push_back()创建一个临时对象，然后将临时对象拷贝到容器中
      d.push_back(Date(“2016”,”05”,”26”));

      // 直接进行构造插入，省去构造临时对象的开销
      // 前提是元素需要有相应的构造函数
      d.emplace_back(“2016”,”05”,”26”);

vector

  • 定义

    1
    2
    3
    vector<typename> name;	// 一维变长
    vector<vector<typename>> name;	// 二维变长
    vector<typename> arrName[arrSize];	// 第一维定长，第二维变长

  • 元素访问

    • 使用下标：v[i]
    • 迭代器：
      • vector<typename>::iterator it：类似指针，用*it访问元素
      • vi.begin(), vi.end()：左闭右开。（只有vector和string可以使用vi.begin()+i的写法

  • 常用函数

    1
    2
    3
    4
    5
    6
    7
    vi.push_back(x);	// O(1)
    vi.pop_back();	// O(1), 删除尾元素
    vi.size();	// O(1), 返回unsigned类型
    vi.clear(); // O(n), 清除vector中所有元素
    vi.insert(it, x);	// O(n), 向it处插入一个元素
    vi.erase(it);	// O(n), 删除it处的元素
    vi.erase(first, last)	// O(n), 删除[first, last)内的所有元素, first, last为迭代器

set

内部自动有序且不含重复元素的集合

  • 定义：和vector类似

  • 元素访问
    只能通过迭代器：set<typename>::iterator it

    1
    2
    3
    4
    5
    // 只能按以下方式枚举，不支持*(it+i)
    for (set<int>::iterator it = st.begin(); it != st.end(); it++)
    {
        printf("%d", *it);
    }

  • 常用函数

    1
    2
    3
    4
    5
    6
    7
    8
    st.insert(x);	// O(logn), 自动递增排序和去重
    st.find(value);	// O(logn), 返回值为value的迭代器it
    st.count(value);	// 如果value在集合中，返回1，否则返回0
    st.erase(it);	// O(1), 删除元素
    st.erase(value);	// O(logn), 删除元素
    st.erase(first, last);	/// O(n)
    st.size();	// O(1)
    st.clear();	// O(n)
  • 拓展：multiset, unordered_set

string

  • 定义

    1
    2
    3
    4
    5
    6
    7
    8
    // 使用字符串常量初始化
    string str = "abcd";

    // 使用字符数组初始化
    char c[MAXN];
    ...
    string str(c);
    string str1 = c;

  • 元素访问

    • 直接像字符数组一样访问

    • 直接输入输出，只能用cin和cout

      1
      2
      3
      string str;
      cin >> str;
      cout << str;

    • 使用printf输出

      1
      printf("%s\n", str.c_str());

    • 迭代器访问

      1
      2
      3
      4
      for (string::iterator it = str.begin(); it != str.end(); it++)
      {
          printf("%c", *it);
      }

  • 常用函数

    • operator+=（字符串拼接）

      1
      string str3 = str1 + str2;

    • compare operator，按字典序比较

      1
      2
      3
      4
      if (str1 >= str2)
      {
          // do something...
      }

    • 其他

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      str.length(); str.size();	// O(1), 二者基本相同
      str.insert(pos, str2);	// O(N), 在pos下标处插入str2
      str.insert(it, first, last);	//	O(N), 在原字符串it处插入串[first, last)
      str.erase(it);	// O(N), 删除it指向的元素
      str.erase(first, last);
      str.erase(pos, length);	// 从pos处删除length个字符(含本身)
      str.clear();	// O(1), 清空
      str.substr(pos, len);	// O(len), 返回从pos开始、长度为len的子串
      str.find(str2); // O(nm), 如果str2是字串, 返回其在str第一次出现的位置, 否则返回string::npos(unsigned_int型, 值为-1)
      str.find(str2, pos);	// 从pos处开始匹配str2
      // 常用写法：if (str.find(str2) != string::npos) 如果能找到, 则...
      str.replace(pos, len, str2); // O(n), 把str从pos处开始、长度为len的子串替换为str2
      str.replace(first, last, str2);	// 把str的[first, last)子串替换为str2

map

map内的键会按从小到大顺序自动排序（因为是基于红黑树实现），键唯一

注：

​ map无法按value排序，只能将pair放进vector里，对vector排序

  • 定义

    1
    map<type1, type2> mp;

  • 访问

    • 直接使用下标（新值会覆盖旧值）

      1
      mp['c'] = 20;

    • 通过迭代器访问

      1
      2
      3
      map<type1, type2>::iterator it;
      it->first;	// 访问键
      it->second;	// 访问值

  • 常用函数

    1
    2
    3
    4
    5
    6
    7
    it = mp.find(key);	// O(logN), 返回键为key的迭代器it
    mp.insert(make_pair(value1, value2));
    mp.erase(it);	// O(1), 删除元素
    mp.erase(key);	// O(logN), 根据键删除
    mp.erase(first, last);	// 删除一个区间的元素
    mp.size();	// O(1)
    mp.clear(); // O(N)

  • 拓展

    • multimap：一个键对多个值
    • unordered_map：只映射不排序，比纯map快很多

  • 其他

    • hashmap可当作bool数组使用
    • map会自动初始化

queue

先进先出

  • 定义

    1
    queue<type> q;

  • 元素访问
    只能用q.front()或q.back()访问队首或队尾元素
    （ps：访问前先使用empty()判断队是否空）

  • 常用函数

    1
    2
    3
    4
    5
    q.push();	// O(1)
    q.front(); q.back();	// O(1)
    q.pop();	// O(1) 队首出队
    q.empty();	// O(1) 队列是否空
    q.size();

  • 拓展

    • 双端队列deque：首尾皆可插入和删除
    • 优先队列priority_queue：堆实现，最大元素置于队首

  • 其他

    • 通常通过重新定义一个队列来完成清空O(1)

priority_queue

用堆实现，队首元素是当前队列中优先级最高的一个

  • 定义

    1
    2
    #include <queue>
    priority_queue<type> name;

  • 元素访问
    只能通过top()来访问队首元素（优先级最高）
    （ps：使用top()前要用empty()判断队是否空）

  • 常用函数

    1
    2
    3
    4
    5
    pq.push(x);	// O(logN), 入队
    pq.top();	// O(1)
    pq.pop();	// O(logN), 令队首元素出队
    pq.empty();	// O(1), 队是否空
    pq.size();	// O(1)

  • 优先级设置

    • 基本数据类型
      默认为大顶堆。小顶堆写法为：

      1
      priority_queue< [type], vector<[type]>, greater<[type]> > pq;

      vector<[type]：承载堆的容器；greater<[type]>：小于对应大优先级

    • 结构体优先级

      写在结构体内：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      struct fruit
      {
          string name;
          int price;
          // 重载小于号
          friend bool operator < (const fruit& f1, const fruit& f2)
          {
              return f1.price < f2.price;	// 价格大的优先级大, 相当大顶堆
              // return f1.price > f2.price // 价格小的优先级大，即小顶堆
          }
      };

      priority_queue<fruit> pq;

      （friend友元允许非成员函数访问类/结构体的所有成员）

      写在结构体外：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      struct cmp
      {
          bool operator() (const fruit& f1, const fruit& f2)
          {
              return f1.price > f2.price;	// 小顶堆
          }
      };

      priority_queue<fruit, vector<fruit>, cmp> pq;

      注意：结构体指针的比较需另写struct cmp

      1
      2
      3
      4
      5
      6
      7
      8
      struct cmp
      {
      	bool operator() (const Node* n1, const Node* n2) const
      	{
      		return n1->v > n2->v;
      	}
      };
      priority_queue<Node*, vector<Node*>, cmp> pq;

stack

后进先出

  • 定义

    1
    stack<type> name

  • 元素访问
    st.top()

  • 常用函数

    1
    2
    3
    4
    st.push(x);		// O(1)
    st.top();		// O(1)
    st.pop();		// O(1)
    st.empty();		// O(1)

  • 其他

    • 通常通过重新定义一个栈来完成栈的清空O(1)

pair

将两个元素合成为一个

  • 定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include <utility>
    using namespace std;

    // 声明
    pair<type1, type2> name;
    //初始化
    pair<type1, type2> p(value1, value2);
    //临时构建
    pair<type1, type2>(value1, value2);	// 方法一
    make_pair(value1, value2);		// 方法二

  • 元素访问

    只有两个元素：p.first，p.second

  • 常用函数

    • 比较操作
      直接使用比较符号如>=, !=。首先比较first，只有当first相等时才去比较second
      （可类似priority_queue重写<号）

  • 常见用途
    作为map的键值对插入

    1
    mp.insert(make_pair(value1, value2));s

algorithm头文件下的常用函数

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

// x, y为整数
max(x, y);
min(x, y);
abs(x);		// 若想获取浮点数的绝对值，使用math头文件下的fabs

swap(x, y);	// 交换x和y的值

reverse(it1, it2);	// 使数组或STL的[it1, it2)之间的元素反转

typename a[N];
do
{
	printf("%d%d%d...", a[0], a[1], a[2]...);   
} while (next_permutation(it1, it2));	// 给出序列[it1, it2)在全排列中的下一个序列

fill(it1, it2, value);	// 给数组或容器的某一段区间赋值value, 区别memset

sort(it1, it2, cmp);	// 默认升序

lower_bound(it1, it2, val);	// 寻找[it1, it2)内第一个值大于等于val的元素位置，返回指针/迭代器
upper_bound(it1, it2, val);	// 返回第一个大于val的元素位置
// ps: 如果没有该元素，返回的是可供插入的位置，即假设元素存在时其所在的位置
// 		若只想获得下标，令返回值减去数组首地址即可

数据结构专题

链表

  • 定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 动态
    struct node
    {
        typename data;	// 数据域
        node* next;	// 指针域
    };

    // 静态
    struct node
    {
        typename data;
        int next;	// 用数组下标表示指针域
    };

  • 空间分配

    1
    2
    3
    4
    5
    6
    // C malloc
    #include <stdlib.h>
    node* p = (node*)malloc(sizeof(node));

    // c++ new
    node* p = new node;

    (申请较大动态数组时可能会失败)

    内存泄漏：使用malloc或new分配的空间，使用后没有释放，直到程序结束前一直占据。

    内存泄漏会导致内存消耗过快而最终五内存可使用

    1
    2
    3
    4
    5
    // C free
    free(p);	// p为指针变量，free释放p指向的空间，并将p指向NULL

    // C++
    delete(p);

    malloc与free成对出现；new与delete成对出现

  • 创建与增删

    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
    // 创建
    node* create(vector<typename> arr)
    {
    	node *p, *head;
    	
    	head = new node;	// 使用头节点，相当于数组的下标0
    	for (int i = 0; i < arr.length(); i++)
    	{
    		p = new node;
    		p->val = arr[i];
    		p->next = head->next;
    		head->next = p;
    	}	
    	return head;
    }

    // 增
    void insert(node* head, int pos, int val)
    {
    	node* p = head;
    	
        // p移动到pos的前一个元素位置 
    	// (p从head开始，i从0开始，i到达pos-1时，p也到达第pos-1个元素) 
        // 使用头节点即可不用讨论在链表头插入的情况
        int i;
    	for (i = 0; i < pos - 1 && p != NULL; i++, p = p->next);
        
    	if (p == NULL || i > pos - 1)	// i小于1或大于表长
    		return;	
        
    	node* q = new node;
    	q->val = val;
    	q->next = p->next;
    	p->next = q;	
    }

    // 删(删除某一位置上的元素)
    void deleteNode(node* head, int pos)
    {
    	node* p = head;
    	node* q = NULL;
    	
        // 同insert寻找前元
    	for (int i = 0; i < pos - 1; i++, p = p->next);
        if (p == NULL || p->next == NULL) 
            return;
    	
    	q = p->next;	// 要删除q
    	p->next = q->next;
    	delete(q);	// 与new成对
    }

  • 静态链表排序
    将有效结点前置，按升序排序。之后即可用数组下标访问链表，数组序即为排序后的链表序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    // 定义有效位
    struct node
    {
        int data, addr;
        int next;
        int valid;	// 为true表示在链表上
    }ls[maxn];

    // 定义比较函数
    bool cmp(const node& n1, const node& n2)
    {
        if (n1.valid && n2.valid)	// 都是有效结点
        {
            return n1.data < n2.data;
        }
        else
        {
            return n1.valid > n2.valid;
        }
    }

    // sort需要排所有元素（包括无效的）
    sort(ls, ls+maxn, cmp);

搜索专题

DFS

找“岔路口”与“死胡同”

比如背包问题，对每个物品，有选或不选两种选择即“岔路口”；物品重量总和超过V或已完成n个物品选择，就到达“死胡同”

用递归即可写出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int index, int sumW, int sumC)
{
    if (index == n)	// 完成选择 
        return;
    
    dfs(index + 1, sumW, sumC);	// 岔路1：选
    
    if (sumW + w[index] <= V)	// 如果重量超过，到达死胡同
    {
        if (sumC + c[index] > max) 
            max = sumC + c[index];
        
        dfs(index + 1, sumW + w[index], sumC + c[index]);	// 岔路2：不选
    }
}

BFS

访问完所有邻接点，再往下层

一般用队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bfs(int s)
{
    queue<int> q;
    q.push(s);	// 起点入队
    
    while (!q.empty())
    {
        // 取队首元素q.front();
        // *****访问*****
        q.pop();	// 队首出队
        
        for (当前元素的邻接点x)
            q.push(x);
    }
}

迷宫问题

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
// 增量数组
int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0};

int BFS()
{
    q.push(S);
    inq[S.x][S.y] = true;
    while (!q.empty())
    {
        // 取队首
        node top = q.front();
        q.pop();

        if (top.x == T.x && top.y == T.y) 
        {
            return top.step;	// 遇到终点返回, 此时就是最小步数
        }
		
        // 利用增量数组访问四个方向上的点
        for (int i = 0; i < 4; i++)
        {
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if (isValid(newX, newY) && !inq[newX][newY])	// 点合法且没入过队
            {
                Node node(newX, newY);
                node.step = top.step + 1;	// 步数增加
                q.push(node);	// 结点入队
                inq[newX][newY] = true;	// 标记结点已入过队
            }
        }
    }
    return -1;
}
  • 注inq[x][y]的含义是判断结点是否入过队，而非结点是否已被访问。如果使用后者定义会导致重复入队，进而造成重复访问

  • 迷宫问题考虑的重点是：检查下一次可以走到的位置以及它们是否合法

  • 8数码难题的启发

    • 将数字排列的矩阵，转换为一串整型数字，当作状态，用于剪枝。已到过该状态就无需再入队
    • sprintf和sscanf处理字符串和数字间的转换

树

一些定义与概念

  • 结点、根结点、叶子结点、子树、边
  • 层次：根节点为第1层，往下增；
    • 深度：即层数
    • 高度：从最底层叶子结点（高度为1）向上逐层累加至该结点
  • 度
    • 结点的度：该结点子树的棵数，叶子结点的度为0
    • 树的度：树中结点的最大的度
  • 祖先、子孙：自己既是自己的祖先结点，也是自己的子孙结点

二叉树

概念

  • 递归定义：要么没有根节点，是一棵空树；要么由根节点、左子树、右子树组成，子树都是二叉树
    （与度为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
// 定义
struct node
{
    typename data;
    node* lch;
    node* rch;
};
node* root = NULL;

// 新建节点
node* newNode(typename x)
{
    node* p = new node;
    p->data = x;
    p->lch = NULL; p->rch = NULL;
    return p;
}

// 改查
void search(node* p, typename x, typename newData)
{
    if (root == NULL)
        return;
    
    if (root->data == x)
        root->data = newData;
    
    search(root->lch, x, newData);
    search(root->rch, x, newData);
}

// 插入（注意*root带引用）
void insert(node* &root, typename x)
{
    if (root == NULL)
    {
        root = newNode(x);
        return;
    }
    
    if (xxx)	// 根据性质
        insert(root->lch, x);
    else
        insert(root->rch, x);
}

// 创建
node* create(typename data[], int n)
{
    node* root = NULL;
    for (int i = 0; i < n; i++)
    {
        insert(root, data[i]);
    }
    return root;
}

完全二叉树的递归创建

1
2
3
4
5
6
7
8
Node* create(int x)
{
    Node* root = newNode(x);
    root->lch = create(2 * x);		// 递归创建左子树
    root->rch = create(2 * x + 1);	// 递归创建右子树
    
    return root;
}

遍历

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
// 先序 中-左-右
void preOrder(node* root)
{
    if (root == NULL)
        return;
    
    // 访问
    printf("%d ", root->x);
    
    preOrder(root->lch);
    preOrder(root->rch);
}

// 中序 左中右
void inOrder(node* root)
{
    if (root == NULL)
        return;
    
    inOrder(root->lch);
     // 访问
    printf("%d ", root->x);
    
    inOrder(root->rch);
}

// 后序 左右中
void postOrder(node* root)
{
    if (root == NULL)
        return;
    
    postOrder(root->lch);
    postOrder(root->rch);
    // 访问
    printf("%d ", root->x);
}

// 层序遍历
void  layerOrder(node* root)
{
    queue<node*> q;
    
    q.push(root);
    while (!q.empty())
    {
        node* now = q.front();
        q.pop();
        // 访问
        printf("%d ", root->x);
        
        if (now->lch != NULL) q.push(now->lch);
        if (now->rch != NULL) q.push(now->rch);
    }
}

二叉树静态实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 用数组下标代表指针，-1表示NULL
struct node
{
    typename data;
    int lch;
    int rch;
}Node[maxn];
int root = -1;

// 新建结点
int index = 0;
int newNode(int v)
{
    Node[index].data = v;
    Node[index].lch = Node[index].rch = -1;
    return index++;
}

// 其余的与指针表示一致

注：

  • 有些题按层序标了号，要求计算一些特性，此时可能无需建树（只需假想一棵树），利用下标计算：
    当前结点: x，左子: 2x，右子: 2x+1，
    判断超出范围：2x > n

一般的树

尽量考虑静态写法，maxn为结点数上限

1
2
3
4
5
sreuct node
{
    typename data;
    vector<int> child;	// 子结点下标
} Node[maxn];

从树的遍历看DFS与BFS

  • DFS：合法的DFS都能画出树的形式，“死胡同”等价于叶子结点；“岔路口”等价于非叶子结点，DFS遍历过程即树的先序遍历过程
    从树的角度引入对状态的剪枝
  • BFS：即对树的层序遍历

需要再看看的题目

  • codeup_611_b 子结点计算
  • codeup_611_d 树重建（主要看指针方式存储树的创建）

二叉查找树 BST

也叫二叉排序树

递归定义：

  • 要么是一棵空树
  • 要么由根节点、左右子树构成，左子树上的结点小于根结点，右子树上的结点大于根节点

性质：

  • 对二叉查找树进行中序遍历，遍历结果是有序的

编码

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
// 查找 O(h)
bool search(node* root, int x)
{
    if (root == NULL)	// 查找失败
        return false;
    
    if (x == root->data)
        return true;	//查找成功
    else if (x < root->data)
        return search(root->lch, x);	// 小于则往左找
    else
        return search(root->rch, x);	// 大于则往右找
}

// 插入 O(h)
void insert(node* &root, int x)	// 没有修改根节点的值, 而是为对应层的root赋予新的地址
{
    if (root == NULL)	// 查找失败，即插入的位置
    {
        root = newNode(x);
        return;
    }
    
    if (x == root->data)	// 查找成功，已存在该点
        return;
    else if (x < root->data)
        insert(root->lch, x);
    else
        insert(root-rch, x);
    
}

// 建立
node* create(int data[], int n)
{
    node* root = NULL;
    for (int i = 0; i < n; i++)
        insert(root, data[i]);
    
    return root;
}

删除比较难，单独记录一下：

删除结点v的基本思路是：使v的前驱（左子树的最大结点，即左子树最右结点）或后继（右子树的最小结点，即右子树的最左结点）覆盖v，然后递归删除前驱或后继

编码

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
node* findMax(node* root)
{
	// Q: 为什么这里传指针，还能修改呢？
	// A: 因为没有改指针里的内容，将node*看成unsigned int，实际上传进来的是拷贝
	while (root->rch != NULL)
		root = root->rch;
	
	return root;
}
node* findMin(node* root)
{
	while (root->lch != NULL)
		root = root->lch;
	
	return root;
}

void deleteNode(node* root, int x)
{
	if (root == NULL)	// 找不到，删除失败
		return;
    
    if (x == root->data)	// 找到结点
    {
        if (root->lch == NULL && root->rch == NULL)	// 叶子结点直接删除
            root = NULL;
        else if (root->lch != NULL)	// 左子树非空
        {
			node* pre = findMax(root->lch);	// 找到前驱	
            root->data = pre->data;	// 覆盖待删除结点
            deleteNode(root->lch, pre->data);	// 在左子树继续删除pre
        }
        else	// 右子树非空
        {
            node* next = findMin(root->rch);
            root->data = next->data;
            deleteNode(root->rch, next->data);
        }
    }
    else if (x < root->data)	// 小，往左找
        deleteNode(root->lch, x);
    else						// 大，往右找
        deleteNode(root->rch, x);
}

注：一直删除前驱或后继会导致树退化成一条链，解决办法有：

  1. 交替删除前驱或后继
  2. 记录高度，总是优先在高度较高的一棵子树里删除结点

平衡二叉树 AVL树

使树高在每次插入后保持O(logn)级别

平衡因子

平衡因子：左子树与右子树的高度差（ps：高度从叶子开始计算，叶子为1）

为记录平衡因子，需要在树的结构中增加变量height：

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
struct Node
{
    int v;
    int height;
    Node* lch, rch;
};

Node* newNode(int x)
{
    Node* node = new Node;
    //...
    node->height = 1;	// 初始树高为1
    //...
    return node;
}

// 获取树高
int getHeight(Node* root)
{
    if (root == NULL)	// 空结点的高度为0
        return 0;
    return root->height;
}

// 计算平衡因子
int getBalanceFactor(Node* root)
{
    return (getHeight(root->lch) - getHeight(root->rch));
}

// 更新树高
void updateHeight(Node* root)
{
    // 需要#include <algorithm>
    root->height = max(getHeight(root->lch), getHeight(root->rch)) + 1;
}

AVL树的重点是插入，需要考虑平衡的调整：

旋转

  • 左旋：

    1. 使B的左子树♦成为A的右子树
    2. 使A成为B的左子树、更新高度
    3. 根节点设置为B

    image-20210309131148866

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void leftRotation(Node* &root)
    {
        Node* temp = root->rch;
        
        root->rch = temp->lch;	// 步骤1
        temp->lch = root;		// 步骤2
        updateHeight(root);		// 顺序别反，root此时是temp的子树
        updateHeight(temp);
        root = temp;			// 步骤3
    }

  • 右旋

    1. 使A的右子树成为B的左子树
    2. 使B成为A的右子树、更新高度
    3. 根节点设置为A

    image-20210309132227795

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 实际上就是把左旋的lch和rch颠倒
    void rightRotation(Node* &root)
    {
        Node* temp = root->lch;
        
        root->lch = temp->rch;		// 步骤1
        temp->rch = root;			// 步骤2
        updateHeight(root);
        updateHeight(temp);
        root = temp;				// 步骤3
    }

插入

AVL插入即BST插入+平衡调整

平衡调整：将最靠近插入结点的失衡结点调整到正常

四种情况（左插LL、LR，右插RR、RL）：

树形 判定条件 调整方法 示图
LL BF(root) = 2,
BF(root->lch) = 1		 对root右旋 image-20210309133417940
LR BF(root) = 2,
BF(root->lch) = -1		 对root->lch左旋，再对root右旋 image-20210309133715663
RR BF(root) = -2,
BF(root->rch) = -1		 对root左旋 image-20210309134048706
RL BF(root) = -2,
BF(root->rch) = 1		 对root->rch右旋，再对root左旋 image-20210309134154099

编码

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
void insert(Node* root, int x)
{
	if (root == NULL)
    {
        root = newNode(x);
        return;
    }
    
    if (x < root->data)	// 左插
    {
        insert(root->lch, x);
        updateHeight(root);		// 插入后别忘了更新树高
        if (getBalanceFactor(root) == 2)	// 失衡：左高于右
        {
            if (getBalanceFactor(root->lch) == 1)	// LL
            {
                rightRotation(root);
            }
            else if (getBalanceFactor(root->lch) == -1)	// LR
            {
                leftRotation(root->lch);
                rightRotation(root);
            }
        }
    }
    else	// 大于或等于root，右插
    {
        insert(root->rch, x);
        updateHeight(root);
        if (getBalanceFactor(root) == -2)	// 失衡：右高于左
        {
            if (getBalanceFactor(root->rch) == -1)	// RR
            {
                leftRotation(root);
            }
            else if (getBalanceFactor(root->rch) == 1)	// RL
            {
                rightRotation(root->rch);
                leftRotation(root);
            }
        }
    }
}

知道如何插入后，AVL树的建立与查找就和BST无异了：

1
2
3
4
5
6
7
8
9
Node* create(int data[], int n)
{
    Node* root = NULL;
    for (int i = 0; i < n; i++)
    {
        insert(root, data[i]);
    }
    return root;
}

注意易错点：

  • search不要想复杂了，查找树按照大小选择子树查找，如果找不到，就是查找失败，无需考虑其他树上有没有该结点
  • 涉及对root本身的修改要记得用指针引用Node* &root，这里有leftRotation, rightRotation和insert
  • insert之后要记得updateHeight

哈夫曼树

结点的路径长度：从根结点到该结点所经过的边数

叶子的带权路径长度：叶子的权值乘以路径长度

树的带权路径长度：所有叶子结点的带权路径长度之和

哈夫曼树：树的带权路径最小的二叉树（最优二叉树）

构建过程：

  1. 初始n个结点，视为n棵只有1个结点的树
  2. 合并其中权值最小的两棵树，生成两棵子树的父结点，权值为两个根结点之和
  3. 重复步骤2，直到只剩下一棵树为止，这棵树即哈夫曼树，根结点的权值为最小带权路径长度

哈夫曼树的构建思想核心为：反复选择两个最小的元素，合并，直到剩下一个元素。有时无需构建树，只需通过合并，得到最终带权路径长度即可。

哈夫曼编码：

  • 对任何一个叶子结点，其编号一定不会成为其他任何结点编号的前缀
  • 左0右1
  • 按频次作为权值，字符串编码为01串的长度即树的带权路径长度

image-20210311163608746

并查集

定义

  • 并（Union）：合并两个集合；

  • 查（Find）：查找，判断两个元素是否在同一集合；

  • 集（Set）：集合

性质：

  • 并查集产生的每个集合都是一棵树（因为只对不同集合进行合并，集合内不会有环）

实现：

  • 用数组father[i]记录结点i的父节点；若i=father[i]，说明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
38
39
40
41
42
43
44
45
46
47
48
49
// 初始化
for (int i = 1; i <= N; i++)
{
    fa[i] = i;
}

// 查找
//int findFather(int x)
//{
//    while (x != fa[x])
//        x = fa[x];
//    return x;
//}
// 使用路径压缩的查找根节点方法 O(1)
int findFather(int x)
{
    int root = x;
    while (root != fa[root])	// 找到根结点
        root = fa[root];
    
    while (x != fa[x])		// 回溯x走过的结点
    {
        int tmp = x;
        fa[tmp] = root;		// 将它们的父节点都标记为根结点
        x = fa[x];
    }
    return root;
}

// 合并
void union(int a, int b)
{
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB)			// 若根节点不同
        fa[faA] = faB;		// 将一方的根结点指向另一方的根结点
}

// 集合个数 O(n)
int count()
{
    int cnt = 0;
   	for (int i = 1; i <= n; i++)
    {
        if (fa[i] == i)		// 集合的标志是根结点，只需数根结点的个数
            cnt++;
    }
    return cnt;
}

补充路径压缩的示意图：

image-20210309224829582

并查集模型的应用：

  • 输入一条边的两个点（双向边），使用union就能将两个点并在一个集合下，进而计数集合的个数或集合内元素个数

堆

定义

  • 堆是一棵完全二叉树

  • 大顶堆：树中每个结点的值都不小于孩子

  • 小顶堆：不大于

实现方式：用数组来存储完全二叉树，这样结点就按层序存储在数组中。第一个结点存于下标1，第i号的左孩子是2i，右孩子是2i+1，父亲是i/2

1
int heap[MAXN];

ps：如果不是强调自己实现堆，在可用STL的情况下，尽量用优先队列，不要造轮子

1
2
3
4
5
#include <queue>
using namespace std;

priority_queue<int> pq;		// 大顶堆
priority_queue< int, vector<int>, greater<int> > pq_s;	// 小顶堆

向下调整

  1. 当前结点与其孩子比较，将其中权值大的孩子与V交换
  2. 继续让V与孩子比较，直到孩子的权值都比V小或没有孩子结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// O(logn)
// 对heap数组[low, high]范围进行调整
// low为预调整的结点下标，high为堆最后一个元素的下标
void downAdjust(int low, int high)
{
    int i = low, j = 2 * i;
    
    while (j <= high)	// 存在孩子（左子不在右子肯定不在）
    {
        if (j + 1 <= hight && heap[j+1] > heap[j])	// 若存在右子，且右子大于左子
            j = j + 1;		// 令j为右子下标, j相当于max(左子, 右子)的下标
        
        if (heap[j] > heap[i])
        {
            swap(heap[j], heap[i]);	// 交换
            i = j;		//	继续向下比较
            j = 2 * i;
        }
        else
            break;	// 没有比结点i小的子结点，结束
    }
}

建堆

完全二叉树的叶子结点个数为$\lceil \frac{n}{2} \rceil$,因此在$[1, \lfloor \frac{n}{2} \rfloor]$范围内的都是非叶子结点，

n个结点的完全二叉树有性质

1）n0+n1+n2=n（其中n0表示度为0的结点）
2）n0=n2+1

3）n1 = 0 或 1

综上可得n0 = $\lceil \frac{n}{2} \rceil$

从$\lfloor \frac{n}{2} \rfloor$倒着枚举，对遍历到的结点$i$进行$[i, n]$范围的调整。

倒着调整是因为，每次调整一个结点后，当前子树中权值最大的结点就会处于子树的根结点位置（这正是向下调整的逻辑），轮到父节点调整时，又可以直接使用这一结果，保证了每个结点都是以其为根结点的子树的权值最大点

image-20210310212428242

记住结论即可：

1
2
3
4
5
6
7
8
// O(n)
void createHeap()
{
    for (int i = n / 2; i >= 1; i--)
    {
        downAdjust(i, n);
    }
}

删除堆顶

思路：用最后一个结点覆盖堆顶结点（根结点），然后对根结点向下调整

1
2
3
4
5
6
// O(logn)
void deleteTop()
{
    heap[1] = heap[n--];
    downAdjust(1, n);
}

增添元素

思路：把要添加的元素放在数组最后，然后向上调整

向上调整：与父结点比较，如果比父节点大就交换，直到到达堆顶或父节点权值大为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// O(logn)
// low一般为1，high为欲调整结点的下标
void upAdjust(int low, int high)
{
    int i = high, j = i / 2;	// j为父节点下标
    
    while (j >= low)	//父节点在数组范围内
    {
        if (heap[j] < heap[i])	// 父节点小
        {
            swap(heap[j], heap[i]);		// 与父节点交换交换
            i = j;		// 继续向上调整
            j = i / 2;
        }
        else
            break;
    }
}

// O(logn)
void insert(int x)
{
    heap[++n] = x;
    upAdjust(1, n);
}

堆排序

思路：取出堆顶元素，然后将堆的最后一个元素替换至堆顶，然后对堆顶向下调整

实际上为了节省空间，用原来存储heap的数组来存排序后的序列，所以用倒着遍历heap数组实现堆排序

  1. i从n开始遍历，直到堆只1个元素
  2. 访问到i，将i与堆顶交换
  3. 在[1, i-1]范围对堆顶进行向下调整
1
2
3
4
5
6
7
8
9
10
11
12
13
// O(nlogn)
// 堆排序与快排有相同的时间复杂度，且不会退化
// 但堆排较快排的劣势是常数较大
void heapSort()
{
    createHeap();
    
    for (int i = n; i > 1; i--)	// 遍历直到堆只剩1个元素
    {
        swap(heap[1], heap[i]);	// 与堆顶交换
        downAdjust(1, i - 1);	// 调整堆顶
    }
}

总结一下

  • 倒着遍历：
    • 建堆：数组中已有数据，从$\lceil \frac{n}{2} \rceil$开始倒着遍历，对每个结点向下调整，建立起堆结构
    • 堆排序：从结点n开始倒着遍历，和堆顶交换，对堆顶向下遍历，已访问的结点固定不再动
  • 调整
    • 向下调整：用于建堆、删除堆顶、堆排序。后二者是对堆顶向下调整，调整后，子树根结点就存放着最大元素
    • 向上调整：用于插入时，将尾巴插入的结点调整到它的位置

图

定义：

  • 图由顶点和边组成：G(V, E)

  • 有向图与无向图

  • 度：和顶点相连的边的条数；
    入度：入边条数；出度：出边条数

  • 权值：点权、边权

图的存储

邻接矩阵：

  • G[i][j]=1代表结点i和j之间有边，G[i][j]=0或-1表示无边

  • G[i][j]存放边权，对于不存在的边可设为0、-1或一个很大的数

一般适用于顶点数目不大（不超过1000）的题目

邻接表

Adj\[i\]存放顶点i的所有出边组成的列表

1
2
3
4
5
6
7
struct Node
{
    int v, w;	// 编号、边权
    Node(int _v, int _w) : v(_v), w(_w) {}	// 构造函数
};

vector<Node> Adj[N];

使用构造函数实现加边

1
Adj[i].push_back(Node(3, 4));	// i和3之间的边，结点3的权值为4

图的遍历

对无向图：

  • 连通：两个顶点之间相互可达
  • 连通图：图G(V, E)中任意两个顶点连通
  • 连通分量：非连通图中的极大连通子图

对有向图：

  • 强连通：两个顶点各有一条有向路径通向另一个顶点（即可达）
  • 强连通图：图G(V, E)中任意两个顶点强连通
  • 强连通分量：非强连通图中的极大强连通子图

DFS

邻接表版：

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
vector<int> adj[MAXV];
bool vis[MAXV] = {false};

//（ps：其本质还是递归边界和递归式，不过递归边界隐藏在邻接点访问和vis[]数组中，
// 没有点可访问了就到了递归边界）
void DFS(int u, int depth)
{
    // 访问结点u
    vis[u] = true;
    /*
    	...访问细节
    */
    
    
    // 访问u的邻接点
    for (int i = 0; i < adj[u].size(); i++)
    {
        int v = adj[u][i];
        if (!vis[v])
            DFS(v, depth + 1);
    }
}

void DFSTravel()
{
    // 遍历所有连通块
    for (int u = 0; u < n; u++)
    {
        if (!vis[u])
            DFS(u, 1);
    }
}

无向图、邻接矩阵存储，涉及边权的累计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void DFS(int u, int& totalW)
{
	vis[u] = true;
	/*
    	访问...
   	*/
    
	for (int v = 0; v <nump; v++)
	{
		if (G[u][v] > 0)	// 如果有边
		{
			// 累计边权 
			totalW += G[u][v];
			G[u][v] = G[v][u] = 0;	// ***/删除边，防止回头，因为此处不考虑是否访问过
			
			// dfs访问 
			if (!vis[v])
				DFS(v, totalW);
		}
	}
}

BFS

之前介绍过了，这里只放图的代码

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
// 邻接矩阵版
int n, G[MAXV][MAXV];
bool inq[MAXV] = {false};	// 是否入过队

void BFS(int u)
{
    queue<int> q;
    q.push(u);
    inq[u] = true;
    
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int v = 0; v < n; v++)
        {
            // 有边且未入过队
            if (!inq[v] && G[u][v] != INT_MAX)
            {
                q.push(v);
                inq[v] = true;
            }
        }
    }
}

// 邻接表版 参考搜索专题

注意：清空inq数组时，要对整个MAXV长度清空，否则后面来的如果访问顶点数大于前者

最短路径

Dijkstra

算法流程：

  1. 从未访问过的点集（V-S）中找到一个与起点距离最小的点u
  2. u作为中介点，对起点s 与 所有从u能到达的未访问顶点 进行relaxing（松弛）操作
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
const int INF = 1e9;
int G[MAXV][MAXV];
int d[MAXV];
int pre[MAXV];
bool vis[MAXV] = {false};

// 邻接矩阵写法
void Dijkstra(int s)
{
    fill(d, d+MAXV, INF);
    d[s] = 0;
    
    for (int i = 0; i < n; i++)
    {
        // 获取与顶点距离最小的点
        int u = -1, minD = INF;
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && d[j] < MIN)
            {
                u = j;
                minD = d[j];
            }
        }
        
        // 更新
        if (u == -1)	// 找不到点，说明剩下的点不连通
            return;
        vis[u] = true;
        for (int v = 0; v < n; v++)
        {
            // 松弛操作
            if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] + G[u][v];
                pre[v] = u;		// 记录前驱结点
            }
        }
    }
}

// 递归输出最短路径
void dfs(int s, int v)
{
    if (v == s)
    {
        printf("%d ", s);
        return;
    }
    dfs(s, pre[v]);
    printf("%d ", v);
}

三种可能的第二标尺（多条最短路径时的其他衡量标准）：

只需在relaxing操作中进行修改

  • 新增边权（如花费）
    初始化合数组d相同

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for (int v = 0; v < n; v++)
    {
        if (!vis[v] && G[u][v] != INF)
        {
            if (d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] + G[u][v];
                c[v] = c[u] + cost[u][v];
            }
            else if (d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v])	// 多条
                c[v] = c[u] + cost[u][v];
        }
    }

  • 新增点权（如每个点的资源）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // w[u]记录从起点s到点u收集的最大资源数（前提为路径最短）
    // 初始化w[s]=weight[s]，其余w[u]=0
    for (int v = 0; v < n; v++)
    {
        if (!vis[v] && G[u][v] != INF)
        {
            if (d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] + G[u][v];
                w[v] = w[u] + weight[v];
            }
            else if (d[u] + G[u][v] == d[v] && w[u] + weight[v] > w[v])	// 多条
                w[v] = w[u] + weight[v];
        }
    }

  • 求最短路径条数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for (int v = 0; v < n; v++)
    {
        if (!vis[v] && G[u][v] != INF)
        {
            if (d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] + G[u][v];
                num[v] = num[u];	// 仅一条时，遵循上个结点
            }
            else if (d[u] + G[u][v] == d[v])
                num[v] += num[u];	// 有多条不同的最短路通往v
        }
    }

使用Dij+dfs简化逻辑：

  1. 使用dij记录下所有最短路径

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    vector<int> pre[MAXV];

    // 在relaxing操作中
    for (int v = 0; v < n; v++)
    {
        if (!vis[v] && G[u][v] != INF)
        {
            if (d[u] + G[u][v] < d[v])
            {
                d[v] = d[u] + G[u][v];
                pre[v].clear();		// 因为最短路已换，前驱需清空
                pre[v].push_back(u);	// 添加新的前驱
            }
            else if (d[u] + G[u][v] == d[v])
                pre[v].push_back(u);	// 记录多个前驱
        }
    }

  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
    vector<int> pre[MAXV];
    vector<int> path, tempPath;
    int optValue;

    void dfs(int v, int curValue)
    {
        if (v == st)	// 到达起点，形成一条倒着的完整最短路
        {
            if (curValue 优于 optValue)	// 更新
    		{
    			optValue = curValue;
    			path = tempPath;
    			path.push_back(v);		// 别忘了添加起点
    		}
    		return;
        }
        
        tempPath.push_back(v);	// 加入临时的最短路径
        for (int i = 0; i < pre[v].size(); i++)
        {
            int u = pre[v][i];
            dfs(u, curValue + value[u][v]);		// 递归访问前驱结点，累计第二标尺的权值
        }
        tempPath.pop_back();	// 删除结点v，因为要记录其他最短路
        
    }

注意：

  • INF要用const int INF = 1e9定义，不要用#define，后者值为0，原因不明
  • 所有的min都要记得初始化

Bellman-Ford与SPFA

Bellman-Ford：

邻接表实现为$O(VE)$，思路如下：

进行V-1轮操作，每轮对所有边松弛

最后一轮再对所有边松弛，如果仍能松弛，说明有原点可达的负环，返回false；否则返回true；

1
2
3
4
5
6
7
8
9
10
11
12
13
d[s] = 0;	// 起点为0
for (int i = 0; i < n - 1; i++)
{
    for (each edge e[u][v])
        if (d[u] + e[u][v] < d[v])
        {
            d[v] = d[u] + e[u][v];
        }
}

for (each edge e[u][v])
    if (d[u] + e[u][v] < d[v])
        return false;

SPFA：

邻接表实现为$O(kE)$，从B-F算法优化而来，思路如下：

只有当某个顶点d[u]的值改变时，从它出发的邻接点v的d[v]才有可能改变

因此建立一个队列，每次松弛后，如果顶点不在队中，将其入队。若入队次数超过V-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
vector<Node> adj[MAXV];
int d[MAXV], num[MAXV];
bool inq[MAXV];

bool SPFA(int s)
{
    fill(d, d + MAXV, INF);
    // 原点入队
    queue<int> q;
    q.push(s);
    inq[s] = true; num[s]++; d[s] = 0;
    // 主体
    while (!q.empty())
    {
        // 取队首
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int j = 0; j < adj[u].size(); j++)
        {
            // relaxing
            int v = adj[u][v].v, dis = adj[u][v].dis;
            if (d[u] + dis < d[v])
            {
                d[v] = d[u] + dis;
                if (!inq[v])
                {
                    q.push(v);
                    inq[v] = true; num[v]++;
                    if (num[v] >= n)	// 有可达负环
                        return false;
                }
            }
        }
    }
    return true;
}

可以使用优先队列priority_queue进行优化

Floyd

全源最短路径算法，$O(n^3)$，n应限制在200以内

基本思想：枚举中介点k，使用k任意两个顶点进行松弛操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dis[MAXV][MAXV];

void floyd()
{
    fill(dis[0], dis[0] + MAXV * MAXV, INF);
    
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++);
        {
            for (int j = 0; j < n; j++)
            {
                // 松弛
                if (dis[i][k] != INF && dis[k][j] != INF
                   && dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
}

最小生成树MST

MST（Minimum Spanning Tree）

在给定无向图G中求一棵树T，T包含G中所有顶点，且边都来自G，满足整棵树边权之和最小

  • 作为树，MST有：边数=顶点数-1
  • MST不唯一，但边权之和一定为1
  • 一般给定一个根结点求最小生成树

Prim

复杂度$O(V^2)$，优先队列优化能达到$O(VlogV)$

基本思想：

  1. 集合S存放已访问结点，每次从V-S中选择与S距离最小的点u，将该距离最小的边加入MST，并将u加入S

  2. 令顶点u为中介，优化 所有u的邻接点 与 集合S 之间的最短距离

  3. 循环n次后，即得到MST

（Prim与Dij的思想几乎相同，区别只有：Prim松弛的是邻接点到集合S的距离，Dij松弛的是邻接点到起点之间的距离；在代码中体现为数组d[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
38
39
40
41
int G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV] = {false};

int prime(int s)
{
    int ans = 0;
    fill(d, d + MAXV, INF);
    d[s] = 0;
    
    for (int i = 0; i < n; i++)
    {
        int u = -1, minD = INF;
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && d[j] < minD)
            {
                u = j;
                minD = d[j];
            }
        }
        
        if (u == -1)
            return;
        vis[u] = true;
        ans += d[u];		// 累计MST的边权
        for (int v = 0; v < n; v++)
        {
            if (!vis[v] && G[u][v] != INF)	// 未访问过的邻接点
            {
                if (G[u][v] < d[v])		// 如果能松弛到S的距离
                {
                    d[v] = G[u][v];		
                    // 如果需要记录边，在这里记录，将d[v]和边u->v放入一个结构体中存储
                }
                    
            }
        }
    }
    return ans;
}

Kruskal

复杂度$O(ElogE)$，开销来自于边排序

基本思想：边贪心策略

​ 每次选择图中最小边权的边，如果加入不成环（边两端顶点在不同连通块中），就把边加入MST中

实现：使用并查集判断是否成环

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
// 边结构
struct Edge
{
    int u, v;
    int cost;
} E[MAXE];
// 边排序使用的比较函数
bool cmp(edge a, edge b)
{
    return a.cost < b.cost;
}
// 并查集
int fa[MAXV];
int findFather(int x)
{
    //...
}

int kruskal(int n, int m)	// n顶点数，m边数
{
    int ans = 0, nEdges = 0;
    // 并查集初始化
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    // 边排序
    sort(E, E + m, cmp);
    // 遍历所有边
    for (int i = 0; i < m; i++)
    {
        int faU = findFather(E[i].u);
        int faV = findFather(E[i].v);
        if (faU != faV)
        {
            fa[faU] = faV;		// 集合合并
            ans += E[i].cost;	// MST边权累加
            nEdges++;		// MST的边数累加
            if (nEdges == n - 1)	// 边数等于顶点数-1时，完成MST构建
                break;
        }
    }
    if (nEdges != n - 1)	// 无法连通
        return -1;		
    else
        return ans;
}

总结

  • prim和dij思想相近，都是不断优化d[]，复杂度与顶点数有关，适用于稠密图（边多点少）
  • kruskal使用边贪心策略，并查集判断是否成环，复杂度与边数有关，适用于稀疏图（边少点多）

拓扑排序

有向无环图（Directed Acyclic Graph， DAG）：有向、无环（任意点都无法通过边回到自身）

拓扑排序：将DAG图的所有顶点排成一个序列，如果存在边u->v，则序列中u一定在v之前

算法步骤：

  1. 定义队列Q，将所有入度为0的结点入队
  2. 取队首结点输出，删去所有从它出发的边，并令边到达的结点入度-1
  3. 重复直到队空。如果入过队的结点数目为N，则排序成功；否则图中有环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 邻接表实现
vector<int> G[MAXV];
int inDegree[MAXV];	// 入度

bool toplogicalSort()
{
    int num = 0;	// 记录加入拓扑序列的结点数
    queue<int> q;
    
    for (int i = 0; i < n; i++)
    {
        if (inDegree[i] == 0)
            q.push(i);
    }
    
    while (!q.empty())
    {
        // 取队首
        int u = q.front();
        q.pop();
        // 访问：输出结点，或加入数组
        printf("%d ", u);
        num++;		// 累计加入拓扑序列的结点个数
        
        // 更新邻接点的入度、入度为0的结点入队
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            inDegree[v]--;
            if (inDegree[v] == 0)
                q.push(v);
        }
        G[u].clear();	// 清空出边，如无必要可不写
    }
    
    return (num == n);	// 加入拓扑序列的点数为n，说明无环
}

关键路径

AOV（Activity On Vertex）网：顶点活动网，用顶点表示活动，边集表示活动间优先关系的有向图

AOE（Activity On Edge）网：边活动网，带权边集表示活动，顶点表示事件的有向图。边权表示活动所需时间

image-20210313210932268

源点：入度为0的点，表示起始事件；

汇点：出度为0的点，表示终止事件

关键路径：AOE网中的最长路径，关键路径上的活动称为关键活动，关键路径的长度等于工程最短完成时间

  • 最长？从路径长度上看，选择不能拖延的活动，组成的就是最长的路径，比较对象是选择其他路径的方案
  • 最短？从时间角度看，不能拖延的活动按照时间完成就是最短的时间，比较对象是活动中有拖延的方案

AOE网实际是DAG图

求解关键路径的问题即 求解DAG图中最长路径

四个关键的数组：

数据 定义 计算 图示
e[r] 活动$a_r$的最早开始时间 e[r] = ve[i] image-20210313212311647
l[r] 活动$a_r$的最迟开始时间 l[r] = vl[j] - length[r] image-20210313212311647
（活动r最迟开始时间+活动时间=事件j最迟发生时间）
ve[i] 事件$i$的最早发生时间 ve[j] = max{ve[ip] + length[rp]} image-20210313212537246
（所有前驱事件发生、活动完成之后，Vj才能被激活，最后完成的是max）
vl[i] 事件$i$的最迟发生时间 vl[i] = min{vl[jk] - length[rk]} （图中用了逆拓扑展示）
image-20210313213046547
（事件i的最迟发生，加上活动时间，不能影响到任何后继事件，最先影响到的是min）

编码：

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
// 拓扑排序，并计算ve
stack<int> topOrder;	// 使用栈是为了获取逆拓扑序列
bool toplogicalSort()
{
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (inDegree[i] == 0)
            q.push(i);
    }
    
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        topOrder.push(u);	// 拓扑序列入栈
        // 遍历邻接点
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i].v;
            inDegree[v]--;
            if (inDegree[v] == 0)
                q.push(v);
            // 使用ve[u]更新所有后继结点v的最早开始时间ve[v]
			// 本质是松弛操作（反向）
            if (ve[u] + G[u][i].w > ve[v])
                ve[v] = ve[u] + G[u][i].w;
            
        }
    } 
    return (topOrder.size() == n);	// n个结点进入序列才为成功
}

int criticalPath()
{
    memset(ve, 0, sizeof(ve));
    // 拓扑排序的过程中计算ve
    // 如果不是DAG图，返回-1
    if (!toplogicalSort())	
        return -1;
    
    // 获取汇点的最早发生时间
    // 汇点i顶是最后发生的事件，所以一定ve最大
    int maxLength = 0;
    for (int i = 0; i < n; i++)
    {
        if (ve[i] > maxLength)
            maxLength = ve[i];
    }
    fill(vl, vl + n, maxLength);	// 初始化事件最晚发生时间
    
    // 使用逆拓扑序列，更新事件的vl数组
    while (!topOrder.empty())
    {
        int u = topOrder.top();
        topOrder.pop();
        // 使用u的后继结点的来更新u的最迟发生时间vl[u]
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i].v;
            if (vl[v] - G[u][v].w < vl[u])
                vl[u] = vl[v] - G[u][v].w;
        }
    }
    
    // 计算关键路径
    for (int u = 0; u < n; u++)
    {
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i].v, w = G[u][i].w;
            // 计算活动最早开始时间e和最迟开始时间l
            int e = ve[u], l = vl[v] - w;
            if (e == l)		// 如果e==l，说明活动u->v（即这条边）是关键活动
                nextPath[u] = v; 
        }
    }
    // 找出源点
    int s;
    for(int i = 0; i < n; i++)
	{
        if(ve[i] == 0)
		{
            s = i;
            break;
        }
    }
    // 输出路径
    while (nextPath[s] != s)
    {
    	printf("(%c,%c) ", vertices[s], vertices[nextPath[s]]);
    	s = nextPath[s];
	}
    
    return maxLength;	// 关键路径长度
}

动态规划 DP

  • 状态：记录当前信息；状态转移方程：根据之前的状态计算当前状态值
    如何设计二者是DP的核心
  • 最优子结构：问题最优解可以由子问题的最优解构造出来
  • 状态的无后效性：当前状态一旦确定，不再改变。只有当前状态能影响下一状态，历史信息只能通过已有状态影响决策，而不直接参与决策

分治与DP

  • 同：都分解为子问题
  • 异：分治的子问题不重叠，DP的重叠

贪心与DP

  • 同：都要求最优子结构
  • 异：贪心壮士断腕，直接选择一个子问题往下求解；DP总会考虑所有子问题，选择继承能得到最优解的一个

最大连续子序列

给定数字序列$A_1, …, A_n$，求$i, j$使$A_1 + … + A_j$最大，输出这个和

暴力：$O(n^2)$，DP：$O(n)$

状态：dp[i]表示以A[i]为结尾的连续序列最大和

状态转移方程：dp[i] = max(A[i], dp[i-1] + A[i])

  • 一个元素：A[i]
  • 多个元素：前面最大和dp[i-1]加上当前A[i]
1
2
3
4
dp[0] = A[0];
for (int i = 1; i < n; i++)
    dp[i] = max(A[i], dp[i-1] + A[i]);
// max(dp[1], ..., dp[n-1])即为结果

最长不下降子序列 LIS

LIS（Longest Increasing Sequence）

给定一个数字序列，子u最长的非下降子序列长度（可以不连续）

暴力：$O(2^n)$， DP：$O(n^2)$

状态：dp[i] 表示以A[i]结尾的LIS长度

状态转移方程：dp[i] = max{1, dp[j] + 1}（j=1, 2,…, i-1 && A[j] <= A[i]）

  • A[i]跟在A[j]后面，LIS长度+1
  • A[i]自己成为一条新的LIS，长度为1
1
2
3
4
5
6
7
8
9
10
11
for (int i = 0; i < n; i++)
    dp[i] = 1;
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < i; j++)
    {
        if (A[j] <= A[i] && dp[j] + 1 > dp[i])
            dp[i] = dp[j] + 1;
    }
}
// asn = max(dp[0],...dp[n-1])

最长公共子序列 LCS

给定两个字符串A和B，求字符串s，使s使A和B的最长公共部分（可以不连续）

复杂度：$O(nm)$

状态：dp[i][j] 表示A的i号位和B的j号位之前的LCS长度

状态转移方程：
image-20210315144750560

  • 如果A[i]==B[i]，LCS长度为增加1位
  • 否则，继承dp[i-1][j]和dp[i][j-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
char A[MAXN], B[MAXN];
int dp[MAXN][MAXN], p[MAXN][MAXN];
const int LU = 0, U = 1, L = 2;

int LCS()
{
    gets(A + 1);	// 从下标1开始读入
    gets(B + 1);
    int lenA = strlen(A + 1);
    int lenB = strlen(B + 1);
    
    for (int i = 0; i <= lenA; i++)
    	dp[i][0] = 0;
    for (int j = 0; j <= lenB; j++)
        dp[0][j] = 0;

    for (int i = 1; i <= lenA; i++)
    {
        for (int j = 1; j <= lenB; j++)
        {
            if (A[i] == B[j])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
             	p[i][j] = LU;		// 左上
            }
                
            else if (dp[i - 1][j] > dp[i][j - 1])
            {
                dp[i][j] = dp[i - 1][j];
                p[i][j] = U;		// 上
            }
            else
            {
                dp[i][j] = dp[i][j - 1];
                p[i][j] = L;	// 左
            }
                
        }
    }
    return dp[lenA][lenB];
}
// 打印最长公共子序列，printLCS(lenA, lenB)
void printLCS(int i, int j)
{
    if (p[i][j] == LU)
    {
        printLCS(i - 1, j - 1);
        putchar(A[i]);
    }
    else if (p[i][j] == U)
        printLCS(i - 1, j);
    else
        printLCS(i, j - 1);
}

最长回文串

复杂度：$O(n^2)$

状态：dp[i][j]表示S[i]到S[j]是否是回文串，是为1，不是为2

状态转移方程：
image-20210315152211196

  • 若S[i]==S[j]，则只要S[i+1]至S[j-1]是回文串，S[i]至S[j]就是，因此继承dp[i+1][j-1]
  • 若S[i]!=S[j]，肯定不是回文串，dp[i][j]=0

采用区间dp实现，即两层循环，外层枚举子串长度L，内层枚举初始位置（左端点）i，右端点=i+L-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
int ans = 0;	// 最大长度
// 边界
for (int i = 0; i < len; i++)
{
    dp[i][i] = 1;
    if (i < len - 1 && S[i] == S[i+1])
    {
        dp[i][i+1] = 1;
        ans = 2;
    }   
}

for (int L = 3; L <= len; L++)
{
    for (int i = 0; i + L - 1 < len; i++)
    {
        int j = i + L - 1;
        if (S[i] == S[j] && dp[i+1][j-1] == 1)
        {
            dp[i][j] = 1;
            ans = L;
        }
    }
}
return ans;

DAG最长路

也即求关键路径，两个问题：

  1. 整个DAG中的最长路径
  2. 固定终点，求DAG的最长路径

整个DAG中的最长路径

状态：dp[i]表示从i号结点出发能获得的最长路径长度

状态转换方程：dp[i] = max{dp[j] + length[i->j]} (i,j)∈E

  • 因为是用后继结点j更新结点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
38
39
40
41
42
43
44
45
46
int DP(int i)
{
    if (dp[i] > 0)
        return dp[i];
    
    for (int j = 0; j < n; j++)
    {
        if (G[i][j] != INF)
        {
            int temp = DP(j) + G[i][j];
            if (temp > dp[i])
            {
                dp[i] = temp;
                pathNext[i] = j;	// 记录后继结点
            }
        }
    }
    return dp[i];
}

void criticalPath()
{
    // 初始化dp[i]=0, 结点后继为本身
    for (int i = 0; i < n; i++)
    {
        dp[i] = 0;
        pathNext[i] = i;
    }
    // dp计算最长路径
    int ans = 0, s;
    for (int i = 0; i < n; i++)
    {
        if (DP(i) > ans)
        {
           ans = dp[i]; 	// 更新最长路径
            s = i;		// 起始点
        }  
    }
    // 打印路径
    printf("%d", s);
    while (pathNext[s] != s)
    {
        s = pathNext[s];
        printf("->%d", s);
    }
}

上述代码还自动实现了取字典序最小的路径（因为是按结点从小到大遍历）

固定终点的DAG最长路径

状态：dp[i]表示从i出发到终点T的最长路径长度

状态转移方程：dp[i] = max{dp[j] + length[i->j]} (i,j)∈E

  • 与前一个问题的方程相同，区别在对边界的定义：初始化所有dp[i]=-INF来表达不可达，dp[T]=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
int DP(int i)
{
    if (vis[i])	// 已访问过才能取值
        return dp[i];
    
    vis[i] = true;
    for (int j = 0; j < n; j++)
    {
        if (G[i][j] != INF)
        {
            dp[i] = DP(j) + G[i][j];
        }
    }
    return dp[i];
}

int criticalPath(int S, int T)
{
    // 初始化dp[i]=-INF, dp[T]=0
    for (int i = 0; i < n; i++)
    {
        dp[i] = -INF;
    }
    dp[T] = 0;
    return DP(S);		// 返回从起点S到终点T的关键路径长度
}

path选择以及最小字典序方案和上一个问题相同

总结：

  • 不规定终点的DAG关键路径，dp[i]=0有两层意思：
    1）如果是出度为0的点，从它出发的关键路径长度为0
    2）出度不为0的点，表示未更新dp[i]，因此进入邻接点的遍历
  • 规定终点的关键路径问题，不能初始化所有dp[i]=0，因为并非所有点都可达T，所以初始化未-INF，并利用vis数组记录dp[i]是否更新

  • 不关心起点，因为dp[i]已经具有这层意思。
    对于规定起点S的问题，返回DP(S)即可，
    对于未规定起点的问题，取dp[i]最大的结果返回

  • 用DAG的思路解决矩形嵌套问题：每个矩形看成一个顶点，嵌套关系视为有向边，边权为1，于是就能转换为DAG最长路问题

背包问题

多阶段动态规划问题：:arrow_right:问题可以描述成若干有序阶段，每个阶段（多个状态）只与上个阶段的状态有关

01背包就是多阶段DP问题

01背包

DP：$O(nV)$

n件物品，容量V的背包，每件物品重w[i]，价值c[i]，问如何选取物品使背包内物品总价值最大（每个物品1件）

  1. 状态与最优子结构
    dp[i][v]表示选择前i项物品装入容量v的背包的最大价值
    • 不放第i件物品：dp[i][v]=dp[i-1][v]
    • 放第i件物品：dp[i][v] = dp[i-1][v-w[i]]+c[i]

  2. 状态转移方程
    image-20210316082007789

  3. 自底向上
    边界dp[0][v]=0（0件物品放入任何背包容量的价值都为0）
    枚举i<-1 to n，v<-w[i] to V

编码：

1
2
3
4
5
for (int i = 1; i <= n; i++)
{
    for (int v = w[i]; v <= V; v++)
        dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - w[i]] + c[i]);
}

优化空间复杂度：

上一阶段的状态，用于计算当前阶段的状态后，就不再使用，因此可以用滚动数组，化为一阶数组表示当前状态

image-20210316084246846

注意，自底向上的遍历必须逆序，因为如果正序遍历，dp[v]使用的dp[v-w[i]]是i-1阶段的状态，会造成错误。逆序保证了计算第i阶段的状态时使用的都是i-1阶段的状态

1
2
3
4
5
for (int i = 1; i <= n; i++)
{
    for (int v = V; v >=w[i]; v--)
        dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
}

总结：

  • 如果能划分阶段，可以尝试将阶段作为状态，将数组降一维
  • 如果设计的状态不满足无后效性，可以尝试将状态升维（多个阶段，每个阶段多个状态）来表达相应信息

完全背包问题

与01背包的区别在于，每个物品有无穷件（可选择多次）

  1. 状态与最优子结构
    dp[i][v]表示选择前i项物品装入容量v的背包的最大价值

    • 不放第i件物品：dp[i][v]=dp[i-1][v]
    • 放第i件物品：dp[i][v] = dp[i][v-w[i]]+c[i]
      注意此处转移到了第i阶段而非i-1阶段，因为放了第i件物品后还可以继续放

  2. 状态转移方程
    image-20210316091304532|
    优化版：
    image-20210316091330893

  3. 自底向上
    对于优化版：边界：初始化所有dp[v]为0（即表示dp[0][v]=0）
    正向枚举v<-w[i] to V，因为求解dp[i][v]总是需要它左边的dp[i][v-w[i]]，而上方的dp[i-1][v]在计算完后才会覆盖
    image-20210316091619664
1
2
3
4
5
for (int i = 1; i <= n; i++)
{
    for (int v = w[i]; v <= V; v++)
        dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
}

总结

  • 当题目与序列或字符串A有关时，可以考虑状态设计：
    1. 令dp[i]表示以A[i]结尾（或开头）的xxx
    2. 令dp[i]表示以A[i]至A[j]区间的xxx

  • 当题目包含某种”方向“的意思时，状态需要几个维度来表示，对每一维用以下描述

    1. 恰好为i
    2. 前i

    令dp数组表示恰好为i（或前i）的xxx

大多数情况都可以把DP问题看作一个有向无环图（DAG），结点是状态，边是状态转移方向，辅助理解

KMP算法

给出两个字符串text和pattern，判断pattern是否是text的子串

暴力法枚举起始点$O(nm)$，使用KMP能达到$O(n+m)$

求解next数组

  • next[i]定义：
    使子串s[0...i]的前缀s[0...k]和后缀s[i-k...i]相等的最大的k（前后缀长度为k+1），也即最长相等前后缀的前缀最后一位的下标

    image-20210316125810982
    上框下划线画出匹配的前后缀，下框的第一行为前缀，第二行为后缀

  • 递推求解next[i]：
    令j=next[i-1]

    • 若s[i] == s[j+1]，最长相等前后缀可以扩展，长度+1，即next[i]=j+1

      image-20210316125722792

    • 若s[i] != s[j+1]，前后缀匹配失败，相等前后缀无法达到那么长，因此需要缩短一点。需要找出一个j'，使得

      • 1） s[i] == s[j'+1]成立
      • 2） s[0...j']（下图3的~）是s[i-j-1...i-1]（下图3和~在一个框的上方的子串）的后缀
        因为s[i-j-1..i-1] == s[0..j]（由j=next[i-1]的意义决定，j是s[0..i-1]的最长前后缀匹配的前缀最后一位下标），所以只需满足s[0..j']是s[0..j]的后缀
        从下面图片来理解就是：j=next[4]=2，需要找一个串s[0..j']，使得它是s[2..4]="aba"的后缀（这样才能匹配成功），因为s[2..4] == s[0..2]（因为next[4]=2），所以也即s[0..j']需满足是s[0..2]后缀
      • 3） s[0...j']是s[0...j]的前缀（自动满足，因为是在0..j里找j'）
      • 4）j'尽可能大

      image-20210316131651669

      上面的要求2）3）4），正好就是next[j]的定义：s[0..j]最长相等前后缀的前缀下标j'，因此只需让j'=next[j]，判断s[i]==s[j'+1]是否成立，不成立继续回退，直到j'=-1
      image-20210316133601904

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 求解长度为len的字符串s的next数组
    void getNext(char s[], int len)
    {
        int j = -1;
        next[0] = -1;
        // 1. 让i在1~len-1范围内遍历
        for (int i = 1; i < len; i++)
        {
            // 2.不断令j=next[j]，直到j回退到-1，或满足s[i]==s[i+1]
            while (j != -1 && s[i] != s[j+1])
                j = next[j];
            
    		// 3. 若s[i]==s[j+1]，则next[i]=j+1，否则next[i]=j
            if (s[i] == s[j+1])
                j++;
            next[i] = j;
        }
    }

KMP算法

令i指向text的欲比较位，j指向pattern已被比较的最后一位

  • 若text[i] == pattern[j+1]，说明匹配成功，i、j自增，继续比较

  • 若text[i] != pattern[j+1]，匹配失败，需要考虑j回退到哪，位置要满足以下条件：

    • 1）text[i] == pattern[j' + 1]成立
    • 2）pattern[0..j']仍然与text相应位置处于匹配状态，即pattern[0..j']是text[i-1-j..i-1]的后缀，由于之前匹配的结果有text[i-1-j..i-1] == pattern[0..j]，因此只需满足pattern[0..j']是pattern[0..j]的后缀
    • 3）pattern[0..j']是pattern[0..j]的前缀（自动满足，因为是回退）
    • 4）j'尽可能大

    条件2）3）4）正是数组next[j]的定义，因此只需不断令j'=next[j]，直到满足条件1）或j'=-1为止。（逻辑与next数组的求解几乎一致）

    从这个角度来看，next数组的含义就是当j+1位失配时，j应该回到的位置

image-20210316141313149

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool KMP(char text[], char pattern[])
{
    int n = strlen(text), m = strlen(pattern);
    getNext(pattern, m);
    int j = -1;
    // 1. 遍历文本串text
    for (int i = 0; i < n; i++)
    {
        // 2. 不断令j=next[j]，直到j回退到-1，或text[i]==pattern[j+1]为止
        while (j != -1 && text[i] != pattern[j+1])
            j = next[j];
        // 3. 若匹配，往前一位
        if (text[i] == pattern[j+1])
            j++;
        // 4. 若j达到pattern尾，说明是子串
        if (j == m - 1)
            return true;
    }
    return false;
}

统计文本串text中pattern的出现次数（不是子串个数，如text=”ababab”中，pattern=”abab”出现了2次）

思路：

完全匹配一次pattern后，j需回退一定距离，使得不漏解且效率最高。由于next[j]的定义是最长前后缀匹配的前缀最后一位，完全匹配时text[i-j..i] == pattern[0..j], j=m-1，所以令j=next[j]，在next[j]之前的位置都已完成匹配，省去了许多无意义的比较

image-20210316141352442

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int KMP(char text[], char pattern[])
{
    int n = strlen(text), m = strlen(pattern);
    getNext(pattern, m);
    
    int j = -1; ans = 0;
    for (int i = 0; i < len; i++)
    {
        while (j != -1 && text[i] != pattern[j+1])
            j = next[j];
        if (text[i] == pattern[j+1])
            j++;
        if (j == m - 1)
        {
            ans++;
            j = next[j];	// 关键一步
        }
    }
    return ans;
}

总结

  • 计算next数组实际上是pattern自我匹配的过程
  • KMP的关键是j回退的位置j=next[j]，实质就是回到一个已知匹配的长度，从而省去从头开始比较的开销。容易模糊的地方是如何证明这个回去的位置是有效而且最优的，可以多看看上面的解释，思路就是递推求解代替逐项匹配
  • $O(n+m)$的开销：i和j的变化是$O(n)$的，计算next数组的开销是$O(m)$

其他

中缀表达式计算

1）中缀转换为逆波兰（后缀表达式）：

（使用队列存储）

  1. 如果是数字，直接入队

  2. 如果是运算符op：如果运算符栈空，压入运算符栈，否则与栈顶比较优先级（用map记录优先级）：
    只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “

    1
    2
    3
    4
    5
    6
    while(栈非空 && 栈顶 != '(' && op小于或等于栈顶)
    {
        // 栈顶入队
        // 弹栈
    }
    // 表达式中的op压栈

  3. 如果遇到一个右括号，则将栈元素弹出（入队），将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。

  4. 表达式扫描结束后，若运算符栈非空，从栈顶依次入队

2）逆波兰表达式运算：

（由队首依次出队）

  1. 如果是数字，压栈
  2. 如果是运算符，取栈顶两个数字，运算，将结果压栈
  3. 队列扫描结束后，栈顶数字即最终结果

3）中缀表达式直接计算：
（使用数字栈和运算符栈）

  1. 如果是数字，压栈
  2. 如果是运算符，同1），不过弹栈时，取数字栈顶两个元素运算后压栈，而非入队
  3. 同1），弹栈时运算而非入队

C语言变长参数函数写法

使用头文件<stdarg.h>实现，下面为用到的四个宏：

  • va_list：声明指向变长参数的指针ap
  • va_start(ap, arg)：用于初始化变长参数指针ap的位置，arg为最后一个固定参数
  • va_arg(ap, type)：ap传入变长参数指针，type为参数类型。函数返回ap当前指向的类型为type的参数，并将ap指向参数列表的下一个参数
  • va_end(ap)：置ap为空指针

变长参数函数的参数中，先填写若干个固定参数，然后在最后一个固定参数的逗号后方添加3个点，表示变长参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdarg.h>
#include <cstdio>

void test(int num, ...)
{
	va_list ap;
	va_start(ap, num);
	char* str;
	
	for (int i = 0; i < num; i++)
	{
		str = va_arg(ap, char*);
		printf("%s\n", str);
	}
	va_end(ap);
}

int main()
{
	test(3, "hello", "fxxking", "world");
}

Debug思路

  • 注意考虑边界情况，如0、有质数的题考虑1
  • 没有编码错误的情况下，找逻辑错误（代码是否和题目逻辑一致），着重检查循环里的数组下标i,j,k
  • 注意浮点数精度：float能保证6位，double能保证到15位。有时float错了可能double能过
  • 可能没有考虑多组输入
  • 格式问题，有些题目可能输出点个数为0时需输出空行
  • 无法调试可能的原因：
    • 内存爆了，减小MAXN
    • 添加查看了STL容器
  • 声明const char []型数据时，一定要检查后面有没有添加'\0'，否则可能会出现本地没问题但交上去WA的情况。比如：const char ONE[2] = {'1', '\0'};能过，但const char ONE[1] = {'1'};在Linux环境下会出现怪数，但windows下结果正常
  • 同阶时间复杂度的算法，实际表现可能有很大差异。比如O(nlogn)和O(2nlog(2n))。当RE时，可能其他同阶算法能过
  • sort的cmp函数中如果使用return a >= b可能会有段错误（原因不明），改用return a > b，不影响语义
  • 多组输入，记得对每个用到的数据结构进行初始化

杂

  • 字符转数字

    1
    2
    3
    num = 0;
    for (int i = 0; i < len; i++)
    	num = num * 10 + str[i] - '0';

  • 注意先找规律，n很大的不要一上来就递归DP，很容易超时。有时可能往简单想能做出来

  • int的范围[-2147483648, 2147483647]，10个0就无法支持了，一般取INF=1e9

  • ceil()：向上取整；floor()：向下取整；round()：四舍五入；三者都返回double值

  • 万能库：include <bits/stdc++.h>

  • long和int都是4字节，long long才是8字节

  • 21！就超过了long long的范围

  • cin和cout远比scanf和printf花费时间多，能不用尽量不用

  • 运行时限为1s，算法复杂度不能超过百万级，也即不能超过一千万
    比如$O(n^2)$，n应<=3000

  • cin的多组输入：while(cin >> x)，cin在读入EOF时返回0

  • 浮点数比较，在经过大量计算后应考虑误差

    1
    2
    3
    4
     #include <math.h>

    const double eps = 1e-8
    #define Equ(a, b) (fabs((a)-(b))<(eps))

    大于、小于、大于等于，以及sqrt、asin、cos等也需要考虑

  • C的空指针为NULL，c++11引入nullptr

  • scanf("%c")会可以读入空格，需要考虑

  • 下标的计算（i、j的加加减减之类的）从实体加减考虑，不要考虑加减位置

  • C语言中整型最大值和最小值的宏

    1
    2
    3
    4
    #include <limits.h>

    printf("%d ", INT_MAX);	//2147483647
    printf("%d ", INT_MIN);	//-2147483648

  • 命令行输入

    1
    2
    3
    4
    5
    6
    int main( int argc, char *argv[ ])
    {
    	int i;
    	for(i=1; i<argc; i++)
        	printf(“%s%c”, argv[i], (i< argc-1)? ' ': '\n');
    }

发表于 分类于 Valine：

环境

OS：Ubuntu 16.04LTS

软件：ettercap, driftnet

1
2
$ sudo apt-get install ettercap-graphical 
$ sudo apt-get install driftnet

ps：使用虚拟机vmware+kali体验更好

抓包

  1. $sudo ettercap -G打开ettercap图形化界面
  2. Sniff->Unified sniffing->wlp2s0（无线网卡）
  3. Host->scan for hosts，扫描连接在同一网段上的设备
  4. 设备IP地址Add to Target 1；路由器IP（通常是最后一位为1）Add to Target 2（注意不要反了，否则可能导致宽带认证错误，上不了网，只能打电话找运营商清除一下之前的缓存）
  5. Mitm（中间人攻击）->Arp poisoning->Sniff remote connections->ok，至此，设备与路由器的通信会经过本主机，因此可以截获报文
  6. Start->Start sniffing开始监听，View->View Connections查看截获的报文

图片监视

监听无线网卡：

1
$ sudo driftnet -i wlp2s0

会弹出一个图片预览框，截取设备访问的图片

driftnet其他参数：

  • -i 监听网卡
  • -b 声音提醒
  • -a 保存图片（这样的话图片不会显示在窗口）
  • -d 图片保存目录，例：driftnet -i wlan0 -b -a -d /pic

总结

经过本人的实验，可以抓取到微信朋友圈的视频帧、图片（很少），以及公众号中浏览的一些图片，原因可能是大部分图片还是经过加密传输的。但即使如此，还是见识到了连接在同一wifi上造成的信息泄露。

参考

发表于 分类于 Valine：

题目描述

约瑟夫环问题

标准做法 递归 $O(n)$

由于问题是求0到n-1里最后剩下的数字，所以问题也可以转换为安全数字的序号。对问题建模，令f(n, m)为问题的答案，即最终安全位置的序号。最开始，我们要删除的是第m%n个元素，之后，序列长度变为n-1，然后从第m%n位开始往后数。剩下的n-1长度的序列从第m%n位开始，只要往后数f(n-1, m)位就能达到安全位置，所以(m%n+f(n-1,m))%n即为所求。(m%n+f(n-1,m))%n = (m+f(n-1, m)%n

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    int f(int n, int m) {
        if (n == 1)
            return 0;
        int x = f(n - 1, m);
        return (m + x) % n;
    }
public:
    int lastRemaining(int n, int m) {
        return f(n, m);
    }
};

标准做法 迭代/DP $O(n)$

由上面的递归式，就可以得到DP所需的状态转移方程

只有一个状态转换量，所以可以用简单变量替代

在i=1时，也就是长度为1的序列，安全位置就是0，即f1 = 0

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i)
            f = (m + f) % i;
        return f;
    }
};

总结

  • 模拟约瑟夫环的删除过程会超时
  • 这种类似归纳法解决问题的逻辑很巧妙，希望能掌握下来

参考