总结:
一.目前学习的算法和思想:
1.基础算法:
排序:
二分:
前缀和和差分:
双指针:
位运算:
区间合并:
离散化:
2.数据结构:
单双链表
栈和队列
单调栈和单调队列
并查集
数和图
3.搜索:
bfs和dfs
4.图论:
图的遍历:bfs和dfs
图的拓扑排序
图的最小生成树:kruskal算法,prime算法
图上两点的最短路径: 单源最短路径dijkstra 所有点对:floyd 两点之间的最短路径:bfs搜索
5.其他算法思想
暴力
DP
贪心
6.其他:
基本语法和c++STL使用
STL复习
#include<vector>
//vector 动态可变长数组 学习
//声明
vector<int> a;
vector<int> b[150];//创建了包含150元素的数组,每个元素是一个vector容器,相当于矩阵
struct zbg
{
int x, y;
};
vector<zbg> c;//结构体vector
//插入和删除
a.push_back(5);//尾插
a.pop_back();//尾删
//元素的提取
a.front();//首元素
a.back();//尾元素
//元素大小和判空
a.size();
a.empty();
//迭代器
vector<int>::iterator first = a.begin(), last = a.end();
//获得a的首尾迭代器
a.clear();//清空a的所有元素
#include<stack>
//栈 stack
stack<int> sta;
//基本
sta.size(); sta.empty();
//插入删除
sta.push(1);//入栈
sta.pop();//出栈
sta.top();//栈顶元素引用
#include<queue>
//queue和priority_queue 队列 学习
//声明
queue<int> q;
//插入和删除
q.push(2);//入队咧
q.pop();//出队列
//元素提取
q.front(); q.back();
//基本
q.empty(); q.size();
//优先级队列学习 priority_queue 二叉堆 默认为大根堆
//声明
priority_queue<int> z;
priority_queue<zbg> z1;//结构体要重载小于运算符
struct zbg
{
int x, y;
bool operator <(const zbg &a)const
{
return this.x<a.x;
}
};
priority_queue<pair<int, string>> z2;//二元组优先级队列
//插入和删除
z.push(5);//堆插入
z.pop();//只能删除堆顶
//元素提取
z.top();
z.size(); z.empty();//基本函数
//大根堆转换成小根堆
//1.正整数和正小数转换为负数存储(不推荐)
//2.创建结构体,对小于运算符重载
struct Int {
int x;
Int(const int& a) : x(a) {}
bool operator<(const Int& a)
{
return x > a.x;
}
};
priority_queue<Int> z0;//int类型的小根堆
//pair 二元组 学习
pair<string, int> min;//带默认值的初始化
pair<string, int> max("zbg", 1);//赋初始值
min = make_pair("zbg", 1);//调用函数初始化,make_pair生成一个pair临时对象
min.first; min.second;//元素获取,数据成员,不是函数
//比较运算符
min == max;//当且仅当两个分别相等
min < max;//小于运算 只比较第一个
#include<deque>
//双端队列学习 deque 两端都有口
deque<int> j;
//插入和删除
j.push_back(1);//尾插
j.pop_back();//尾删
j.push_front(3);//头插
j.pop_front();//头删
//特殊功能
j[0];//下标运算符类似数组
//基本
j.size(); j.empty(); j.clear();
//迭代器
typename deque<int>::iterator deque_first = j.begin(), deque_last = j.end();
#include<set>
//有序非重复集合 set 和有序重复集合 multiset 底层实现为红黑树,会自动排序
//声明
set<int> s; multiset<int> ms;
//自定义结构体时候要重载小于运算符
//基本
s.size(); s.empty(); s.clear();
ms.size(); ms.empty(); ms.clear();
//中序迭代器 只提供了前++ 和前--的操作(双向访问迭代器,只能左右不能随机)
typename set<int>::iterator set_first = s.begin(), set_last = s.end();
--set_first; ++set_first;
//插入和删除
s.insert(1); s.erase(s.begin());
ms.insert(1); ms.erase(s.begin());
s.erase(s.begin());//删除,元素和迭代器都可以,元素会删除全部,迭代器只是一个
//其他特殊函数
s.find(2);//查找函数,返回迭代器
s.lower_bound(2);//查找>=2的最小的一个,返回迭代器
s.upper_bound(2);//查找>2的最小的一个,返回迭代器
s.count(2);//返回s中元素2的个数
#include<map>
//映射<key,value>的二元映射 map和multimap 前者不允许重复,后者可以 底层是红黑树
//声明,常用做(伪)哈希表
map<int, int> ma;//自定义结构体要重载小于运算符
//基本
ma.size(); ma.empty(); ma.clear();
ma.begin(); ma.end();//双向迭代器,begin,end仍是前闭后开的范围
//迭代器 返回值是二元组pair
typename map<int, int>::iterator map_first = ma.begin();
//插入和删除
pair<int, int> mac(5, 1);
ma.insert(mac); ma.insert(make_pair(5, 2));//插入参数为pair二元组
ma.erase(ma.begin());
//其他操作
ma.find(5);//返回迭代器
//索引运算符重载
ma[5] = 3;//对关键码5进行改写,没有就创建
//也可以直接查找
#include<unordered_map>
//哈希表 unordered_map 底层是哈希表实现
//声明
unordered_map<string, int> hash;
//基本跟map差不多
hash.insert(make_pair("zbg", 1));
hash.insert(pair<string, int>("npc", 1));//隐式转换
hash.insert(unordered_map<string, int>::value_type("npc", 1));//非隐式转换
hash.erase(hash.end());
#include<algorithm>
//STL算法学习
//algorithm容器算法内容,以vector为例
vector<int> wj;
reverse(wj.begin(), wj.end());//容器翻转
unique(wj.begin(), wj.end());//去重,返回尾指针
//运用,求个数
int n = wj.end() - unique(wj.begin(), wj.end());
random_shuffle(wj.begin(), wj.end());//随机打乱,用法跟reverse相同
next_permutation(wj.begin(), wj.end());//求字典序下一个排列,并且直接在原容器上更新,不存在就返回false
sort(wj.begin(), wj.end());//排序函数
//排序结构体时需要重载小于运算符或者自定义比较函数
bool cmp(int a, int b)
{
return a < b;
}
sort(wj.begin(), wj.end(), cmp);
//下面两个函数都返回元素位置迭代器
lower_bound(wj.begin(), wj.end(), 5);//二分查找第一个大于等于5的元素
upper_bound(wj.begin(), wj.end(), 5);//二分查找第一个大于5的元素