收集常见题目和代码

1、c++ 快速入门

两数之间的交换：

c++

void swap2(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}
void swap2(int& a, int& b) {
	a = a + b;
	b = a - b;
	a = a - b;
}
void swap2(int& a, int& b) {
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}

void swap2(int* a, int* b) {
	*a = *a + *b;
	*b = *a - *b;
	*a = *a - *b;
}

1.1 数组

1.1.1 BubbleSort

c++

#include <vector>
#include<iostream>
using namespace std;
void BubbleSort(int *a) {
	int i, j;
	for (i = 0; i < 5 - 1; i++) {
		for (j = 0; j < 5 - i - 1; j++) {
			if (a[j] > a[j + 1]) {
				a[j] = a[j] + a[j + 1];
				a[j + 1] = a[j] - a[j + 1];
				a[j] = a[j] - a[j + 1];
			}
		}
	}
}
int main() {
	int a[5];
	int i;
	for (size_t i = 0; i < 5; i++)
	{
		cin >> *(a + i);
	}
	BubbleSort(a);
	for (size_t i = 0; i < 5; i++)
	{
		cout << *(a + i) << "\t";
	}
	return 0;
}

1.1.2 `memset`用法

头文件需要添加#include<string.h>

格式：

memset(数组名, 值, sizeof(数组名))

示例：

c++

#include<string.h>
#include<stdio.h>
int main() {
	int a[5] = { 1, 3, 4, 6, 7 };
	memset(a, 0, sizeof(a));
	for (size_t i = 0; i < 5; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	memset(a, -1, sizeof(a));
	for (size_t i = 0; i < 5; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	memset(a, 1, sizeof(a));
	for (size_t i = 0; i < 5; i++)
	{
		printf("%d ", a[i]);
	}
}

赋值为0， -1的时候常用，其他的值复制会存在问题

1.1.3 字符串数组

1、scanf 对字符类型有%c 和%s 两种格式，其中%c 用来输入单个字符，%s 用来输入一个字符串并存在字符数组里。%c格式能够识别空格跟换行并将其输入，而%s通过空格或换行来识别一个字符串的结束。

2、getchar 和 putchar 分别用来输入和输出单个字符

3、gets 用来输入一行字符串（注意： gets 识别换行符\n 作为输入结束，因此 scanf 完一个整数后，如果要使用 gets，需要先用 getchar 接收整数后的换行符），并将其存放于一维数组（或二维数组的一维）中； puts 用来输出一行字符串，即将一维数组（或二维数组的一维在界面上输出，并紧跟一个换行。

1.1.4 sscanf 和 sprintf 用法

sscanf 可以表示为 scanf(screen, "%d", &n)

sprintf 可以表示为 printf(screen, "%d", n)

可以发现， scanf 的输入其实是把 screen 的内容以"%d"的格式传输到 n 中（即从左至右），而 printf 的输出则是把 n 以"%d"的格式传输到 screen 上（即从右至左）。

c++

#include<string.h>
#include<stdio.h>
int main() {
	int n, m;
	char str[100] = "465";
	sscanf(str, "%d", &n);
	printf("%d\n", n);
	m = 56545;
	sprintf(str, "%d", m);
	printf("%s", str);
	return 0;
}
/*
465
56545
*/

除此之外，还可以进行复杂的格式输入和输出。比如：

sscanf

c++

#include<stdio.h>
int main() {
	int n;
	double db;
	char str[100] = "2048:3.14,jldas", str2[10];
	sscanf(str, "%d:%lf,%s", &n, &db, str2);
	printf("%d, %f, %s", n, db, str2);
	return 0;
}
//2048, 3.140000, jldas

sprintf

c++

#include<stdio.h>
int main() {
	int n = 12;
	double db = 3.1415;
	char str[100], str2[100] = "good";
	sprintf(str, "%d:%.2f,%s", n, db, str2);
	printf("str = %s \n", str);
	return 0;
}
//str = 12:3.14,good

1.2 结构体

结构体也有构造函数

如：

c++

struct studentInfo {
	int id;
	char gender;
	// 构造函数；无参构造
	studentInfo(){}
	// 构造函数 初始化gender
	studentInfo(char _gender) {
		gender = _gender;
	}
	// 构造函数 初始化gender 和 id
	studentInfo(int _id, char _gender) {
		id = _id;
		gender = _gender;
	}
};

注：

有参构造可以简写，如：

c++

studentInfo(int _id, char _gender) {
	id = _id;
	gender = _gender;
}

可简写为：

c++

	studentInfo(int _id, char _gender) : id(_id), gender(_gender) {}

1.3 补充

1.3.1 两个浮点数比大小

c++

#include<stdio.h>
#include<math.h>
// 定义误差偏移量
const double eps = 1e-8;
// 圆周率 派 $\pi$
const double Pi = acos(-1.0);
// 等于
#define Equ(a,b) ((fabs((a) - (b))) < (eps))
// 大于
#define More(a,b) (((a) - (b)) > (eps))
// 小于
#define Less(a,b) (((a) - (b)) < (-eps))
// 大于等于
#define MoreEqu(a,b) (((a) - (b)) > (-eps))
// 小于等于
#define LessEqu(a,b) (((a) - (b)) < (eps))

2、算法初步

2.1 计算两个日期之间的天数

计算两个日期之间相差的天数
输入示例：20250501 20250629
输出示例：2025 5 1 2025 6 29 Total Days: 60

c++

#include<stdio.h>
int month[13][2] = {
		{0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31},
};
bool isLeap(int year) {
	return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
int main() {
	char time1[8];
	int y1, m1, d1;
	char time2[8];
	int y2, m2, d2;
	while (scanf("%s\n%s", time1, time2) != EOF) {
		sscanf(time1, "%4d%2d%2d", &y1, &m1, &d1);
		sscanf(time2, "%4d%2d%2d", &y2, &m2, &d2);
		int count = 1;
		printf("%d %d %d\n", y1, m1, d1);
		printf("%d %d %d\n", y2, m2, d2);
		while (y1 < y2 || m1 < m2 || d1 < d2) {
			d1++;
			if (d1 == month[m1][isLeap(y1)] + 1) {
				m1++;
				d1 = 1;
			}
			if (m1 == 13) {
				m1 = 1;
				y1++;
			}
			count++;
		}
		printf("Total Days: %d", count);
	}
	return 0;
}
/*
* 计算两个日期之间相差的天数
* 输入示例：20250501 20250629
* 输出示例：2025 5 1 2025 6 29 Total Days: 60
*/

改进：

c++

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
// 日期差值
// 平年和闰年的每个月的天数
int month[13][2] = {
	{0, 0},{31, 31}, {28, 29}, {31, 31} , {30, 30}, {31, 31}, {30, 30},
	{31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30},{31, 31}
};

// 判断是否是闰年
int isLeap(int year) {
	return (year % 400 == 0) || (year % 100 != 0 && year % 4 == 0) ? 1 : 0;
}
// 计算两个日期之间的天数差
int dateDifference(int time1, int time2) {
	int y1, m1, d1;
	int y2, m2, d2;
	if (time1 > time2) {
		swap(time1, time2);
	}
	y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
	y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
	int ans = 1;// 记录结果
	while (y1 < y2 || (y1 == y2 && m1 < m2)) {
		
		ans += month[m1][isLeap(y1)];
		m1++;
		if (m1 == 13) {
			y1++;
			m1 = 1;
		}
	}
	ans = ans + d2 - d1;
	return ans;
}
int main() {
	int time1, y1, m1, d1;
	int time2, y2, m2, d2;
	while (scanf("%d%d", &time1, &time2) != EOF) {
		printf("ans = %d\n", dateDifference(time1, time2));
	}
	return 0;
}
/*
输入样例：
20130101
20130105
*/

2.3 `sort`函数的使用

用法：

sort(首元素地址（必填）,尾元素地址的下一个地址（必填）, 比较函数（非必填）)

示例：

c++

#include<stdio.h>
#include<algorithm>
using namespace std;
int main() {
	int a[6] = {9, 4, 2, 5, 6, -1};
	sort(a, a + 4);
	for (int i = 0; i < 6; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	sort(a, a + 6);
	for (int i = 0; i < 6; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}
/*
* 2 4 5 9 6 -1
* -1 2 4 5 6 9
*/

加入了比较函数：

c++

#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a, int b) {
	return a > b;
}
int main() {
	int a[6] = {9, 4, 2, 5, 6, -1};
	sort(a, a + 4, cmp);
	for (int i = 0; i < 6; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	sort(a, a + 6, cmp);
	for (int i = 0; i < 6; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}
/*
* 9 5 4 2 6 -1
* 9 6 5 4 2 -1
*/

如果比较函数不写，默认得到从小到大升序排序。

支持的迭代器类型总结

容器	迭代器类型	是否支持 `sort`
`vector`	随机访问	✅
`array`	随机访问	✅
`deque`	随机访问	✅
`string`	随机访问	✅
普通数组指针	随机访问	✅
`list`	双向	❌
`forward_list`	前向	❌
`set/map`	双向	❌（但自带排序）
`unordered_*`	前向	❌

2.4 打印n个整数的全排列信息

c++

#include<stdio.h>
#include<stdlib.h>
const int maxn = 11;
int n, P[maxn], hashTable[maxn] = { false };
void generateP(int index) {
	if (index == n + 1) {
		for (int i = 1; i <= n; i++) {
			printf("%d ", P[i]);
		}
		printf("\n");
		return;
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (hashTable[i] == false) {
				P[index] = i;
				hashTable[i] = true;
				generateP(index + 1);
				hashTable[i] = false;
			}
		}
	}
}
int main() {
	printf("Please input a number:");
	scanf("%d", &n);
	generateP(1);
	return 0;
}
/*
Please input a number : 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/

2.5 n皇后问题

2.5.1 解决方法1

c++

#include<stdio.h>
#include<math.h>
const int maxn = 11;
int n, P[maxn], hashTable[maxn] = { false };
int count = 0;
void generateP(int index) {
	//count++;
	//printf("count = %d\n", count);

	if (index == n + 1) {
		bool flag = true;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (abs(i - j) == abs(P[i] - P[j])) {
					flag = false;
					break;
				}
			}
			if (flag == false) {
				break;
			}
		}
		if (flag) {
			count++;

			for (int i = 1; i <= n; i++) {
				printf("P[%d] = %d ", i, P[i]);
			}
			printf("\n");

		}
		return;
	}
	else {
		for (int x = 1; x <= n; x++) {
			if (hashTable[x] == false) {
				P[index] = x;
				hashTable[x] = true;
				generateP(index + 1);
				hashTable[x] = false;
			}
		}
	}
}


int main() {
	n = 4;
	generateP(1);
	printf("count = %d\n", count);
	return 0;
}
/*
P[1] = 2 P[2] = 4 P[3] = 1 P[4] = 3
P[1] = 3 P[2] = 1 P[3] = 4 P[4] = 2
count = 2
*/

2.5.2 进阶用法

c++

#include<stdio.h>
#include<math.h>
const int maxn = 11;
int n, P[maxn], hashTable[maxn] = { false };
int count = 0;
void generateP(int index) {

	if (index == n + 1) {
		/*bool flag = true;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (abs(i - j) == abs(P[i] - P[j])) {
					flag = false;
					break;
				}
			}
			if (flag == false) {
				break;
			}
		}
		if (flag) {
			count++;

			for (int i = 1; i <= n; i++) {
				printf("P[%d] = %d ", i, P[i]);
			}
			printf("\n");

		}*/
		count++;
		for (int i = 1; i <= n; i++) {
			printf("P[%d] = %d ", i, P[i]);
		}
		printf("\n");
		return;
	}
	else {
		for (int x = 1; x <= n; x++) {
			if (hashTable[x] == false) {
				bool flag = true;
				for (int i = 1; i < index; i++) {

					if (abs(i - index) == abs(x - P[i])) {
						flag = false;
						break;
					}

				}
				if (flag) {

					P[index] = x;
					hashTable[x] = true;
					generateP(index + 1);
					hashTable[x] = false;
				}
			}
		}
	}
}


int main() {
	n = 4;
	generateP(1);
	printf("count = %d\n", count);
	return 0;
}
/*
P[1] = 2 P[2] = 4 P[3] = 1 P[4] = 3
P[1] = 3 P[2] = 1 P[3] = 4 P[4] = 2
count = 2
*/

2.5 二分查找

2.5.1 求平方根

c++

#include<cstdio>
#include<stdlib.h>
const double eps = 1e-8;
double f(double x) {
	return x * x;
}
double calSqrt(double left, double right, double target) {
	double mid;
	while (right - left > eps) {
		mid = (left + right) / 2.0;
		if (f(mid) > target) {
			right = mid;
		}
		else {
			left = mid;
		}
	}
	return mid;
}
int main() {
	double left = 3.0;
	double right = 4.0;
	double target = 15.0;
	printf("%lf", calSqrt(left, right, target));
	return 0;
}
// 根号15 约为 3.872983

2.5.2 拓展

已知一个数组nums，一个target，请二分查找实现找到

1、第一个大于target

2、第一个大于等于target

3、等于target

4、最后一个小于target

5、最后一个小于等于target的元素的下标代码

第一个小于target的下标 = 第一个大于等于target的下标 - 1
第一个小于等于target的下标 = 第一个大于target的下标 - 1

（1）第一个大于和第一个大于等于

c++

/**
 * 找到第一个 > target 的下标
 * 思路：只要 nums[mid] > target，说明答案在左半区间，收缩右边界
 * 否则收缩左边界
 * 返回值：下标，如果不存在则返回 -1
 */
int firstGreater(const vector<int>& nums, int target) {
    int l = 0, r = nums.size(); // 区间 [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > target) r = mid;  // 可能是答案，缩小右边
        else l = mid + 1;                 // 太小，往右找
    }
    return l < nums.size() ? l : -1;
}

/**
 * 找到第一个 >= target 的下标
 * 思路：只要 nums[mid] >= target，说明可能是答案，收缩右边界
 * 否则收缩左边界
 */
int firstGreaterEqual(const vector<int>& nums, int target) {
    int l = 0, r = nums.size(); // 区间 [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l < nums.size() ? l : -1;
}

（2）最后一个小于和最后一个小于等于

c++

/**
 * 找到最后一个 < target 的下标
 * 思路：nums[mid] < target，说明答案可能在右边，移动左边界
 * 否则收缩右边界
 * 最终结果是 l-1
 */
int lastLess(const vector<int>& nums, int target) {
    int l = 0, r = nums.size(); // 区间 [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l - 1;
}

/**
 * 找到最后一个 <= target 的下标
 * 思路：nums[mid] <= target，答案可能更靠右，移动左边界
 * 否则收缩右边界
 * 最终结果是 l-1
 */
int lastLessEqual(const vector<int>& nums, int target) {
    int l = 0, r = nums.size(); // 区间 [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] <= target) l = mid + 1;
        else r = mid;
    }
    return l - 1;
}

（3）查找等于

c++

/**
 * 找到等于 target 的下标（经典二分）
 * 思路：标准写法 [l, r]
 */
int equalTo(const vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1; // 注意这里是闭区间
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1; // 没找到
}
/**
 * 找到等于 target 的下标（经典二分）
 * 思路：标准写法 [l, r)
 */
int equalTo2(const vector<int>& nums, int target) {
    int l = 0, r = nums.size(); // 注意这里是开区间
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid;
    }
    return -1; // 没找到
}

2.6 归并排序

2.6.1 序列合并问题

假设有两个递增序列 A 与 B，要求将它们合并为一个递增序列 C

c++

#include<cstdio>
#include<stdlib.h>
// 将递增数组A和递增数组B合并为数组C，保持递增
int merge(int A[], int B[], int C[], int length1, int length2) {
	
	int i = 0, j = 0, k = 0;
	while (i < length1 && j < length2) {
		if (A[i] <= B[j]) {
			C[k++] = A[i++];
		}
		else {
			C[k++] = B[j++];
		}
	}
	while (i < length1) {
		C[k++] = A[i++];
	}
	while (j < length2) {
		C[k++] = B[j++];
	}
	return k;
}
int main() {
	int a[5] = { 1, 3, 5, 6, 7 };
	int b[5] = { 4, 8, 9, 11, 32 };
	int length1 = sizeof(a) / sizeof(a[0]);
	int length2 = sizeof(b) / sizeof(b[0]);
	int* c = (int*)malloc(sizeof(int) * 20);


	int length3 = merge(a, b, c, length1, length2);
	for (int i = 0; i < length3; i++) {
		printf("%d ", c[i]);
	}
	return 0;
}

2.6.2 归并排序代码递归实现

c++

#include<cstdio>
#include<stdlib.h>
const int maxn = 1000;
// 将数组a中的[L1, R1] 和 [L2, R2]区间进行合并
void merge(int a[], int L1, int R1, int L2, int R2) {
	int i = L1, j = L2;
	int temp[maxn] = { 0 }, k = 0;
	while (i <= R1 && j <= R2) {
		if (a[i] <= a[j]) {
			temp[k++] = a[i++];
		}
		else {
			temp[k++] = a[j++];
		}
	}
	while (i <= R1) {
		temp[k++] = a[i++];
	}
	while (j <= R2) {
		temp[k++] = a[j++];
	}
	// 将temp数组的结果重新写入到a数组中去
	for (i = L1; i < L1 + k; i++) {
		a[i] = temp[i - L1];
	}
}
// 将数组a中的[left, right]进行归并排序
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);
	}
}
int main() {
	int a[10] = { 2 , 5, 1, 4, 6, 7, -3, 6, 10, -5 };
	mergeSort(a, 0, 9);
	for (int i = 0; i < 10; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}
// -5 -3 1 2 4 5 6 6 7 10

2.7 快速排序

2.7.1 代码实现

c++

#include<cstdio>
#include<stdlib.h>
int Partition(int A[], int left, int right) {
	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;
	return left;
}
void quickSort(int *a, int left, int right) {
	if (left < right) {
		int pos = Partition(a, left, right);
		quickSort(a, left, pos - 1);
		quickSort(a, pos + 1, right);
	}
}
int main() {
	int a[10] = { 2 , 5, 1, 4, 6, 7, -3, 6, 10, -5 };
	quickSort(a, 0, 9);
	for (int i = 0; i < 10; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}
// -5 -3 1 2 4 5 6 6 7 10

其中A[left]称为主元，当数组A几乎有序时，时间复杂度最坏，为O( $n^{2}$ )，为了改进，修改主元，使用随机数随机选取一个作为主元

2.7.2 改进

需要把Partition函数改为如下：

c++

#include<time.h>
#include<math.h>
#include<algorithm>
using namespace std;
int randPartition(int A[], int left, int right) {
	// 生成 [left, right] 内的随机数 p

	int p = round(1.0 * rand()/RAND_MAX * (right - left) + left);

	int temp = A[left]; // 交换 A[p] 和 A[left]

	swap(A[p], 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;
	return left;
}

2.8 双指针思路

1、判断链表是否有环

快指针：每次走两步，慢指针：每次走一步，如果快慢指针相遇，那么有环

c++

bool hasCycle(ListNode *head) {
    ListNode* slow = head, *fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

2、判断链表是否是回文链表

快指针：每次走两步，慢指针：每次走一步

c++

ListNode* fast = head->next;
ListNode* slow = head;
while(fast && fast->next){
    slow = slow->next;
    fast = fast->next->next;
}
// 退出循环的时候 slow 位置就是链表中间位置
// 然后将slow后面的元素进行反转，得到一个反转链表
// 将链表的前半部分和后半部分进行遍历判断即可

2.9 快速幂

c++

#include<iostream>
#include<vector>
using namespace std;
// 求 a 的 b 次幂
int QuickPow(int a, int b) {
	int result = 1;
	while (b != 0) {
		if (b & 1) {
			result *= a;
		}
		a *= a;
		b >>= 1;
	}
	return result;
}
int main() {
	int a, b;
	cin >> a >> b;
	cout << QuickPow(a, b) << "\n";
	return 0;
}

3、数学问题

3.1 最大公约数和最小公倍数

3.1.1 最大公约数

c++

#include<cstdio>
#include<stdlib.h>
using namespace std;
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d", gcd(a, b));
	return 0;
}
/*
35 15
5
*/

3.1.2 最小公倍数

思路：对于数a和数b，先求出最大公约数d，那么最小公倍数就是 a / d * b

c++

#include<cstdio>
#include<stdlib.h>
using namespace std;
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
int lcm(int a, int b) {
	int temp = gcd(a, b);
	return a / temp * b;
}
int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	printf("%d", lcm(a, b));

	return 0;
}
/*
15 6
30
*/

拓展——求最大公约数的三种方法：

c++

int gcd1(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
int gcd2(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
int gcd3(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}

3.2 素数

3.2.1 枚举法

时间复杂度： $O (n \sqrt{(} n))$

c++

#include<cstdio>
#include<stdlib.h>
#include<math.h>
bool isPrime(int n) {
	if (n <= 1) {
		return false;
	}
	else {
		int i = 2;
		int sqt = (int)sqrt(1.0 * n);
		for (i = 2; i <= sqt; i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}
const int num = 101;
int prime[num], pNum = 0;
bool p[num] = { false };
using namespace std;
void FindPrime() {
	for (int i = 0; i < num; i++) {
		if (isPrime(i)) {
			prime[pNum++] = i;
			p[i++] = true;
		}
	}
}
int main() {
	FindPrime();
	for (int i = 0; i < pNum; i ++ ) {
		printf("%d ", prime[i]);
	}
	return 0;

}
// 2 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

3.2.2 埃氏筛选法

时间复杂度： $O (n l o g l o g (n))$

代码实现：

c++

#include<cstdio>
#include<stdlib.h>
#include<math.h>
const int maxn = 100;
int prime[maxn], pNum = 0;
bool p[maxn] = { false };
using namespace std;
void FindPrime() {
	for (int i = 2; i < maxn; i++) {
		if (p[i] == false) {
			prime[pNum++] = i;
			for (int j = i + i; j < maxn; j = j + i) {
				p[j] = true;
			}
		}
	}
}
int main() {
	/*for (int i = 0; i < maxn; i++) {
		printf("%d", p[i]);
	}*/
	FindPrime();
	printf("pNum = %d\n", pNum);
	for (int i = 0; i < pNum; i ++ ) {
		printf("%d ", prime[i]);
	}
	return 0;

}
/*
pNum = 25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
*/

3.3.3 总结

c++

#include <iostream>
#include <vector>
using namespace std;

const int MAX_NUM = 1001; // 定义最大数值范围（筛到 1000）

vector<int> primes;           // 存储所有找到的素数
bool is_composite[MAX_NUM];   // 标记是否为合数（true 表示不是素数），初始 false 表示都是素数候选

/**
 * @brief 判断一个数是否为素数（试除法）
 * @param n 待判断的数
 * @return true 表示是素数，false 表示不是素数
 *
 * 时间复杂度：O(√n)
 * 适用于单个数字判断，不适合大量筛选。
 */
bool isPrime(int n) {
	if (n <= 1) return false;  // 1 和负数不是素数
	if (n == 2) return true;   // 2 是唯一偶数素数
	if (n % 2 == 0) return false; // 偶数（除了2）都不是素数

	// 只需检查到 sqrt(n)，即 i <= n/i 避免浮点运算
	for (int i = 3; i <= n / i; i += 2) { // 跳过偶数因子
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

/**
 * @brief 普通筛法（暴力调用 isPrime）
 * @description 遍历每个数并用 isPrime 判断，效率较低 O(n√n)
 */
void Find_Prime_BruteForce() {
	// 重置状态和结果
	primes.clear();
	fill(is_composite, is_composite + MAX_NUM, false); // 初始化为 false（未标记）

	for (int i = 2; i < MAX_NUM; i++) { // 从2开始（最小素数）
		if (isPrime(i)) {
			primes.push_back(i);        // 记录素数
			is_composite[i] = true;     // 可选：标记该数为素数（注意这里命名反了）
		}
	}
	// 注意：这里 is_composite[i]=true 实际上表示 i 是素数，命名容易混淆，建议改名或反转逻辑
}

/**
 * @brief 埃拉托斯特尼筛法（埃氏筛）
 * @description 从最小的素数开始，将其所有倍数标记为合数
 * 时间复杂度：O(n log log n)，适合 n <= 1e6 左右
 */
void Find_Prime_Eratosthenes() {
	primes.clear();
	fill(is_composite, is_composite + MAX_NUM, false); // 初始化：所有数默认是素数候选

	for (int i = 2; i < MAX_NUM; i++) {
		if (!is_composite[i]) { // 如果 i 还未被标记为合数，则它是素数
			primes.push_back(i);

			// 从 i*i 开始标记，因为小于 i*i 的 i 的倍数已经被更小的素数筛掉了
			// 例如：当 i=5 时，2*5=10 已被 2 筛掉，3*5=15 被 3 筛掉，只有 25 及以上需要筛
			for (long long j = (long long)i * i; j < MAX_NUM; j += i) {
				is_composite[j] = true; // 标记 j 为合数
			}
		}
	}
}

/**
 * @brief 欧拉筛法（线性筛），保证每个合数只被其最小质因子筛一次
 * @description 时间复杂度 O(n)，空间换时间，最高效
 */
void Find_Prime_Linear() {
	primes.clear();
	fill(is_composite, is_composite + MAX_NUM, false); // 初始化

	for (int i = 2; i < MAX_NUM; i++) {
		if (!is_composite[i]) {
			// i 未被标记，说明是素数，加入素数表
			primes.push_back(i);
		}

		// 关键：用已知素数去筛后面的合数
		for (int j = 0; j < primes.size(); j++) {
			int p_j = primes[j];               // 当前素数
			long long next = (long long)i * p_j; // 要筛掉的合数

			if (next >= MAX_NUM) break;        // 超出范围就跳出

			is_composite[next] = true;         // 标记合数

			// 核心优化：如果 i % p_j == 0，说明 p_j 是 i 的最小质因子
			// 那么对于下一个更大的素数 p_k > p_j，i * p_k 的最小质因子仍是 p_j
			// 所以等到 i 更大时再由 p_j 来筛，避免重复
			if (i % p_j == 0) {
				break;
			}
		}
	}
}

/**
 * @brief 主函数
 * 使用线性筛法生成 2 到 1000 内的所有素数，并打印
 */
int main() {
	ios::sync_with_stdio(false); // 加速 cin/cout（虽然这里用了 printf）
	cin.tie(nullptr);

	// 调用线性筛法（推荐）
	Find_Prime_Linear();

	// 输出所有找到的素数，每行 10 个便于阅读
	cout << "Total primes found: " << primes.size() << "\n";
	for (int i = 0; i < primes.size(); ++i) {
		printf("%4d ", primes[i]); // 每个数占4位宽度
		if ((i + 1) % 10 == 0) cout << "\n"; // 每10个换行
	}
	if (primes.size() % 10 != 0) cout << "\n";

	return 0;
}

🔍 对比三种方法总结：

方法	名称	时间复杂度	特点
`Find_Prime_BruteForce`	暴力判断	$O (n \sqrt{(} n))$	简单但慢，不适合大范围
`Find_Prime_Eratosthenes`	埃氏筛	$O (n l o g l o g n)$	经典高效，教学常用
`Find_Prime_Linear`	欧拉筛（线性筛）	$O (n)$	最优，每个合数只筛一次

3.3 分解质因数

c++

#include<cstdio>
#include<stdlib.h>
#include<math.h>
const int maxn = 100;
int prime[maxn];
bool isPrime[maxn] = { true };
int pNum = 0;
void Find_Prime() {
	for (int i = 0; i < maxn; i++) {
		isPrime[i] = true;
	}
	for (int i = 2; i < maxn; i++) {
		if (isPrime[i] == true) {
			prime[pNum++] = i;
			for (int j = i + i; j < maxn; j = j + i) {
				isPrime[j] = false;
			}
		}
	}
}
struct factor {
	int x, cnt; // x 为质因子， cnt为个数
}fac[10];
int main() {
	Find_Prime();
	printf("pNum = %d\n", pNum);
	for (int i = 0; i < pNum; i++) {
		printf("%d ", prime[i]);
	}
	int n, num = 0;  // num 为 n的不同质因子的个数
	printf("\nPlease input a number:");
	scanf("%d", &n);
	if (n == 1) {
		printf("1 = 1");
	}
	else {
		printf("%d = ", n);
		int sqr = (int)sqrt(1.0 * n);
		for (int i = 0; i < pNum && prime[i] <= sqr; i++) {
			if (n % prime[i] == 0) {
				//printf("prime[i] = %d", prime[i]);
				fac[num].x = prime[i];
				fac[num].cnt = 0;
				while (n % prime[i] == 0) {
					fac[num].cnt++;
					n /= prime[i];
				}
				num++;
			}
			
			if (n == 1) {
				break;
			}
		}
		if (n != 1) {
			fac[num].x = n;
			fac[num++].cnt = 1;
		}
		// 输出结果
		for (int i = 0; i < num; i++) {
			if (i > 0) {
				printf("*");
			}
			printf("%d", fac[i].x);
			if (fac[i].cnt > 1) {
				printf("^%d", fac[i].cnt);
			}
		}
	}
	return 0;
}

/*
pNum = 25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Please input a number:192
192 = 2^6*3
*/

==写法2：==

c++

#include <iostream>
#include <vector>
using namespace std;

/**
 * 函数：factorize
 * 功能：对正整数 n 进行质因数分解，并以 "n = p1 * p2 * ... * pk" 的格式输出
 * 原理：利用算术基本定理，将整数分解为质数乘积
 */
void factorize(int n) {
    // 存储所有质因数（含重复）
    vector<int> factors;

    int original = n;  // 保存原始值用于输出

    // 特殊情况：n <= 0 或 n == 1
    if (n <= 0) {
        printf("输入必须是正整数！\n");
        return;
    }
    if (n == 1) {
        printf("1 = 1\n");
        return;
    }

    printf("%d = ", n);  // 开始输出分解式

    // 步骤 1：处理因子 2（唯一的偶数质数）
    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }

    // 步骤 2：处理奇数质因子，从 3 开始，只检查奇数，直到 sqrt(n)
    for (int i = 3; i <= n / i; i += 2) {  // i <= n/i 等价于 i*i <= n，避免浮点运算
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }

    // 步骤 3：如果剩余部分大于 1，则它本身是一个质数
    if (n > 1) {
        factors.push_back(n);
    }

    // 步骤 4：格式化输出结果，用 " * " 连接各因子
    for (int i = 0; i < factors.size(); i++) {
        if (i == 0) {
            printf("%d", factors[i]);
        }
        else {
            printf(" * %d", factors[i]);
        }
    }
    printf("\n");  // 换行，使输出更整洁
}

int main() {
    int n;

    // 显示输入提示
    cout << "请输入一个正整数进行质因数分解: ";
    cin >> n;

    // 调用分解函数
    factorize(n);

    return 0;
}

/*
示例运行：

输入：
请输入一个正整数进行质因数分解: 58

输出：
58 = 2 * 29


其他示例：
输入: 60
输出: 60 = 2 * 2 * 3 * 5

输入: 17
输出: 17 = 17

输入: 1
输出: 1 = 1
*/

3.4 大数算法

3.4.1 大数之间的加法（自定义结构体）

c++

#include<cstdio>
#include<stdlib.h>
#include<math.h>
#include<cstring>
struct bign {
	int d[1000];
	int len;
	bign(){
		memset(d, 0, sizeof(d));
		len = 0;
	}
};
// 整数字符串转换为 bign
bign change(char str[]) {
	bign a;
	a.len = strlen(str);
	for (int i = 0; i < a.len; i++) {
		a.d[i] = str[a.len - 1 - i] - '0';
	}
	return a;
}
// 大数之间的比较
int compare(bign a, bign b) {
	if (a.len > b.len) return 1;
	else if (a.len < b.len) return -1;
	else {
		for (int i = 0; i < a.len; i++) {
			if (a.d[i] > b.d[i]) {
				return 1;
			}
			else if (a.d[i] < b.d[i]) {
				return -1;
			}
		}
		return 0;
	}
}
bign add(bign a, bign b) {
	bign c;
	int carry = 0;
	for (int i = 0; i < a.len || i < b.len; i++) {
		int temp = a.d[i] + b.d[i] + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10;
	}
	if (carry != 0) {
		c.d[c.len++] = carry;
	}return c;
}
void print(bign a) {
	for (int i = a.len - 1; i >= 0; i--) {
		printf("%d", a.d[i]);
	}
}
int main() {
	char str1[1000], str2[1000];
	scanf("%s%s", str1, str2);
	bign a = change(str1);
	bign b = change(str2);
	printf("%s + %s = ", str1, str2);
	print(add(a, b));
	return 0;
}
/*
565632 564654321
565632 + 564654321 = 565219953
*/

3.4.2 大数之间的加减乘除（string实现）

0、前置处理

c++

// 判断两个大数的大小
//长度长的一定大（这里假设除了0以外，都没有前导0），长度相等则字典序小的数字更小
bool Lower(string str1, string str2) {
	return str1.length() < str2.length() || (str1.length() == str2.length() && str1 < str2);
}
// 判断是否为0
bool CheckZero(const string& str) {
	for (int i = 0; i < str.size(); i++) {
		if (str[i] != '0') {
			return false;
		}
	}
	return true;
}
// 判断是否为负数
bool CheckNegative(const string& str) {
	return str[0] == '-';
}

1、大数加法

c++

string addStrings(string& num1, string& num2) {
	int i = num1.size() - 1, j = num2.size() - 1;
	int result = 0;
	string ans;
	while (i >= 0 || j >= 0 || result != 0) {
		int x = i >= 0 ? num1[i--] - '0' : 0;
		int y = j >= 0 ? num2[j--] - '0' : 0;
		result += x + y;
		ans.push_back(result % 10 + '0');
		result = result / 10;
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

2、大数减法

c++

string Sub(string& str1, string& str2) {
	//处理0的情况
	if (str1 == str2 || (CheckZero(str1) && CheckZero(str2))) return "0";  //如果两数相等或者都是0
	else if (CheckZero(str1)) return "-" + str2;                       //如果第一个数字为0
	else if (CheckZero(str2)) return str1;                           //如果第二个数字为0
	//定正负
	int negative = 0;                     //结果的正负号
	if (Lower(str1, str2)) {
		swap(str1, str2);                //保证str1大于str2
		negative = 1;                     //如果str1小于str2，则结果过为负值
	}
	string ans;
	int i = str1.size() - 1, j = str2.size() - 1;//逆序开始处理
	int flag = 0;                         //借位标记
	while (i >= 0 || j >= 0) {
		int numa = i >= 0 ? str1[i--] - '0' : 0;  //取每一位，因为长度可能不同所以当某一个已经读取完毕时对应位置取0
		int numb = j >= 0 ? str2[j--] - '0' : 0;
		numa -= flag;                     //先减去借位
		if (numa < numb) {                  //如果不够减则向上一位借位（只可能借一位）
			numa += 10;                   //借位并记录借位
			flag = 1;
		}
		else flag = 0;                    //如果不借位，则借位标记为0
		ans += '0' + numa - numb;             //计算当前位置并保存
	}
	i = ans.size() - 1;
	while (ans[i] == '0') i--;
	ans = ans.substr(0, i + 1);              //去除前导0,如111-110=1
	//ans.resize(i + 1);
	if (negative) ans += '-';              //如果计算结果是负数，添加负数符号
	reverse(ans.begin(), ans.end());     //因为是逆序计算得到的结果，所以需要翻转一下
	return ans;
}

3、大数乘法

c++

string Mul(string str1, string str2) {
    if (CheckZero(str1) || CheckZero(str2)) return "0";   //如果有一个为0,则结果为0

    int negative = 0, negastr1 = 0, negastr2 = 0;         //定正负
    if (CheckNegative(str1)) {                            //确定正负号标记，并且去掉-字符
        negastr1 = 1; str1 = str1.substr(1, str1.size() - 1);
    }
    if (CheckNegative(str2)) {
        negastr2 = 1; str2 = str2.substr(1, str2.size() - 1);
    }
    negative = negastr1 ^ negastr2;                       //异或运算确定结果的正负号

    string ans;
    if (Lower(str1, str2)) swap(str1, str2);              //保证str1大于等于str2
    int size1 = str1.size(), size2 = str2.size();
    for (int i = size2 - 1; i >= 0; i--) {                //遍历较小数字的每一位
        string temp(size2 - 1 - i, '0');                  //temp为str1乘以str2[i]的积，根据str2[i]的权重（个十百千万，补充对应个数的0）
        int flag = 0;                                     //进位标记
        for (int j = size1 - 1; j >= 0; j--) {
            flag += (str1[j] - '0') * (str2[i] - '0');
            temp.push_back('0' + (flag % 10));
            flag /= 10;
        }
        if (flag) temp.push_back('0' + flag);             //如果最高位还有进位
        reverse(temp.begin(), temp.end());
        ans = Add(ans, temp);                             //将计算结果累加到最终的结果上
    }
    if (negative) ans = "-" + ans;                        //处理结果的正负号
    return ans;
}

4、全部代码

c++

#include<iostream>
#include<string>
using namespace std;
//大数四则运算，两个参数都不能为空
string Add(string str1, string str2);       //大数加法
string Sub(string str1, string str2);       //大数减法
string Mul(string str1, string str2);       //大数乘法
string Div(string str1, string str2);       //大数除法
bool Lower(string str1, string str2);       //大数比较（小于）
bool CheckZero(const string& str);          //检查是不是0，比如0000认为是0
bool CheckNegative(const string& str);      //检查是不是负数
void ShowMenu();                            //提示菜单
void ShowMenu(char choice);                 //二级菜单
int main() {
    string a, b;
    char ch;
    ShowMenu();
    while (cin >> ch && ch != 'q') {                //循环打印菜单并提示用户输入
        ShowMenu(ch);
        cin >> a >> b;
        switch (ch) {
        case 'a':cout << a << " + " << b << " = " << Add(a, b) << endl; break;
        case 'b':cout << a << " - " << b << " = " << Sub(a, b) << endl; break;
        case 'c':cout << a << " * " << b << " = " << Mul(a, b) << endl; break;
        case 'd':cout << a << " / " << b << " = " << Div(a, b) << endl; break;
        }
        ShowMenu();
    }
    return 0;
}
string Add(string str1, string str2) {
    //关于0的处理
    if (CheckZero(str1) && CheckZero(str2)) return "0";    //如果都是0
    else if (CheckZero(str1)) return str2;               //如果有个一为0
    else if (CheckZero(str2)) return str1;
    string ans;
    int i = str1.size() - 1, j = str2.size() - 1;
    int flag = 0;                                         //进位标记
    while (i >= 0 || j >= 0 || flag) {
        int numa = i >= 0 ? str1[i--] - '0' : 0;                  //如果所有位都访问完毕，对应的位置用0代替
        int numb = j >= 0 ? str2[j--] - '0' : 0;
        flag = numa + numb + flag;                            //计算两位的和
        ans += '0' + flag % 10;                               //取个位保存在答案中
        flag /= 10;                                       //计算进位
    }
    reverse(ans.begin(), ans.end());
    return ans;
}
string Sub(string str1, string str2) {
    //处理0的情况
    if (str1 == str2 || (CheckZero(str1) && CheckZero(str2))) return "0";  //如果两数相等或者都是0
    else if (CheckZero(str1)) return "-" + str2;                       //如果第一个数字为0
    else if (CheckZero(str2)) return str1;                           //如果第二个数字为0
    //定正负
    int negative = 0;                     //结果的正负号
    if (Lower(str1, str2)) {
        swap(str1, str2);                //保证str1大于str2
        negative = 1;                     //如果str1小于str2，则结果过为负值
    }
    string ans;
    int i = str1.size() - 1, j = str2.size() - 1;//逆序开始处理
    int flag = 0;                         //借位标记
    while (i >= 0 || j >= 0) {
        int numa = i >= 0 ? str1[i--] - '0' : 0;  //取每一位，因为长度可能不同所以当某一个已经读取完毕时对应位置取0
        int numb = j >= 0 ? str2[j--] - '0' : 0;
        numa -= flag;                     //先减去借位
        if (numa < numb) {                  //如果不够减则向上一位借位（只可能借一位）
            numa += 10;                   //借位并记录借位
            flag = 1;
        }
        else flag = 0;                    //如果不借位，则借位标记为0
        ans += '0' + numa - numb;             //计算当前位置并保存
    }
    i = ans.size() - 1;
    while (ans[i] == '0') i--;
    ans = ans.substr(0, i + 1);              //去除前导0,如111-110=1
    if (negative) ans += '-';              //如果计算结果是负数，添加负数符号
    reverse(ans.begin(), ans.end());     //因为是逆序计算得到的结果，所以需要翻转一下
    return ans;
}
string Mul(string str1, string str2) {
    if (CheckZero(str1) || CheckZero(str2)) return "0";   //如果有一个为0,则结果为0

    int negative = 0, negastr1 = 0, negastr2 = 0;         //定正负
    if (CheckNegative(str1)) {                            //确定正负号标记，并且去掉-字符
        negastr1 = 1; str1 = str1.substr(1, str1.size() - 1);
    }
    if (CheckNegative(str2)) {
        negastr2 = 1; str2 = str2.substr(1, str2.size() - 1);
    }
    negative = negastr1 ^ negastr2;                       //异或运算确定结果的正负号

    string ans;
    if (Lower(str1, str2)) swap(str1, str2);              //保证str1大于等于str2
    int size1 = str1.size(), size2 = str2.size();
    for (int i = size2 - 1; i >= 0; i--) {                //遍历较小数字的每一位
        string temp(size2 - 1 - i, '0');                  //temp为str1乘以str2[i]的积，根据str2[i]的权重（个十百千万，补充对应个数的0）
        int flag = 0;                                     //进位标记
        for (int j = size1 - 1; j >= 0; j--) {
            flag += (str1[j] - '0') * (str2[i] - '0');
            temp.push_back('0' + (flag % 10));
            flag /= 10;
        }
        if (flag) temp.push_back('0' + flag);             //如果最高位还有进位
        reverse(temp.begin(), temp.end());
        ans = Add(ans, temp);                             //将计算结果累加到最终的结果上
    }
    if (negative) ans = "-" + ans;                        //处理结果的正负号
    return ans;
}
string Div(string str1, string str2) {
    //处理除数为0的情况和被除数为0的情况
    if (CheckZero(str2)) return "The divisor cannot be zero!";
    else if (CheckZero(str1)) return "0.000000";

    int negative = 0, negastr1 = 0, negastr2 = 0;               //定正负
    if (CheckNegative(str1)) {                            //确定正负号标记，并且去掉-
        negastr1 = 1; str1 = str1.substr(1, str1.size() - 1);
    }
    if (CheckNegative(str2)) {
        negastr2 = 1; str2 = str2.substr(1, str2.size() - 1);
    }
    negative = negastr1 ^ negastr2;                         //异或运算确定结果的正负号

    int point = 0;                                        //结果是否为纯小数
    if (Lower(str1, str2)) point = 1;                       //如果str1小于str2，则计算为纯小数
    string ans;                                         //计算结果
    str1 += string(6, '0');                                //补足6个0，用于计算小数位

    int size1 = str1.size(), size2 = str2.size();
    int i = size2 - 1;                                      //商第一位的位置
    string temp = str1.substr(0, i);                       //从str1上取size2-1个字符
    for (i; i < size1; i++) {
        temp += str1[i];                                  //从后边拿出一位，预先处理可以防止结尾处越界
        int cnt = 0;                                      //当前位的商，也就是temp中包含了多少个str2，使用减法                                          //如果temp不为0，则计算商
        while (Lower(str2, temp) || temp == str2) {            //如果当前位商不为0，则计算商
            temp = Sub(temp, str2);
            cnt++;
        }
        if (temp == "0") temp.clear();                     //如果某次计算结果为0，则清空，避免0的堆积,比如111000 111
        ans.push_back('0' + cnt);                         //保存商
    }
    i = 0;
    while (ans[i] == '0') i++;
    ans = ans.substr(i, ans.size() - i);                     //去除前导0
    if (point) {                                          //如果是纯小数,补足6位并添加小数点
        int len = 6 - ans.size();
        ans = "0." + string(len, '0') + ans;
    }
    else ans.insert((ans.end() - 6), '.');                 //如果不是小数，则只需要插入小数点       
    if (negative) ans = "-" + ans;                           //最后一步骤，如果是负数带上负号
    return ans;
}
bool Lower(string str1, string str2) {                   //长度长的一定大（这里假设除了0以外，都没有前导0），长度相等则字典序小的数字更小
    return str1.size() < str2.size() || (str1.size() == str2.size() && str1 < str2);
}
bool CheckZero(const string& str) {      //检查是否等于0
    int size = str.size();                //如果全是0则为0，这里假设不会有带符号的+00000或者-00000作为输入
    for (int i = 0; i < size; i++)
        if (str[i] != '0') return false;
    return true;
}
bool CheckNegative(const string& str) {  //检查是否为负数
    return str[0] == '-';
}
void ShowMenu() {
    cout << "请选择要进行的大数运算：\n"
        << "a) 加法          b) 减法\n"
        << "c) 乘法          d) 除法\n"
        << "q) 退出\n"
        << "请输入你的选择： ";
}
void ShowMenu(char choice) {
    cout << "请输入要计算的两个数字";
    switch (choice) {
    case 'a':cout << "（仅支持非负整数加法计算）: " << endl; break;
    case 'b':cout << "（仅支持非负整数减法计算）: " << endl; break;
    case 'c':cout << "（仅支持整数乘法计算）: " << endl; break;
    case 'd':cout << "（仅支持整数除法计算，计算结果显示6位小数）: " << endl; break;
    }
}

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

3.4.3 另一种方法

c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 比较字符串数字大小（长度优先，长度相同则按字典序比较）
bool lower(const string& a, const string& b) {
    return a.length() < b.length() || (a.length() == b.length() && a < b);
}

// 大整数加法（a + b）
void add(const string& a, const string& b) {
    string result;                          // 存储结果
    int i = a.size() - 1, j = b.size() - 1; // 从最低位开始相加
    int sum = 0;                            // 进位累加器

    // 当两个数未遍历完 或 有进位时继续计算
    while (i >= 0 || j >= 0 || sum != 0) {
        int numA = i >= 0 ? a[i--] - '0' : 0; // 当前位 a
        int numB = j >= 0 ? b[j--] - '0' : 0; // 当前位 b
        sum += numA + numB;                   // 本位求和
        result.push_back(sum % 10 + '0');     // 保存个位
        sum /= 10;                            // 更新进位
    }

    reverse(result.begin(), result.end());    // 反转为正常顺序
    cout << result << endl;                   // 输出结果
}

// 大整数减法（a - b）
void sub(string& a, string& b) {
    // 如果两数相等，直接输出 0
    if (a == b) {
        cout << 0 << endl;
        return;
    }

    string result; 
    bool negative = false; // 标记是否为负数

    // 如果 a < b，则交换，结果为负
    if (lower(a, b) == true) {
        swap(a, b);
        negative = true;
    }

    int i = a.size() - 1, j = b.size() - 1, carry = 0;

    // 按位相减
    while (i >= 0 || j >= 0) {
        int numA = i >= 0 ? a[i--] - '0' : 0;
        int numB = j >= 0 ? b[j--] - '0' : 0;
        int temp = numA - numB - carry;   // 计算差值
        if (temp < 0) {                   // 需要借位
            temp += 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result.push_back(temp + '0');
    }

    // 去掉高位多余的 0
    while (result.size() > 1 && result.back() == '0') {
        result.pop_back();
    }

    // 如果是负数，添加负号
    if (negative) {
        result.push_back('-');
    }

    reverse(result.begin(), result.end()); // 恢复正确顺序
    cout << result << endl;
}

// 大整数乘法（a * b）
void mul(string& a, string& b) {
    string result;
    reverse(a.begin(), a.end()); // 翻转方便从低位计算
    reverse(b.begin(), b.end());
    vector<int> sum(a.size() + b.size(), 0); // 存储中间结果

    // 模拟竖式乘法
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            sum[i + j] += (a[i] - '0') * (b[j] - '0');
        }
    }

    // 处理进位
    for (int i = 0; i < sum.size() - 1; i++) {
        sum[i + 1] += sum[i] / 10;
        sum[i] %= 10;
    }

    // 去掉前导 0
    int k = sum.size() - 1;
    while (k >= 0 && sum[k] == 0) {
        k--;
    }

    // 如果结果为 0
    if (k < 0) {
        result = "0";
    } else {
        // 拼接结果
        while (k >= 0) {
            result += (sum[k--] + '0');
        }
    }
    cout << result << endl;
}

// 封装运算：输出加法、减法、乘法结果
void solve(string& a, string& b) {
    add(a, b);
    sub(a, b);
    mul(a, b);
}

int main () {
    string a, b;
    cin >> a >> b;  // 输入两个大整数
    solve(a, b);    // 执行三种运算
    return 0;
}

3.4.4 乘法（高精度 * 高精度）

c++

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>mul(vector<int>&A, vector<int>&B) {
	vector<int>result(A.size() + B.size(), 0);
	for (int i = 0; i < B.size();i++) {
		for (int j = 0; j < A.size();j++) {
			result[i + j] += A[j] * B[i];
		}
	}
	for (int i = 1; i < result.size();i++) {
		result[i] += result[i - 1] / 10;
		result[i - 1] %= 10;
	}
	while (result.size() > 1 && result.back() == 0) {
		result.pop_back();
	}
	return result;
}
void solve(string& a, string& b) {
	vector<int>A, B;
	for (int i = a.size() - 1; i >= 0;i--) {
		A.emplace_back(a[i] - '0');
	}
	for (int i = b.size() - 1; i >= 0;i--) {
		B.emplace_back(b[i] - '0');
	}
	vector<int>C = mul(A, B);
	for (int i = C.size() - 1; i >= 0;i--) {
		cout << C[i];
	}
}
int main() {
	string a, b;
	cin >> a >> b;
	solve(a, b);
	return 0;
}

4、C++标准模板库

4.1 vector 容器

可以理解为变长数组

头文件：#include<vector>

4.1.1 迭代器访问

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > temp;
	int length = 10;
	for (int i = 0; i < length; i++){
		temp.push_back(i);
	}
	vector<int>::iterator it;
	for (it = temp.begin(); it != temp.end(); it++) {
		printf("%d ", *it);
	}
	return 0;
}
// 0 1 2 3 4 5 6 7 8 9

4.1.2 常用函数

（1）push_back()函数

在vector后面添加一个元素x，时间复杂度为O(1)

用法示例：

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > temp;
	int length = 10;
	for (int i = 0; i < length; i++){
		temp.push_back(i);
	}
	vector<int>::iterator it;
	for (it = temp.begin(); it != temp.end(); it++) {
		printf("%d ", *it);
	}
	return 0;
}
// 0 1 2 3 4 5 6 7 8 9

（2）pop_back()函数

用于删除vector的尾元素，时间复杂度为O(1)

用法示例：

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > vi;
	int length = 10;
	for (int i = 0; i < length; i++){
		vi.push_back(i);
	}
	vi.pop_back();
	vector<int>::iterator it;
	for (it = vi.begin(); it != vi.end(); it++) {
		printf("%d ", *it);
	}
	return 0;
}
// 0 1 2 3 4 5 6 7 8

（3）size()函数

用于获得vector中的元素个数，时间复杂度为O(1)

示例用法：

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > vi;
	int length = 10;
	for (int i = 0; i < length; i++){
		vi.push_back(i);
	}
	vi.pop_back();
	printf("lentgh = %d", vi.size());
	
}
// lentgh = 9

（4）clear()函数

用于清空vector中的所有元素，时间复杂度为O(N)，其中N为vector中元素的个数

示例用法：

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > vi;
	int length = 10;
	for (int i = 0; i < length; i++){
		vi.push_back(i);
	}
	vi.clear();
	printf("lentgh = %d", vi.size());
	
}
// lentgh = 0

（5）insert()函数

insert(it, x)用来向 vector 的任意迭代器it处插入一个元素x，时间复杂度为O(N)

示例代码：

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > vi;
	int length = 10;
	for (int i = 0; i < length; i++){
		vi.push_back(i);
	}
	vi.insert(vi.begin() + 2, -5); // 向位置为2的地方插入-5
	vector<int>::iterator it;
	for (it = vi.begin(); it != vi.end(); it++) {
		printf("%d ", *it);
	}
	return 0;
}
// 0 1 -5 2 3 4 5 6 7 8 9

（6）erase()函数

两种用法：删除单个元素、删除一个区间内的所有元素。时间复杂度为O(N)

示例用法：

1、删除单个元素：erase(it)即为删除迭代器it处的元素

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > vi;
	int length = 10;
	for (int i = 0; i < length; i++){
		vi.push_back(i);
	}
	vi.erase(vi.begin() + 1); // 删除 vi[1]
	vector<int>::iterator it;
	for (it = vi.begin(); it != vi.end(); it++) {
		printf("%d ", *it);
	}
	return 0;
}
// 0 2 3 4 5 6 7 8 9

2、删除一个区间内的所有元素：erase(first, last)用于删除[fist, last)内的所有元素

示例代码：

c++

#include<cstdio>
#include<vector>
using namespace std;
int main() {
	vector< int > vi;
	int length = 10;
	for (int i = 0; i < length; i++){
		vi.push_back(i);
	}
	vi.erase(vi.begin() + 1, vi.begin() + 4); // 删除 vi[1] vi[2] vi[3]
	vector<int>::iterator it;
	for (it = vi.begin(); it != vi.end(); it++) {
		printf("%d ", *it);
	}
	return 0;
}
// 0 4 5 6 7 8 9

4.2 set 集合

set翻译为集合，是一个内部自动有序且不含重复元素的容器

头文件：#include<set>

4.2.1 迭代器访问

c++

#include<cstdio>
#include<set>
using namespace std;
int main() {
	set<int> st;
	st.insert(3);
	st.insert(2);
	st.insert(5);
	st.insert(3);
	for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
		printf("%d ", *(it));
	}
	return 0;
}
// 2 3 5

4.2.2 常用函数

（1）insert()函数

insert(x)实现将x插入set容器中，并且自动递增排序和去重，时间复杂度为O(logN)，其中N为set内的元素个数

（2）find()函数

find(value)函数返回set中对应值为value的迭代器，时间复杂度为O(logN)，其中N为set内的元素个数

示例用法：

c++

#include<cstdio>
#include<set>
using namespace std;
int main() {
	set<int> st;
	st.insert(3);
	st.insert(2);
	st.insert(5);
	st.insert(3);
	set<int> ::iterator it = st.find(2); // 在 set 中查找2，返回其迭代器
	printf("%d\n", *it);
	return 0;
}
// 2

（3）erase()函数

两种用法：删除单个元素、删除一个区间内的所有元素

1、删除单个元素，两种方法

st.erase(it)，其中 it 为所需要删除元素的迭代器，时间复杂度为O(1)，可以结合find()来使用

c++

#include<cstdio>
#include<set>
using namespace std;
int main() {
	set<int> st;
	st.insert(100);
	st.insert(200);
	st.insert(100);
	st.insert(300);
	st.erase(st.find(100));
	for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
		printf("%d ", *(it));
	}
	return 0;
}
// 200 300

st.erase(value)，value 为所需要删除元素的值，时间复杂度为O(logN)，N为set内的元素个数

c++

#include<cstdio>
#include<set>
using namespace std;
int main() {
	set<int> st;
	st.insert(100);
	st.insert(200);
	st.insert(100);
	st.insert(300);
	st.erase(100);
	for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
		printf("%d ", *(it));
	}
	return 0;
}
// 200 300

2、删除一个区间内的所有元素：erase(first, last)用于删除[fist, last)内的所有元素，时间复杂度为O(last - first)

c++

#include<cstdio>
#include<set>
using namespace std;
int main() {
	set<int> st;
	st.insert(20);
	st.insert(10);
	st.insert(40);
	st.insert(30);
	st.erase(st.find(30), st.end());
	for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
		printf("%d ", *(it));
	}
	return 0;
}
// 10 20

（4）size()函数

用于获取set内的元素个数，时间复杂度为O(1)

（5）clear()函数

用于清空set中的所有元素，时间复杂度为O(N)，N为set内的元素个数

IMPORTANT

==set最主要的作用是自动去重并且升序排序==

4.3 String 字符串

KMP算法：

c++

void getNext(int* next, const string& s) {
	int j = -1;
	next[0] = j;
	for (int i = 1; i < s.size(); i++) {
		while (j >= 0 && s[i] != s[j + 1]) {
			j = next[j];
		}
		if (s[i] == s[j + 1]) {
			j++;
		}
		next[i] = j;
	}
}
// s 是主串，t是模式串
int strStr(string& s, string& t) {
	if (t.size() == 0) {
		return 0;
	}
	vector<int> next(t.size());
	getNext(&next[0], t);
	for (int i = 0; i < next.size(); i++) {
		printf("next[%d] = %d, ", i, next[i]);
	}
	int j = -1; // // 因为next数组里记录的起始位置为-1
	for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
		while (j >= 0 && s[i] != t[j + 1]) { // 不匹配
			j = next[j]; // j 寻找之前匹配的位置
		}
		if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动
			j++; // i的增加在for循环里
		}
		if (j == (t.size() - 1)) { // 文本串s里出现了模式串t
			return (i - t.size() + 1);
			//return (i - j);
		}
	}
	return -1;
}

KMP优化版本，不算官方，自己测试出来的：

c++

    void getNext(int* next, string& s) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++) {
            while (j >= 0 && s[j + 1] != s[i]) {
                j = next[j];
            }
            if (s[j + 1] == s[i]) {
                j++;
            }
            next[i] = j;
            //  next[i] = (j >= 0 && s[i] == s[j]) ? next[j] : j;
        }
        for(int i = 0; i <s.size();i++){
            if(i > 0 && s[next[i-1] + 1] == s[i] && next[i-1] >= 0){
                next[i-1] = next[next[i-1]];
            }
        }
    }

4.4 list

list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。

5、二叉树

5.1 二叉树的定义

c++

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

1、二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
2、二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

5.2 构建树

依据中序和后序构建一棵二叉树

c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Tree {
public:
	struct TreeNode {
		int val;
		TreeNode* left;
		TreeNode* right;
		TreeNode() : val(0), left(nullptr), right(nullptr) {}
		TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
		TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
	};
	void printTree(TreeNode* node, int depth) {
		if (node == nullptr) return;
		printTree(node->right, depth + 1);
		for (int i = 0; i < depth; ++i) cout << "    ";
		cout << node->val << endl;
		printTree(node->left, depth + 1);
	}
public:
	TreeNode* buildTree(vector<int> inorder, vector<int> postorder) {
		// 1、判断是否为空
		if (postorder.size() == 0) {
			return nullptr;
		}
		// 2、找出根节点
		int rootValue = postorder.back();
		TreeNode* root = new TreeNode(rootValue);

		// 3、找出根节点在中序遍历中的位置
		int index = 0;
		for (index = 0; index < inorder.size(); index++) {
			if (inorder[index] == rootValue) {
				break;
			}
		}
		if (postorder.size() == 1) {
			return root;
		}
		// 4、切分中序和后序遍历数据
		vector<int> leftInorder(inorder.begin(), inorder.begin() + index);
		vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());
		postorder.pop_back();
		vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
		vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
		// 5、递归调用
		root->left = buildTree(leftInorder, leftPostorder);
		root->right = buildTree(rightInorder, rightPostorder);
		return root;
	}
	void deleteTree(TreeNode* root) {
		if (root == nullptr) {
			return;
		}
		if (root->left) {
			deleteTree(root->left);
		}
		if (root->right) {
			deleteTree(root->right);
		}
		delete root;

	}
	void print(TreeNode* root) {
		printTree(root, 0);
	}
};
int main() {
	vector<int> InOrder = {9, 3, 15, 20, 7};
	vector<int> PostOrder = {9, 15, 7, 20, 3};
	Tree tree;
	Tree::TreeNode* root = tree.buildTree(InOrder, PostOrder);
	// 打印构建的树
	cout << "构建的二叉树结构如下：" << endl;
	tree.print(root);

	// 释放内存
	tree.deleteTree(root);

	return 0;
}
/*
构建的二叉树结构如下：
        7
    20
        15
3
    9
*/

5.3 先序+中序->后序

已知先序遍历数组和中序遍历数组，请问如何求后序遍历数组

c++


#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// 哈希表用于快速查找中序遍历中元素的位置
unordered_map<int, int> index_map;

// 递归函数：根据先序和中序生成后序遍历
void buildPostOrder(const vector<int>& preorder, int pre_start, int pre_end, const vector<int>& inorder, int in_start, int in_end, vector<int>& postorder) {
	if (pre_start > pre_end) return;

	int root_val = preorder[pre_start];
	int in_root = index_map[root_val];

	int left_size = in_root - in_start;

	// 递归左子树
	buildPostOrder(preorder, pre_start + 1, pre_start + left_size,
		inorder, in_start, in_root - 1, postorder);

	// 递归右子树
	buildPostOrder(preorder, pre_start + left_size + 1, pre_end,
		inorder, in_root + 1, in_end, postorder);

	// 后序遍历：最后添加根节点
	postorder.push_back(root_val);
}

// 主函数：输入先序和中序，返回后序
vector<int> getPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
	int n = preorder.size();
	for (int i = 0; i < n; ++i) {
		index_map[inorder[i]] = i;  // 构建值到索引的映射
	}

	vector<int> postorder;
	buildPostOrder(preorder, 0, n - 1, inorder, 0, n - 1, postorder);
	return postorder;
}

// 测试代码
int main() {
	vector<int> preorder = { 9, 2, 1, 4, 7, 6, 10, 8 };
	vector<int> inorder = { 1, 2, 4, 9, 10, 6, 7 ,8};

	vector<int> postorder = getPostOrder(preorder, inorder);

	cout << "Postorder traversal: ";
	for (int val : postorder) {
		cout << val << " ";
	}
	cout << endl;

	return 0;
}
// Postorder traversal: 1 4 2 10 6 8 7 9

5.4 有序数组->二叉搜索树

已知一个有序数组，依据这个构建一个二叉搜索树

c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() {}
	TreeNode(int x): val(x) {}
	TreeNode(int x, TreeNode*left): val(x), left(left) {}
	TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right) {}
};
class Tree {
public:
	// 区间是 [ )
	TreeNode* buildTree(vector<int>& nums, int left, int right) {
		if (left == right) {
			return nullptr;
		}
		int mid = left + (right - left) / 2;
		TreeNode* root = new TreeNode(nums[mid]);
		root->left = buildTree(nums, left, mid);
		root->right = buildTree(nums, mid + 1, right);
		return root;
	}
	void print(TreeNode* root, int depth) {
		if (root == nullptr) {
			return;
		}
		print(root->right, depth + 1);
		for (int i = 0; i < depth; ++i) {
			printf("    ");
		}
		printf("%d\n", root->val);
		print(root->left, depth + 1);
	}
};
int main() {
	vector<int> array = {1, 4, 7, 8, 10, 11};
	Tree tree;
	TreeNode* root = tree.buildTree(array, 0, array.size());
	printf("构建的树结构如下：\n");
	tree.print(root, 0);

	return 0;
}
/*
构建的树结构如下：
    11
        10
8
        7
    4
        1
*/

6、回溯算法

回溯三部曲

1、回溯函数模板返回值以及参数

2、回溯函数终止条件

3、回溯搜索的遍历过程

c++

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

7、动态规划

解决的问题：

动规基础问题、背包问题、打家劫舍、股票问题、子序列问题

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

7.1 背包问题

7.1.1 `0-1背包问题`

==题目：有n件物品和一个最多能背容量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。==

举例说明：背包最大重量为4。物品为：

	容量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

（1）二维dp数组

1、dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2、递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3、dp数组初始化

	容量：1	容量：2	容量：3	容量：4
物品0	15	15	15	15
物品1	任意赋值	任意赋值	任意赋值	任意赋值
物品2	任意赋值	任意赋值	任意赋值	任意赋值

4、确定遍历顺序（一般是先遍历物品，再遍历背包）

5、打印dp数组

6、整体代码：

c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int bagProblem(vector<int> weight, vector<int> value, int volume) {
	int m = weight.size(); // 物品数量
	int n = volume;  // 背包容量
	vector<vector<int>> dp(m, vector<int>(n + 1));
	int i, j, k;
	// 初始化dp数组
	for (i = 0; i < m; i++) {
		dp[i][0] = 0;
	}
	for (i = 0; i < weight[0]; i++) {
		dp[0][i] = 0;
	}
	for (i = weight[0]; i <= n; i++) {
		dp[0][i] = value[0];
	}
	// 遍历dp数组
	for (i = 1; i < m; i++) {
		for (j = 1; j <= n; j++) {
			if (j < weight[i]) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
			}
			
		}
	}
	// 打印dp数组
	for (i = 0; i < m; i++) {
		for (j = 0; j <= n; j++) {
			printf("dp[%d][%d] = %d\t", i, j, dp[i][j]);
		}
		printf("\n");
	}
	return dp[m - 1][n];

}
int main() {
	vector<int> weight = { 1, 3, 4 };
	vector<int> value = { 15, 20, 30 };
	int volume = 4;
	printf("result = %d", bagProblem(weight, value, volume));
	return 0;
}
/*
dp[0][0] = 0    dp[0][1] = 15   dp[0][2] = 15   dp[0][3] = 15   dp[0][4] = 15
dp[1][0] = 0    dp[1][1] = 15   dp[1][2] = 15   dp[1][3] = 20   dp[1][4] = 35
dp[2][0] = 0    dp[2][1] = 15   dp[2][2] = 15   dp[2][3] = 20   dp[2][4] = 35
result = 35
*/

NOTE

1、遍历dp数组的两个for循环可以颠倒顺序

（2）一维dp数组

1、dp数组的含义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2、递推公式

二维dp数组的递推公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

一维dp数组，其实就上一层 dp[i-1] 这一层拷贝的 dp[i]来。

所以在上面递推公式的基础上，去掉i这个维度就好。

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

3、dp数组初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？

看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

4、遍历顺序

c++

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

IMPORTANT

1、必须先遍历物品，在遍历背包容量

2、物品是顺序遍历，背包是倒序遍历，确保每个物品只能使用一次

5、打印dp数组

6、代码示例

c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int bagProblem(vector<int> weight, vector<int> value, int volume) {
	int m = weight.size(); // 物品数量
	int n = volume;  // 背包容量
	vector<int> dp(n + 1);
	int i, j, k;
	// 初始化dp数组
	for (i = 0; i <= n; i++) {
		dp[i] = 0;
	}
	// 遍历dp数组
	for (i = 0; i < m; i++) {
		for (j = n; j >= weight[i]; j--) {
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
		}
	}
	// 打印dp数组
	for (j = 0; j <= n; j++) {
		printf("dp[%d] = %d\t", j, dp[j]);
	}
	printf("\n");

	return dp[n];
}
int main() {
	vector<int> weight = { 1, 3, 4 };
	vector<int> value = { 15, 20, 30 };
	int volume = 4;
	printf("result = %d", bagProblem(weight, value, volume));
	return 0;
}
/*
dp[0] = 0       dp[1] = 15      dp[2] = 15      dp[3] = 20      dp[4] = 35
result = 35
*/

（3）拓展

问题1：不要求装满背包，求能获得的最大总价值；

问题2、要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 0。

解决：

1）二维dp数组

对于二维dp数组，第一维度（行）表示物品(n)，第二维度（列）表示背包容量(m)

1、dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2、递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3、dp数组初始化

对于初始化，第一列表示装进背包容量为0的方法所得到的最大价值，很明显是0；

对于第一行，初始化有分别，包括求下面两个不同的问题：

（1）如果要求问题1，初始化方法跟之前的类似，当容量小于weight[0]时，初始化为0，当容量大于等于weight[0]时，初始化为value[0]；

（2）如果要求问题2，那么如下初始化：

当容量等于weight[0]时，初始化为value[0]；其余的都初始化为最小值(INT_MIN)，注意需要判断最大容量和weight[0]的关系

==在这个基础上进行动态规划，求得的dp[n-1][M]表示恰好装满背包的最大价值==

==此时遍历dp数组的最后一行，找出最大值，最大值就是问题1：不要求装满背包，求能获得的最大总价值==，大致代码如下：

c++

int max1  = INT_MIN;
for (int j = 0; j <= m; j++) {
    if (max1 < dp[n - 1][j]) {
        max1 = dp[n - 1][j];
    }
}

2）一维dp数据

1、dp数组的含义

对于一维dp数组，第一维度表示背包容量(m)

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2、递推公式

二维dp数组的递推公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

一维dp数组，其实就上一层 dp[i-1] 这一层拷贝的 dp[i]来。

所以在上面递推公式的基础上，去掉i这个维度就好。

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

3、dp数组的初始化

dp[0]表示装进背包容量为0的方法所得到的最大价值，很明显是0；

对于其他的数据，初始化有分别，包括求下面两个不同的问题：

（1）如果要求问题1，初始化方法跟之前的类似，其余的元素全部初始化为0

（2）如果要求问题2，那么其余的元素全部初始化为INT_MIN

==在这个基础上进行动态规划，求得的dp[M]表示恰好装满背包的最大价值==

==此时遍历dp数组，找出最大值，最大值就是问题1：不要求装满背包，求能获得的最大总价值==，大致代码如下：

c++

int max1 = 0;
for(int i = 0;i<=m;i++){
    if(max1 < dp[i]){
        max1 = dp[i];
    }
}

3）示例：

c++

### 题目描述

你有一个背包，最大容量为 \( V \)。现有 \( n \) 件物品，第 \( i \) 件物品的体积为 \( v_i \)，价值为 \( w_i \)。研究人员提出以下两种装填方案：
1. 不要求装满背包，求能获得的最大总价值；
2. 要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 0。

### 输入描述:

第一行输入两个整数 \( n \) 和 \( V \)（\( 1 \leq n, V \leq 10^3 \)），分别表示物品数量与背包容量。
此后 \( n \) 行，第 \( i \) 行输入两个整数 \( v_i, w_i \)（\( 1 \leq v_i, w_i \leq 10^3 \)），分别表示第 \( i \) 件物品的体积与价值。

### 输出描述:

输出两行：
1. 第一行输出方案 1 的答案；
2. 第二行输出方案 2 的答案（若无解输出 0）。

### 示例：输入
3 5
2 10
4 5
1 4
#### 示例：输出
14
9

代码：

c++

#include<iostream>
#include<climits>
#include<vector>
using namespace std;

// 解决01背包问题的函数：weight是物品重量数组，value是物品价值数组，n是物品数量，V是背包容量
void solve(vector<int>& weight, vector<int>& value, int n, int V) {
    // dp[j] 表示容量为j时能获得的最大价值，初始化为极小值（表示不可达）
    vector<int> dp(V + 1, INT_MIN);
    dp[0] = 0;           // 容量为0时最大价值为0（不选任何物品）

    int max1 = 0;        // 用于记录所有容量下能达到的最大价值（不一定装满背包）

    // 遍历每个物品
    for (int i = 0; i < n; i++) {
        // 从背包容量V倒序遍历到当前物品重量，避免重复使用同一个物品（01背包特性）
        for (int j = V; j >= weight[i]; j--) {
            // 状态转移：选或不选第i个物品，取最大值
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

            // 更新全局最大价值（不论是否装满背包）
            if (dp[j] > max1) {
                max1 = dp[j];
            }
        }
    }

    // 如果容量为V时的最大价值仍为负数（不可达），则设为0（题目要求？或避免负值输出）
    if (dp[V] < 0) {
        dp[V] = 0;
    }

    // 输出两个结果：
    cout << max1 << endl;     // 所有容量中能获得的最大价值（不一定装满）
    cout << dp[V] << endl;    // 容量恰好为V时能获得的最大价值（可能为0）
}

// 主函数：程序入口
int main() {
    int n, V;                 // n：物品数量；V：背包容量
    cin >> n >> V;            // 从标准输入读取n和V

    vector<int> weight(n);    // 存储每个物品的重量
    vector<int> value(n);     // 存储每个物品的价值

    // 读取每个物品的重量和价值
    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }

    // 调用解决函数
    solve(weight, value, n, V);

    return 0;                 // 程序正常结束
}

另一种思路，如果要求问题2，那么其余的元素全部初始化为-1，在进行状态转移的时候进行判断：

c++

#include<iostream>
#include<vector>
#include<cmath>
#include<climits>
using namespace std;

// 解决 0-1 背包问题：给定物品的重量和价值，求最大价值
// 同时输出：
//   1. 所有可行容量下的最大价值（max1）
//   2. 恰好容量为 V 时的最大价值（dp[V]）
void solve(vector<int>& weights, vector<int>& value, int V) {
    // dp[j] 表示容量为 j 时的最大价值，-1 表示不可达
    vector<int> dp(V + 1, -1);
    dp[0] = 0; // 初始状态：容量为 0 时价值为 0

    int max1 = INT_MIN; // 记录所有容量下的最大价值

    // 遍历每一个物品
    for (int i = 0; i < weights.size(); i++) {
        // 倒序遍历容量，避免一个物品被重复使用
        for (int j = V; j >= 0; j--) {
            // 如果能放下当前物品，且容量 j-weights[i] 可达
            if (j - weights[i] >= 0 && dp[j - weights[i]] != -1) {
                // 更新当前容量 j 的最大价值
                dp[j] = max(dp[j], dp[j - weights[i]] + value[i]);
            }
            // 更新所有容量下的最大价值
            if (max1 < dp[j]) {
                max1 = dp[j];
            }
        }
    }

    // 如果容量 V 不可达，则价值为 0
    if (dp[V] == -1) {
        dp[V] = 0;
    }

    // 输出结果
    cout << max1 << endl; // 所有容量下的最大价值
    cout << dp[V] << endl; // 容量恰好为 V 的最大价值
}

int main() {
    int n, V;
    cin >> n >> V; // 输入物品数量和背包容量
    vector<int> weights(n), value(n);

    // 输入每个物品的重量和价值
    for (int i = 0; i < n; i++) {
        cin >> weights[i] >> value[i];
    }

    // 调用函数解决问题
    solve(weights, value, V);
    return 0;
}

7.1.2 `完全背包问题`

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件

举例说明：背包最大重量为4。物品为：

	容量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

（1）二维dp数组

1、dp[i][j] 表示从下标为[0-i]的物品里任意取，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。

2、递归公式： dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i])（注意，完全背包二维dp数组和 01背包二维dp数组递推公式的区别，01背包中是 dp[i - 1][j - weight[i]] + value[i])）

3、dp数组初始化

	容量：1	容量：2	容量：3	容量：4
物品0	15	30	45	60
物品1	任意赋值	任意赋值	任意赋值	任意赋值
物品2	任意赋值	任意赋值	任意赋值	任意赋值

4、确定遍历顺序（一般是先遍历物品，再遍历背包）

5、打印dp数组

6、整体代码

c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int bagProblem(vector<int> weight, vector<int> value, int volume) {
	int m = weight.size(); // 物品数量
	int n = volume;  // 背包容量
	vector<vector<int>> dp(m, vector<int>(n + 1));
	int i, j, k;
	// 初始化dp数组
	for (i = 0; i < m; i++) {
		dp[i][0] = 0;
	}
	for (i = 0; i < weight[0]; i++) {
		dp[0][i] = 0;
	}
	for (i = weight[0]; i <= n; i++) {
		dp[0][i] = dp[0][i - weight[0]] + value[0];
	}
	// 遍历dp数组
	for (i = 1; i < m; i++) {   // 遍历物品
		for (j = 1; j <= n; j++) {  // 遍历背包
			if (j < weight[i]) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
			}
		}
	}
	// 打印dp数组
	for (i = 0; i < m; i++) {
		for (j = 0; j <= n; j++) {
			printf("dp[%d][%d] = %d\t", i, j, dp[i][j]);
		}
		printf("\n");
	}
	return dp[m - 1][n];

}
int main() {
	vector<int> weight = { 1, 3, 4 };
	vector<int> value = { 15, 20, 30 };
	int volume = 4;
	printf("result = %d", bagProblem(weight, value, volume));
	return 0;
}
/*
dp[0][0] = 0    dp[0][1] = 15   dp[0][2] = 30   dp[0][3] = 45   dp[0][4] = 60
dp[1][0] = 0    dp[1][1] = 15   dp[1][2] = 30   dp[1][3] = 45   dp[1][4] = 60
dp[2][0] = 0    dp[2][1] = 15   dp[2][2] = 30   dp[2][3] = 45   dp[2][4] = 60
result = 60
*/

TIP

1、改动点：dp数组初始化

c++

for (i = weight[0]; i <= n; i++) {
	dp[0][i] = dp[0][i - weight[0]] + value[0];
}

2、遍历dp数组的两个for循环可以颠倒顺序

（2）一维dp数组

1、dp数组的含义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2、递推公式

二维dp数组的递推公式为： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

对于一维dp数组，其实就上一层 dp[i-1] 这一层拷贝的 dp[i]来。

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

3、dp数组初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？

看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

4、遍历顺序

c++

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

IMPORTANT

1、遍历背包容量的时候，需要采用正序遍历

2、对于纯完全背包问题，其for循环的先后循环是可以颠倒的。

5、打印dp数组

6、代码示例

c++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int bagProblem(vector<int> weight, vector<int> value, int volume) {
	int m = weight.size(); // 物品数量
	int n = volume;  // 背包容量
	vector<int> dp(n + 1);
	int i, j, k;
	// 初始化dp数组
	for (i = 0; i <= n; i++) {
		dp[i] = 0;
	}
	// 遍历dp数组
	for (i = 0; i < m; i++) {
		//for (j = n; j >= weight[i]; j--) {
		for (j = 0; j <= n; j++) {
			if (j >= weight[i]) {
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}
	}
	// 打印dp数组
	for (j = 0; j <= n; j++) {
		printf("dp[%d] = %d\t", j, dp[j]);
	}
	printf("\n");

	return dp[n];
}
int main() {
	vector<int> weight = { 1, 3, 4 };
	vector<int> value = { 15, 20, 30 };
	int volume = 4;
	printf("result = %d", bagProblem(weight, value, volume));
	return 0;
}
/*
dp[0] = 0       dp[1] = 15      dp[2] = 15      dp[3] = 20      dp[4] = 35
result = 35
*/

改动点：遍历背包容量的时候使用正序遍历

c++

	for (i = 0; i < m; i++) {
		//for (j = n; j >= weight[i]; j--) {
		for (j = 0; j <= n; j++) {
			if (j >= weight[i]) {
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}
	}

7.1.3总结

对于0-1背包和完全背包问题：

1、对于0-1背包，

二维dp[i][j]数组，i表示物品，j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	✔️	✔️	✖️	✖️
先遍历背包，再遍历物品	✔️	✖️	✖️	✖️

一维dp[j]数组,j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	✖️（完全背包）	✔️	✖️	✖️
先遍历背包，再遍历物品	✖️	✖️	✖️	✖️

2、对于完全背包；

二维dp[i][j]数组，i表示物品，j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	✔️	✖️	✖️	✖️
先遍历背包，再遍历物品	✔️	✖️	✖️	✖️

一维dp[j]数组,j表示背包

遍历顺序	顺序+顺序	顺序+倒序	倒序+顺序	倒序+倒序
先遍历物品，再遍历背包	✔️	✖️	✔️（自己测试的，可行，没有找到网上对应的讲解）	✖️
先遍历背包，再遍历物品	✔️	✔️ （自己测试的，可行，没有找到网上对应的讲解）	✖️	✖️

- 任务完成: ✅ - 有错误: ❎

含义	Emoji 短代码	效果
带框的叉（红叉）	`:negative_squared_cross_mark:`	❌
带框的对（绿勾）	`:white_check_mark:`	✅
勾（对）	`:heavy_check_mark:`	✔️
交叉	`:heavy_multiplication_x:`	✖️

步骤 \ 类型	0-1 背包（二维）	完全背包（二维）	0-1 背包（一维）	完全背包（一维）
1. dp数组含义	`dp[i][j]` 表示从前 i 个物品中选，容量为 j 的背包最大价值	同左，物品可重复选	`dp[j]` 表示容量为 j 时最大价值	同左
2. 递推公式	`dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])`	`dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i]] + value[i])`	`dp[j] = max(dp[j], dp[j-weight[i]] + value[i])`（倒序）	`dp[j] = max(dp[j], dp[j-weight[i]] + value[i])`（正序）
3. 初始化	第一列全为0，第一行：当i<weight[0]时为0，否则为value[0]	第一列全为0，第一行：当i<weight[0]时为0，否则进行累加	`dp[0] = 0`，其余为 0	`dp[0] = 0`，其余为 0
4. 遍历顺序	先物品 `i`，再容量 `j`（遍历物品和背包的顺序可以调换）	先物品 `i`，再容量 `j`（遍历物品和背包的顺序可以调换）	先物品 `i`，再容量 `j`（j 倒序，遍历物品和背包的顺序不能调换）	先物品 `i`，再容量 `j`（j 正序，遍历物品和背包的顺序可以调换）

对于完全背包的一维数组，如果问题是：装满这个背包有多少种方法，那么：
1、先遍历背包再遍历物品，强调物品的顺序，用于求排列数
2、先遍历物品再遍历背包，不强调物品的顺序，用于求组合数

7.2 买卖股票系列

买卖股票的最佳时机

力扣题目链接

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

分析：

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0] 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i] 那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]，也可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1] 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0] 同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

8 图论

8.2 并查集（Union-Find）

8.2.1 概念与核心思想

1、定义

并查集 是一种树型数据结构（双亲表示法存储的结构），用于处理不相交集合的合并与查询问题。
并查集主要有两个功能：
- 将两个元素添加到一个集合中（合并）。
- 判断两个元素在不在同一个集合（查找）。
支持以下操作：
- MakeSet：创建单元素集合。
- Find：确定元素所属集合的代表（根节点）。
- Union：合并两个集合。

2、核心思想

每个集合用一棵树表示，树的根节点作为集合的标识。
通过递归或迭代查找根节点，判断两个元素是否属于同一集合。
合并时通过优化策略（如按秩合并）保持树的平衡性。

8.2.2 基本操作与实现

1、数据结构

father 数组：记录每个节点的父节点。
rank 数组（可选）：记录树的高度（用于按秩合并优化）。
size 数组（可选）：记录集合的大小（用于重量权衡合并）。

2、初始化

c++

#define MAX 1000
int father[MAX];
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i; // 每个节点初始为自己的父节点
        //rank[i] = 0;   // 初始树的高度为0
    }
}

查找（Find）

路径压缩：将路径上的所有节点直接指向根节点，减少后续查找时间。

c++

// 并查集里寻根的过程
int find(int u) {
    if (u == father[u]) return u;
    else return father[u] = find(father[u]); // 路径压缩
}

合并（Union）

按秩合并：将较小的树合并到较大的树上，避免树的高度增加。

c++

// 将v，u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

5、判断是否在同一个集合里

c++

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

6、总体代码模板

c++

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

8.2.3 优化策略和复杂度分析

1、路径压缩

目的：缩短查找路径，使树扁平化。
效果：近似常数时间复杂度 $O (α (n))$ （阿克曼函数反函数，增长极慢）。

2、按秩合并

目的：保持树的高度尽可能小。
实现：通过 rank 或 size 数组记录集合大小，合并时选择较小的树挂到较大的树上。

3、重量权衡合并

目的：合并时优先将小树合并到大树上，减少树的高度。
适用场景：适用于需要动态调整集合大小的场景。

4、复杂度分析

操作	时间复杂度（近似）	空间复杂度
初始化	$O (n)$	$O (n)$
查找（Find）	$O (α (n))$	$O (1)$
合并（Union）	$O (α (n))$	$O (1)$

说明： $α (n)$ 是阿克曼函数的反函数，增长极慢，可视为常数。

9 哈希表

9.1 定义

哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里

9.2 哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set （集合）
map(映射)

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::set	红黑树	有序	否	否	O(log n)	O(log n)
std::multiset	红黑树	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	无序	否	否	O(1)	O(1)

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	key不可重复	key不可修改	O(logn)	O(logn)
std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

虽然std::set和std::multiset 的底层实现基于红黑树而非哈希表，它们通过红黑树来索引和存储数据。不过给我们的使用方式，还是哈希法的使用方式，即依靠键（key）来访问值（value）。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。std::map也是一样的道理。

10、贪心算法

贪心算法一般分为如下四步：

将问题分解为若干个子问题

找出适合的贪心策略

求解每一个子问题的最优解

将局部最优解堆叠成全局最优解

53. 最大子数组和

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

p[3] - p[0] = p[3] - p[2] + p[2] - p[1] + p[1] - p[0], 每次收获正数即可

c++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            int temp = prices[i] - prices[i - 1];
            if (temp > 0) {
                result += temp;
            }
        }
        return result;
    }
};

11、其他

1、螺旋遍历二维数组

https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/

==处理原则：左闭右闭==

c++

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        if(array.size() == 0){
            return {};
        }
        int n = array.size(), m = array[0].size(), k = 0;
        vector<int> result(n * m);
        int left = 0, right = m - 1, top = 0, bottom = n - 1;
        while (true) {
            for (int j = left; j <= right; j++) {
                result[k++] = array[top][j];
            }
            if (++top > bottom) {
                break;
            }
            for (int i = top; i <= bottom; i++) {
                result[k++] = array[i][right];
            }
            if (--right < left) {
                break;
            }
            for (int j = right; j >= left; j--) {
                result[k++] = array[bottom][j];
            }
            if (--bottom < top) {
                break;
            }
            for (int i = bottom; i >= top; i--) {
                result[k++] = array[i][left];
            }
            if (++left > right) {
                break;
            }
        }
        return result;
    }
};

2、二分图：

题目https://www.luogu.com.cn/problem/P3386：

bash

# P3386 【模板】二分图最大匹配

## 题目描述

给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

## 输入格式

输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。

接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

## 输出格式

输出一行一个整数，代表二分图最大匹配的边数。

## 输入输出样例 #1

### 输入 #1

```
1 1 1
1 1
```

### 输出 #1

```
1
```

## 输入输出样例 #2

### 输入 #2

```
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1
```

### 输出 #2

```
2
```

## 说明/提示

#### 数据规模与约定

对于全部的测试点，保证：
- $1 \leq n, m \leq 500$。
- $1 \leq e \leq 5 \times 10^4$。
- $1 \leq u \leq n$，$1 \leq v \leq m$。

**不保证给出的图没有重边**。

代码：

c++

#include<iostream>
#include<vector>
using namespace std;
bool dfs(vector<vector<int>>& grid, vector<bool>& used, vector<int>& linker, int u) {
	for (int j = 0; j < grid[0].size(); j++) {
		if (grid[u][j] != 0 && !used[j]) {
			used[j] = true;
			if (linker[j] == -1 || dfs(grid, used, linker, linker[j])) {
				linker[j] = u;
				return true;
			}
		}
	}
	return false;
}
void solve(vector<vector<int>>& grid, int n, int m) {
	int result = 0;
	vector<int>linker(m + 1, -1); // 存放右节点链接的左节点
	vector<bool>used(n + 1, false);
	for (int i = 1; i <= n; i++) {
		used.assign(used.size(), false);
		if (dfs(grid, used, linker, i)) {
			result++;
		}
	}
	cout << result << endl;
}
int main() {
	int n, m, e, u, v;
	cin >> n >> m >> e;
	vector<vector<int>>grid(n + 1, vector<int>(m + 1, 0));
	for (int i = 0; i < e; i++) {
		cin >> u >> v;
		grid[u][v] = 1;
	}
	solve(grid, n, m);
	return 0;
}

2、关闭同步流动

c++

ios::sync_with_stdio(false);
cin.tie(nullptr);  // 这两句用于关闭流同步，但关流后不可以混用 cin / scanf

3、双向链表数组实现

题目：

markdown

# P1160 队列安排

## 题目描述

一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $1\sim N$，他采取如下的方法：

1. 先将 $1$ 号同学安排进队列，这时队列中只有他一个人；

2. $2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 $M$ 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

## 输入格式

第一行一个整数 $N$，表示了有 $N$ 个同学。

第 $2\sim N$ 行，第 $i$ 行包含两个整数 $k,p$，其中 $k$ 为小于 $i$ 的正整数，$p$ 为 $0$ 或者 $1$。若 $p$ 为 $0$，则表示将 $i$ 号同学插入到 $k$ 号同学的左边，$p$ 为 $1$ 则表示插入到右边。

第 $N+1$ 行为一个整数 $M$，表示去掉的同学数目。

接下来 $M$ 行，每行一个正整数 $x$，表示将 $x$ 号同学从队列中移去，如果 $x$ 号同学已经不在队列中则忽略这一条指令。

## 输出格式

一行，包含最多 $N$ 个空格隔开的整数，表示了队列从左到右所有同学的编号。

## 输入输出样例 #1

### 输入 #1

```
4
1 0
2 1
1 0
2
3
3
```

### 输出 #1

```
2 4 1
```

## 说明/提示

**【样例解释】**

将同学 $2$ 插入至同学 $1$ 左边，此时队列为：

`2 1`

将同学 $3$ 插入至同学 $2$ 右边，此时队列为：

`2 3 1`  

将同学 $4$ 插入至同学 $1$ 左边，此时队列为：

`2 3 4 1`  

将同学 $3$ 从队列中移出，此时队列为：

`2 4 1`  

同学 $3$ 已经不在队列中，忽略最后一条指令

最终队列：

`2 4 1`  

**【数据范围】**

对于 $20\%$ 的数据，$1\leq N\leq 10$。

对于 $40\%$ 的数据，$1\leq N\leq 1000$。

对于 $100\%$ 的数据，$1<M\leq N\leq 10^5$。

c++

#include<iostream>
using namespace std;
const int N = 1e5 + 5;
int l[N], e[N], r[N], add[N];
int idx;
void init() {
	r[0] = 1, l[1] = 0, idx = 2;
	add[0] = 0;
}
void insert_right(int k, int val) {
	e[idx] = val;
	l[idx] = k;
	r[idx] = r[k];
	l[r[k]] = idx;
	r[k] = idx;
	add[++add[0]] = idx++;
}
void insert_left(int k, int val) {
	e[idx] = val;
	l[idx] = l[k];
	r[idx] = k;
	r[l[k]] = idx;
	l[k] = idx;
	add[++add[0]] = idx++;
}
void remove(int k) {
	l[r[k]] = l[k];
	r[l[k]] = r[k];
	e[k] = 0;
	add[0]--;
}
void printList() {
	for (int i = r[0]; i != 1; i = r[i]) {
		printf("%d ", e[i]);
	}
}
int main() {
	init();
	int n, k, p, m, x;
	scanf("%d", &n);
	insert_right(0, 1);
	for (int i = 2; i <=n;i++) {
		scanf("%d %d", &k, &p);
		if (p == 0) {
			insert_left(add[k], i);
		}
		else {
			insert_right(add[k], i);
		}
	}
	scanf("%d", &m);
	while (m--) {
		scanf("%d", &x);
		if (e[add[x]] != 0) {
			remove(add[x]);
		}
	}
	printList();
	return 0;
}

收集常见题目和代码 ​

1、c++ 快速入门 ​

1.1 数组 ​

1.1.1 BubbleSort ​

1.1.2 memset用法 ​

1.1.3 字符串数组 ​

1.1.4 sscanf 和 sprintf 用法 ​

1.2 结构体 ​

1.3 补充 ​

1.3.1 两个浮点数比大小 ​

2、算法初步 ​

2.1 计算两个日期之间的天数 ​

2.3 sort函数的使用 ​

2.4 打印n个整数的全排列信息 ​

2.5 n皇后问题 ​

2.5.1 解决方法1 ​

2.5.2 进阶用法 ​

2.5 二分查找 ​

2.5.1 求平方根 ​

2.5.2 拓展 ​

2.6 归并排序 ​

2.6.1 序列合并问题 ​

2.6.2 归并排序代码递归实现 ​

2.7 快速排序 ​

2.7.1 代码实现 ​

2.7.2 改进 ​

2.8 双指针思路 ​

1、判断链表是否有环 ​

2、判断链表是否是回文链表 ​

2.9 快速幂 ​

3、数学问题 ​

3.1 最大公约数和最小公倍数 ​

3.1.1 最大公约数 ​

3.1.2 最小公倍数 ​

3.2 素数 ​

3.2.1 枚举法 ​

3.2.2 埃氏筛选法 ​

3.3.3 总结 ​

3.3 分解质因数 ​

3.4 大数算法 ​

3.4.1 大数之间的加法（自定义结构体） ​

3.4.2 大数之间的加减乘除（string实现） ​

3.4.3 另一种方法 ​

3.4.4 乘法（高精度 * 高精度） ​

4、C++标准模板库 ​

4.1 vector 容器 ​

4.1.1 迭代器访问 ​

4.1.2 常用函数 ​

4.2 set 集合 ​

4.2.1 迭代器访问 ​

4.2.2 常用函数 ​

4.3 String 字符串 ​

KMP算法： ​

4.4 list ​

5、二叉树 ​

5.1 二叉树的定义 ​

5.2 构建树 ​

5.3 先序+中序->后序 ​

5.4 有序数组->二叉搜索树 ​

6、回溯算法 ​

7、动态规划 ​

7.1 背包问题 ​

7.1.1 0-1背包问题 ​

（1）二维dp数组 ​

（2）一维dp数组 ​

（3）拓展 ​

7.1.2 完全背包问题 ​

（1）二维dp数组 ​

（2）一维dp数组 ​

7.1.3总结 ​

7.2 买卖股票系列 ​

8 图论 ​

8.2 并查集（Union-Find） ​

8.2.1 概念与核心思想 ​

8.2.2 基本操作与实现 ​

8.2.3 优化策略和复杂度分析 ​

9 哈希表 ​

9.1 定义 ​

9.2 哈希结构 ​

10、贪心算法 ​

收集常见题目和代码

1、c++ 快速入门

1.1 数组

1.1.1 BubbleSort

1.1.2 `memset`用法

1.1.3 字符串数组

1.1.4 sscanf 和 sprintf 用法

1.2 结构体

1.3 补充

1.3.1 两个浮点数比大小

2、算法初步

2.1 计算两个日期之间的天数

2.3 `sort`函数的使用

2.4 打印n个整数的全排列信息

2.5 n皇后问题

2.5.1 解决方法1

2.5.2 进阶用法

2.5 二分查找

2.5.1 求平方根

2.5.2 拓展

2.6 归并排序

2.6.1 序列合并问题

2.6.2 归并排序代码递归实现

2.7 快速排序

2.7.1 代码实现

2.7.2 改进

2.8 双指针思路

1、判断链表是否有环

2、判断链表是否是回文链表

2.9 快速幂

3、数学问题

3.1 最大公约数和最小公倍数

3.1.1 最大公约数

3.1.2 最小公倍数

3.2 素数

3.2.1 枚举法

3.2.2 埃氏筛选法

3.3.3 总结

3.3 分解质因数

3.4 大数算法

3.4.1 大数之间的加法（自定义结构体）

3.4.2 大数之间的加减乘除（string实现）

3.4.3 另一种方法

3.4.4 乘法（高精度 * 高精度）

4、C++标准模板库

4.1 vector 容器

4.1.1 迭代器访问

4.1.2 常用函数

4.2 set 集合

4.2.1 迭代器访问

4.2.2 常用函数

4.3 String 字符串

KMP算法：

4.4 list

5、二叉树

5.1 二叉树的定义

5.2 构建树

5.3 先序+中序->后序

5.4 有序数组->二叉搜索树

6、回溯算法

7、动态规划

7.1 背包问题

7.1.1 `0-1背包问题`

（1）二维dp数组

（2）一维dp数组

（3）拓展

7.1.2 `完全背包问题`

（1）二维dp数组

（2）一维dp数组

7.1.3总结

7.2 买卖股票系列

8 图论

8.2 并查集（Union-Find）

8.2.1 概念与核心思想

8.2.2 基本操作与实现

8.2.3 优化策略和复杂度分析

9 哈希表

9.1 定义

9.2 哈希结构

10、贪心算法