0%

C++常见算法

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[100]= {4,10,11,30,69,70,96,100};
int b=binary_search(a,a+9,4);//查找成功,返回1
cout<<"在数组中查找元素4,结果为:"<<b<<endl;
int c=binary_search(a,a+9,40);//查找失败,返回0
cout<<"在数组中查找元素40,结果为:"<<c<<endl;
int d=lower_bound(a,a+9,10)-a;
cout<<"在数组中查找第一个大于等于10的元素位置,结果为:"<<d<<endl;
int e=lower_bound(a,a+9,101)-a;
cout<<"在数组中查找第一个大于等于101的元素位置,结果为:"<<e<<endl;
int f=upper_bound(a,a+9,10)-a;
cout<<"在数组中查找第一个大于10的元素位置,结果为:"<<f<<endl;
int g=upper_bound(a,a+9,101)-a;
cout<<"在数组中查找第一个大于101的元素位置,结果为:"<<g<<endl;
}

广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool BFS(const vector<vector<int>> &graph, const int& start, const int& end)
{
size_t len = graph.size();
queue<int> queHanldel;
queHanldel.push(start);

while (!queHanldel.empty()) {
int point = queHanldel.front();
queHanldel.pop();
for (auto nextPoint : graph[point]) {
if (nextPoint == end) {
return true;
}
queHanldel.push(nextPoint);
}
}
return false;
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
void DFS(const int& nwoPoint, const vector<vector<int>> &frondPoint, const int dest, vector<int> &onePath,
vector<vector<int>> &path)
{
if (nwoPoint == dest) {
path.push_back(onePath);
return;
}
for (int point : frondPoint[nwoPoint]) {
onePath.push_back(point);
DFS(point, frondPoint, dest, onePath, path);
onePath.pop_back();
}
}

并查集

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
vector<int> parent;
vector<int> subSize;
void init(int n) {
parent.resize(n);
subSize.resize(n, 1);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}

int findp(int sub)
{
return parent[sub];
}

void merge(int a, int b)
{
int ap = findp(a);
int bp = findp(b);
if (ap == bp) {
return;
}
int newparent = 0;
int oldparent = 0;
if (subSize[ap] > subSize[bp]) {
newparent = ap;
oldparent = bp;
} else {
newparent = bp;
oldparent = ap;
}
subSize[newparent] += subSize[oldparent];
for (int i = 0; i < parent.size(); i++) {
if (parent[i] == oldparent) {
parent[i] = newparent;
}
}
}

bool isConnect(int a, int b) {
int op = findp(a);
int gp = findp(b);
return a == b;
}