1. 分布式和集群的区别是什么？

• 分布式：侧重于将任务分拆多个子任务，部署在不同的服务器上，解决计算能力的问题
• 集群：侧重同一个业务，部署在多个服务器上，提高系统可用性和性能。

分布式是一个为了解决单个物理服务器容量和性能瓶颈问题而采用的优化手段。它的核心概念是将一个业务拆分成不同的子业务，并部署在不同的机器上执行，服务之间通过远程调用协同工作，对外提供服务。这种拆分和部署的方式可以大大提高系统的可扩展性、可靠性和性能。

分布式涉及多个技术领域，包括但不限于分布式计算、分布式存储、分布式数据库、分布式文件系统等。这些技术各自有不同的应用场景和优势，如分布式计算可以处理巨量的数据和复杂的计算任务，分布式存储可以实现数据的高可用性和容错性，分布式数据库可以支持大规模并发访问和数据处理等。

Cmake

CMake是很多项目首选的项目构建工具。其次，目前很多开发工具，比如VSCode，Clion都支持使用CMake构建项目。使用Cmake能够更加方便的用一个文件实现对C/C++项目的维护管理。

1 数学建模模型分类

数学建模竞赛常用模型有：评价模型、预测模型、优化模型和数理统计模型。

评价模型

评价模型用于对某个系统、方案或决策进行评估。通过构建合适的指标和评价方法，评价模型能够对不同方案的优劣进行比较和分析。在数学建模比赛中，评价模型通常适用于这类问题：根据问题的特点和需求，设计合适的评价标准和指标，对不同方案或模型的性能进行评估和比较，以帮助做出决策。

问题示例：

• 国赛长江水质的综合评价、
• 上海世博会影响力的定量评估问题、
• 美赛“最好大学教练“问题。

评价模型简介总览

预测模型

预测模型能够根据过去的数据和观察结果，对未来的趋势、行为或结果进行预测和推断，适用于对趋势做预测或者规划类题目。预测模型常用于分析时间序列数据、趋势预测、行为模式预测等问题。在数学建模比赛中，预测模型可以根据给定的数据集或者特定规律，构建合适的数学模型，进行未来趋势预测，从而帮助做出决策或规划。

预测模型介绍总览

数理统计模型

数理统计模型用于对数据进行分析、总结和推断。它能够通过建立概率模型和统计分布，对数据的特征、关系和不确定性进行描述和推断。在数学建模比赛中，数理统计模型可以通过对给定数据集的统计分析，推断出数据的分布规律、相关性、假设检验等，为问题提供支持和解决方案

优化模型

优化模型旨在找到使某个目标函数取得最大或最小值的最优解。优化模型适用于求解最佳决策、资源分配、排产安排等问题。在数学建模比赛中，优化模型可以通过建立数学规划模型，确定决策变量、约束条件和目标函数，利用求解方法寻找最优解或次优解，以优化问题的方案或决策。

模型总览

并查集

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

• Find：确定元素属于哪一个子集。这个确定方法就是不断向上查找找到它的根节点，它可以被用来确定两个元素是否属于同一子集。

• Union：将两个子集合并成同一个集合。

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法如MakeSet，用于建立单元素集合。有了这些方法，许多经典的划分问题可以被解决。

并查集的引入

并查集的重要思想在于，用集合中的一个元素代表集合。我曾看过一个有趣的比喻，把集合比喻成帮派，而代表元素则是帮主。接下来我们利用这个比喻，看看并查集是如何运作的。

最开始，所有大侠各自为战。他们各自的帮主自然就是自己。（对于只有一个元素的集合，代表元素自然是唯一的那个元素）

现在1号和3号比武，假设1号赢了（这里具体谁赢暂时不重要），那么3号就认1号作帮主（合并1号和3号所在的集合，1号为代表元素）。

现在2号想和3号比武（合并3号和2号所在的集合），但3号表示，别跟我打，让我帮主来收拾你（合并代表元素）。不妨设这次又是1号赢了，那么2号也认1号做帮主。

现在我们假设4、5、6号也进行了一番帮派合并，江湖局势变成下面这样：

现在假设2号想与6号比，跟刚刚说的一样，喊帮主1号和4号出来打一架（帮主真辛苦啊）。1号胜利后，4号认1号为帮主，当然他的手下也都是跟着投降了。好了，比喻结束了。如果你有一点图论基础，相信你已经觉察到，这是一个树状的结构，要寻找集合的代表元素，只需要一层一层往上访问父节点（图中箭头所指的圆），直达树的根节点（图中橙色的圆）即可。根节点的父节点是它自己。我们可以直接把它画成一棵树：

用这种方法，我们可以写出最简单版本的并查集代码。

初始化

1
2
3
4
5
6

void init(int n){
	vector<int> fa(n+1,0);
	for(int i = 1;i<=n; ++i){
		fa[i]=i;
	}
}

假如有编号为1, 2, 3, ..., n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。

查询

1
2
3
4
5
6

int find(int& x){
	if(fa[x] == x) return x;
	else{
		return find(fa[x]);
	}
}

我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

合并

1
2
3

void merge(int i, int j) {
    fa[find(i)] = find(j); // 修改的是根节点
}

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。

路径压缩（发生在查询时）

随着merge次数的增加，形成的并查集可能会成为一条长长的链，随着链越来越长，我们想要从底部找到根节点的时间复杂度会成为线性。

怎么解决呢？我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，那么这就是我们的路径压缩：

思想是：在查询的过程中，把沿途的的每个节点的父节点都设为根节点，下一次查询时就可以以\(O(1)\)获得根节点

1
2
3
4
5
6
7

int find(int& x){
	if(fa[x]==x) return x;
	else{
		fa[x] = find(fa[x]);
		return fa[x];
	}
}

按秩合并

有些人可能有一个误解，以为路径压缩优化后，并查集始终都是一个 菊花图 （只有两层的树的俗称）。但其实，由于路径压缩只在 查询 时进行，也只压缩 一条路径，所以并查集最终的结构仍然可能是比较复杂的。例如，现在我们有一棵较复杂的树需要与一个单元素的集合合并： 假如这时我们要merge(7,8)，如果我们可以选择的话，是把7的父节点设为8好，还是把8的父节点设为7好呢？

当然是后者。因为如果把7的父节点设为8，会使树的 深度（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的。而把8的父节点设为7，则不会有这个问题，因为它没有影响到不相关的节点。

这启发我们：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。

我们用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用，时间复杂度接近O(n)，但是会破坏rank的准确性。

初始化（按秩合并）

1
2
3
4
5
6
7

void init(int n){
	vector<int> fa(n+1,0);
	vector<int> rank(n+1,1);
	for(int i = 1;i<=n:==i){
		fa[i]=i;
	}
}

合并

1
2
3
4
5
6
7
8
9
10
11
12

void merge(int i,int j){
	int x=find(i),y=find(j);
	if(rank[x]<=rank[y]){
		fa[x] = y;
	}
	else{
		fa[y] = x;
	}
	if(rank[x]==rank[y]&&x!=y){
		rank[y]++;
	}
}

总结

1. 并查集主要解决的分组管理一类的问题，如果问题能抽象成组与组之间的问题，一般情况下可考虑并查集，并查集的常见思路

是否在一个组； 在一个组的条件； 路径和组在图中都属于连通域，上述组均可替换为路径，问题不变；

2. 并查集的主要难点：

Union时，有的问题已经告诉了分组的信息，有的问题则需要自行挖掘； 一般情况下，并查集底层为一个1d数组，有的问题需要对元素进行编号或者转化与之对应； 在不清楚并查集中到底会存放多少数据时，底层也可以map；

3. 并查集功能是Union也就是将两个组合并成一个组，对于拆分的情况，可以逆序思考问题，例如leetcode803 打砖块

4. 根据问题，也可在并查集底层使用其他数据结构，帮助解决问题；

例题

等式方程的可满足性

题目

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回true，否则返回 false。

分析

分析题目可知，可组等式方程或有关系或无关系，那么因此对所有的方程进行管理，该背景下可考虑使用并查集解决：

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

lass UnionFind {
private:
    vector<int> parent(26,0);

public:
    UnionFind() {
		parent.resize(26);
        //对范围内的赋值0
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int index) {
        if (index == parent[index]) {
            return index;
        }
        parent[index] = find(parent[index]);
        return parent[index];
    }

    void unite(int index1, int index2) {
        parent[find(index1)] = find(index2);
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UnionFind uf;
        for (const string& str: equations) {
            if (str[1] == '=') {
                int index1 = str[0] - 'a';
                int index2 = str[3] - 'a';
                uf.unite(index1, index2);
            }
        }
        for (const string& str: equations) {
            if (str[1] == '!') {
                int index1 = str[0] - 'a';
                int index2 = str[3] - 'a';
                if (uf.find(index1) == uf.find(index2)) {
                    return false;
                }
            }
        }
        return true;
    }
};

参考文献： >并查集

1 框架需求分析

本框架主要为适用于IO密集类型的服务器开发而设计，同时作为框架，一是对于开发者而言应该是简单容易上手层次分明，二是框架本身而言容易扩展，能够依据开发人员的需求添加业务处理。

为了保证框架能够实现基本的要求，其总体需求如下：

• 框架能够较好的应对并发场景。
• 开发人员基于该框架能够轻松的实现自己的业务处理逻辑。

接下来我们会一步一步的构建起这个框架，告诉大家这个框架是怎么实现的，而不是一下子出来一个完整的框架，让大家不知道怎么入手，同时也在这个过程中提出一些问题，让大家对框架更加熟悉，面试中能够回答出来一些关键点。

1 安装

• 1.在ubuntu上直接使用apt-get install安装

  1	sudo apt-get install rabbitmq-server

• 2.启用RabbitMQ管理插件（可选）：

  1	sudo rabbitmq-plugins enable rabbitmq_management

  启用后，可以通过浏览器访问http://<服务器IP>:15672来管理RabbitMQ（默认用户名和密码都是guest）。

• 3.安装C++客户端库,为了使用C++与RabbitMQ进行交互,需要安装一个第三方库，这里用SimpleAmqpClient作为例子(如果你要C++程序要连接RabbitServer必须做的步骤)

  1 2 3 4

  git clone https://github.com/alanxz/SimpleAmqpClient.git mkdir simpleamqpclient-build cd simpleamqpclient-build cmake ..

  在cmake过程中如果报缺失什么依赖，直接安装就好，需要Boost库,librabbitmq-dev等等，cmake..成功后执行一下命令安装:

  1	sudo make install

• 4.启动Rabbit服务器

  1	sudo service rabbitmq-server start

  之后，我们可以从localhost:5672访问，用户名密码都默认是guest

什么是Manacher算法(马拉车算法)

Manachar算法主要是处理字符串中关于回文串的问题的，它本质上是对枚举中心法确定回文串的优化，使得算法可以在 O（n） 的时间处理出以字符串中每一个字符为中心的回文串半径。

由于回文字符串以其长度来分，可以分为奇回文（其长度为奇数）、偶回文（其长度为偶数），一般情况下需要分两种情况来寻找回文，马拉车算法为了简化这一步，对原始字符串进行了处理，在每一个字符的左右两边都加上特殊字符（肯定不存在于原字符串中的字符），让字符串变成一个奇回文简化算法