怎么建设一个自己的电商网站,想要网站导航推广页,wordpress 获取当前分类名称,哪个软件做网站好数据结构算法刷题笔记——题型解法 一、常用容器1.1 vector1.1.1 vector基本操作1.1.1.0 头文件#includevector1.1.1.1 构造一个vector容器1.1.1.2 元素访问1.1.1.3 元素个数 .size()1.1.1.4 最大容量 .capacity()1.1.1.5 改变容器有效元素个数 .resize(n)1.1.1.6 改变… 数据结构算法刷题笔记——题型解法 一、常用容器1.1 vector1.1.1 vector基本操作1.1.1.0 头文件#includevector1.1.1.1 构造一个vector容器1.1.1.2 元素访问1.1.1.3 元素个数 .size()1.1.1.4 最大容量 .capacity()1.1.1.5 改变容器有效元素个数 .resize(n)1.1.1.6 改变容器的最大容量 .reserve(n)1.1.1.7 判断是否为空 .empty()1.1.1.8 清空容器 clear()1.1.1.9 迭代器 .begin()、.end()、.rbegin()、rend()1.1.1.10 插入元素 push_back()1.1.1.11 删除最后一个值 pop_back()1.1.1.12 返回最后一个元素 back()1.1.1.13 返回第一个元素 front()1.1.1.14 插入一个元素 insert()1.1.1.15 删除一个元素 erase()1.1.1.16 查找元素值 find()1.1.1.17 交换两个容器的值 swap()1.1.1.18 迭代器失效 1.1.2 vector算法1.1.2.1 头文件1.1.2.2 元素翻转reverse()1.1.2.3 排序 sort() 1.2 list1.2.1 list基本操作1.2.1.0 list头文件1.2.1.1 list定义与声明1.2.1.2 基本操作 1.3 queue1.3.1 queue基本操作1.3.1.0 queue头文件1.3.1.1 queue定义与声明1.2.1.2 基本操作 1.3.2 双端队列deque1.3.1.0 queue头文件1.3.1.1 queue定义与声明1.2.1.2 基本操作 1.3.3 优先队列 priority_queue1.3.3.0 queue头文件1.3.3.1 queue定义与声明1.3.3.2 基本操作 1.4 stack1.4.1 stack基本操作1.4.1.0 stack头文件1.4.1.1 stack定义与声明1.4.1.2 基本操作 1.5 map1.5.1 map基本操作1.5.1.0 map头文件1.5.1.1 map定义与声明1.5.1.2 基本操作 1.6 unordered_map1.6.0 map和unordered_map区别1.6.1 unordered_map基本操作1.6.1.0 unordered_map头文件1.6.1.1 unordered_map定义与声明16.1.2 基本操作 1.7 set1.7.1 set基本操作1.7.1.0 set头文件1.7.1.1 set定义与声明1.7.1.2 基本操作 1.8 unordered_set1.7.1 unordered_set基本操作1.7.1.0 unordered_set头文件1.7.1.1 unordered_set定义与声明1.7.1.2 基本操作 三、常用函数库3.1 优先级队列3.2 链表结构体3.3 链表的插入删除操作3.2 二叉树结构体 1、贪心算法2 动态规划 一、常用容器
1.1 vector
1.1.1 vector基本操作
1.1.1.0 头文件#include
#includevector1.1.1.1 构造一个vector容器
1、vectorint v1;//构造一个int类型的空容器
2、vectorint v2(10,1);//构造一个int类型的容器并初始化了10个1
3、vectorint v3(v2);//将容器v2拷贝给v3
4、vectorint v4(v2.begin(),v2.end());//迭代器拷贝构造
5、string s (hello);//使用别的容器的迭代器也可以拷贝不一定是vector可以是stringvectorchar s1(s.begin(), s.end());1.1.1.2 元素访问
//1.迭代器遍历
//2.范围for遍历其实就是迭代器
//3.下标遍历
//4.array.at(i) //使用at(),当这个函数越界时会抛出一个异常//at()得到编号位置的数据
vectorint::iterator it;
for(itarray.begin();it!array.end();it)cout*itendl;for(int i0;inSize;i)
{ coutvecClass.at(i) ;
} for(auto x:v)
{coutx ;
}for (int i 1; i 6; i){v.push_back(i);}1.1.1.3 元素个数 .size()
v1.size();1.1.1.4 最大容量 .capacity()
v1.capacity();1.1.1.5 改变容器有效元素个数 .resize(n)
1.假设所给值小于当前容器size则size缩小至所给值
2.假设所给值大于当前容器size值并且小于capacitysize扩大至所给值增加的数用0去补充
3.假设所给值大于当前容器size值并且大于capacity值先扩容之后再重复规则2
v.resize(n); // 将v的大小改为n新元素的值为该type的默认值
v.resize(n, value); // 将v的大小改为n并将新元素的值设为value1.1.1.6 改变容器的最大容量 .reserve(n)
1.假设所给值小于当前容量值什么都不会发生改变
2.假如所给值大于当前容容量值扩容至所给值
v.reserve(n);1.1.1.7 判断是否为空 .empty()
v1.empty();//1为空0为非空1.1.1.8 清空容器 clear()
v1.clear();1.1.1.9 迭代器 .begin()、.end()、.rbegin()、rend()
//通过begin我们可以得到容器中的第一个元素的正向迭代器
//通过end我们可以得到容器中的最后一个元素的正向迭代器
vectorintv(5,1);
vectorint::iterator itv.begin();
while(it!v.end())
{cout*it ;it;
}//通过rbegin我们可以得到容器的最后一个元素的反向迭代器
//通过rend我们可以得到容器的第一个元素的反向迭代器
vectorint v(5,3);
vectorint::reverse_iterator itv.rbegin();
while(it!v.rend())
{cout*it ;it;
}1.1.1.10 插入元素 push_back()
v.push_back(1);1.1.1.11 删除最后一个值 pop_back()
v.pop_back();1.1.1.12 返回最后一个元素 back()
v1.back();1.1.1.13 返回第一个元素 front()
v1.front();1.1.1.14 插入一个元素 insert()
//1.选择一个位置迭代器在其前面选择一个我们要插入的元素
v.insert(v.begin(),10);//再开头插入一个元素10
//2.选择一个位置迭代器选择我们一个要插入的元素的数量并且选择一个要插入的元素
v.insert(v.begin(),5,10);//我们头插5个101.1.1.15 删除一个元素 erase()
//1.删除指定位置的内容迭代器(删除掉迭代器处的内容)
v.erase(v.begin());
//2.删除指定位置的内容迭代器删除区间的末尾左闭右开
v.erase(v.begin(),v.begin()2);//删除0、1处的内容1.1.1.16 查找元素值 find()
//find函数可以找到容器中我们要寻找的值并且返回迭代器
//find函数有三个参数迭代器左区间迭代器右区间要查找元素[左闭右开]
vectorint::iterator posfind(v.begin(),v.end(),3);//找到31.1.1.17 交换两个容器的值 swap()
//通过sawp我们可以交换两个容器的值
v1.swap(v);1.1.1.18 迭代器失效
//在使用迭代器之前对整个容器进行了增删改操作,这就是引起迭代器失效的原因
//解决的方法也很简单就是使用迭代器之前重新赋值一下就行。vectorint::iterator it find(v.begin(), v.end(), 2);v.erase(v.begin());//删除头元素it find(v.begin(), v.end(), 2);//it迭代器失效重新获取一下v.erase(it);//删除元素2vectorint::iterator it2 v.begin();//begin()迭代器失效重新获取一下while (it2 ! v.end()){cout *it2 ;it2;}1.1.2 vector算法
1.1.2.1 头文件
#includealgorithm1.1.2.2 元素翻转reverse()
reverse(array.begin(),array.end()); //将元素翻转即逆序排列1.1.2.3 排序 sort()
// 默认升序
sort(array.begin(),array.end());
//降序则调用:
sort(array.begin(),array.end(),[](int a, int b) {return a b});1.2 list
1.2.1 list基本操作
1.2.1.0 list头文件
底层实现是双向链表
#include list1.2.1.1 list定义与声明 listint l 声明一个空链表listint l{1,2,3} 声明一个含指定元素的链表listint l(n) 声明一个含n个元素的链表并全部初始化为0listint l(n, m) 声明一个含n个元素的链表并全部初始化为mlistint l(a,b) 声明一个链表并初始化为区间[a,b]中的元素a、b是迭代器1.2.1.2 基本操作
增1、l.insert() 插入一个元素到list中auto pos L.begin();// 在pos前插入值为4的元素L.insert(pos, 4);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);// 在pos前插入[v.begin(), v.end)区间中的元素L.insert(pos, v.begin(), v.end());2、l.push_back() 在list的末尾添加一个元素 l.push_back(i);3、l.push_front() 在list的头部添加一个元素L.push_front(i);删1、l.clear() 清空list的所有元素// 将l2中的元素清空l2.clear();2、l.erase() 删除一个元素// 删除pos位置上的元素L.erase(pos);// 删除list中[begin, end)区间中的元素即删除list中的所有元素L.erase(L.begin(), L.end());3、l.erase(l.begin(),l.end()) 将l从begin()到end()之间的元素删除。4、l.pop_back() 删除最后一个元素 5、l.pop_front() 删除第一个元素6、l.remove() 从list删除指定元素 l.remove(x);//删除与x相等的元素7、l.remove_if() 按指定条件删除元素l.remove_if(func); //func是函数名容器元素依次传进去删除返回true的元素bool func(const string value){if(value last)return true;return false;}8、l.unique() 删除list中重复的元素改1、l.resize() 改变list的大小l.resize(2);l.resize(10, b);2、l.reverse() 把list的元素倒转查1、l.front() 返回第一个元素 2、l.back() 返回最后一个元素3、l.empty() 若list是空的则返回true否则返回false4、l.max_size() 返回list能容纳的最大元素数量 5、l.size() 返回list中的元素个数其他操作1、l.assign() 给list赋值l.assign(5,100); //将100赋值给前5个元素l2.assign(l1.begin(), l1.end()); //将l1的元素赋值给l2int arr []{10, 20, 30, 40};list3.assign(arr, arr4);2、l.get_allocator() 返回list的配置器3、l.merge() 合并两个listlist1.merge(list2)//将l2中的元素合并到l1中并且l1和l2必须已经排号顺序将一个有序list容器加入另一个有序list容器中且两个list容器必须都为逆序或顺序这是很容易不注意导致报错的主要原因。4、l.sort() 给list排序l.sort(); //默认升序排列l.sort([](int a, int b) {//降序排列return a b;});5、l.splice() 合并两个listlist1.splice(it1, list2)//将list2中的所有元素拷贝到list1中。在list1中的起始位置是it1.复制结束后list2将为空。list1.splice(it1, list2, it2)//将list2中的元素从it2开始剪切到list1的it1起始的地方list1.splice(it1, list2, it2begin, it2end)6、l.swap() 交换两个list// 交换l1和l2中的元素l1.swap(l2);
迭代器:1、begin()/end()返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器listint::iterator it l.begin()2、rbegin()/rend()返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的 reverse_iterator,即begin位置 listint::reverse_iterator it l.rbegin()3、l.begin() 返回指向第一个元素的迭代器 4、l.end() 返回末尾的迭代器5、l.rbegin() 返回指向第一个元素的逆向迭代器 6、l.rend() 指向list末尾的逆向迭代器1.3 queue
std::queue 容器是一种先进先出(First In First Out, FIFO)的数据结构且有两个出口。
1.3.1 queue基本操作
1.3.1.0 queue头文件
#include queue1.3.1.1 queue定义与声明
1、queueintq1; //默认初始化一个空的整数队列
2、queueintq2 {1 2 3 4 5};//使用初始化列表初始化队列
3、queueintq3(q1)//使用q1来初始化q3
4、queuestd::vectorint q; // 初始化一个存储vector的队列 q.emplace(1, 2, 3); // 直接在队列中构造一个vectorint{1, 2, 3}
5、queueint q; // 默认初始化一个空的整数队列 q.push(1); // 添加元素1到队列尾部
6、queueint q2(move(q1)); // 使用q1来移动初始化q2现在q1是空的q2是{1, 2, 3} 1.2.1.2 基本操作
1、push() //在队尾插入一个元素queue string q;q.push(first);
2、pop() //删除队列第一个元素q.pop();
3、size() //返回队列中元素个数
4、empty() //如果队列空则返回true
5、ftont() //返回队列中的第一个元素
6、back() //返回队列中最后一个元素
7、swap() //将当前queue中的元素与参数queue中的元素交换q2.swap(q1);
8、emplace()用传给 emplace() 的参数调用 T 的构造函数在 queue 的尾部生成对象。myqueue5.emplace(45);
9、运算符 ! // []当两个队列front()内容一致返回true// [!]当两个队列元素front()不相等返回true// []左边队列的front()的元素大于右边队列pop的元素则返回true.
10、迭代器没有意义只允许队首出队、队尾入队1.3.2 双端队列deque
deque全称为double-ended queue双端队列它是一种数据结构允许在队列的两端进行插入和删除操作。deque的特点是可以在队列的两端进行元素的操作并且可以高效地在队列的任意位置进行元素的插入和删除操作。deque几乎涵盖了queue队列、stack堆栈、vector向量 等的全部用法功能非常的强大。 deque 通常实现为一组独立区块第一区块朝某方向扩展最末区块朝另一方向扩展
1.3.1.0 queue头文件
#include deque1.3.1.1 queue定义与声明
//deque的定义
dequeintd1; //定义一个储存数据类型为int的双端队列d1
dequedoubled2; //定义一个储存数据类型为double的双端队列d2
dequestringd3; //定义一个储存数据类型为string的双端队列d3
deque结构体类型d4; //定义一个储存数据类型为结构体类型的双端队列d4
dequeint d5[N]; //定义一个储存数据类型为int的双端队列数组d5
dequedoubled6[N]; //定义一个储存数据类型为double的双端队列数组d6 1.2.1.2 基本操作
1、push_back()//在队列的尾部插入元素。
2、emplace_back()//与push_back()的作用一样
3、push_front()//在队列的头部插入元素。
4、emplace_front()//与push_front()的作用一样
5、pop_back()//删除队列尾部的元素。
6、pop_front()//删除队列头部的元素。
7、back()//返回队列尾部元素的引用。
8、front()//返回队列头部元素的引用。
9、clear()//清空队列中的所有元素。
10、empty()//判断队列是否为空。
11、size()//返回队列中元素的个数。
12、resize()//重置元素数量d.resize(num) //将元素数量改为 num如果 size() 变大多出来的新元素都需以 default 构造函数完成初始化)d.resize(num, elem) //将元素数量改为 num如果 size() 变大多出来的新元素都是 elem 的拷贝)
12、begin()//返回头位置的迭代器
13、end()//返回尾1位置的迭代器
14、rbegin()//返回逆头位置的迭代器
15、rend()//返回逆尾-1位置的迭代器
16、insert()//在指定位置插入元素 //或返回 pos———如果没有新元素的话始自C11)d.insert(pos, n, elem)//在iterator 位置 pos 之前方插入 n 个 elem 拷贝并返回第一个新元素的位置d.insert(pos, beg, end) 在 iterator 位置 pos 之前方插入区间 [beg, end) 内所有元素的一份拷贝并返回第一个新元素的位置d.insert(pos, initlist) 在 iterator 位置 pos 之前方插入初值列 initlist 内所有元素的一份拷贝并返回第一个新元素的位置
17、erase()//在指定位置删除元素 d.erase(pos) 移除 iterator 位置 pos 上的元素返回下一元素的位置d.erase(beg, end) 移除 [beg, end) 区间内的所有元素返回下一元素的位置
18、通过迭代器iterator遍历for(itd.begin();it!d.end();it){cout*it ;}
19、通过下标遍历for(int i0;id.size();i){coutd[i] ;}
20、通过foreach遍历for(int it:d){coutit ;}
21、运算符c1 c2 返回 c1 是否等于 c2对每个元素调用)c1 ! c2 返回 c1 是否不等于 c2相当于!(c1c2))c1 c2 返回 c1 是否小于 c2c1 c2 返回 c1 是否大于 c2相当于c2c1)c1 c2 返回 c1 是否小于等于 c2相当于!(c2c1))c1 c2 返回 c1 是否大于等于 c2相当于! (c1c2))
22、 d1.swap(d2) 置换 d1 和 d2 的数据 swap(c1, c2) 置换 c1 和 c2 的数据1.3.3 优先队列 priority_queue
优先队列是一种容器适配器采用了堆这样的数据结构保证了第一个元素总是整个优先队列中最大的(或最小的)元素。优先队列默认使用vector作为底层存储数据的容器在vector上使用了堆算法将vector中的元素构造成堆的结构所以其实我们就可以把它当作堆凡是需要用堆的位置都可以考虑优先队列。(所以需要先学习堆)默认为大堆不允许随机访问只能访问队列首部元素也只能对首部元素进行出队
1.3.3.0 queue头文件
#include queue1.3.3.1 queue定义与声明
priority_queueint q;//储存int型数据
priority_queuedouble q;//储存double型数据
priority_queuestring q;//储存string型数据
priority_queue结构体名 q;//储存结构体或者类 1.3.3.2 基本操作
empty() 如果优先队列为空则返回真
pop() 删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素的个数
top() 返回优先队列中有最高优先级的元素
快速切换大小顶堆定义
less储存的数据类型 即使用大顶堆
greater储存的数据类型 即是用小顶堆
priority_queue储存的类型,vector储存的类型,顶堆的类型 容器名//使用大顶堆
priority_queueint,vectorint,lessint q;//储存int型数据
priority_queuedouble,vectordouble,lessdouble q;//储存double型数据
priority_queuestring,vectorstring,lessstring q;//储存string型数据
priority_queue结构体名,vector结构体名,less结构体名 q;//储存结构体或者类 //使用小顶堆
priority_queueint,vectorint,greaterint q;//储存int型数据
priority_queuedouble,vectordouble,greaterdouble q;//储存double型数据
priority_queuestring,vectorstring,greaterstring q;//储存string型数据
priority_queue结构体名,vector结构体名,greater结构体名 q;//储存结构体或者类 使用结构体重载运算符定义
新建一个结构体通过重载运算符改变顶堆的排序这里是拓展用法也是必学用法因为自己写的结构体是没有比较大小功能的当然也可以在原本的结构体里面重载运算符
struct test{//定义一个结构体test int val;test(int v){//构造函数 this-valv;}bool operator (const test t)const{//重载运算符 return valt.val;}bool operator (const test t)const{//重载运算符return valt.val;}
};自定义结构体重载括号运算符 很多时候我们不应该重载结构体的运算符。像数据结构vector它有它的基本运算方法我们不应该重载它的运算符。 此时我们就应该自定义结构体替代less和greater,通过重载括号符就可以更改比较规则
struct cmp{bool operator () (const test t1,const test t2)const{//重载括号运算符return t1.valt2.val;//小于号是大根堆大于号是小根堆 }
};
priority_queuetest,vectortest,cmp q;//自定义一个优先级队列q 1.4 stack
stack 是一种 先进后出First In Last Out,FILO的数据结构它只有一个出口栈中只有顶端的元素才可以被外界使用因此栈不允许有遍历行为 遍历非质变算法在运算期间不改变容器中的元素栈中进入数据称为 — 入栈 push栈中弹出数据称为 — 出栈 pop - 生活中的栈 子弹夹先装进弹夹的子弹最后被打出来
1.4.1 stack基本操作
1.4.1.0 stack头文件
底层实现是双向链表
#include stack1.4.1.1 stack定义与声明
// stack 采用模板类实现 stack 对象的默认构造形式
stackT stk;1、stackint myStack;2、std::stackint myStack; // 使用push方法初始化stack myStack.push(1); 3、std::vectorint myVector {1, 2, 3, 4, 5}; std::stackint myStack(myVector.begin(), myVector.end());
//拷贝构造函数
stack(const stack stk); 1.4.1.2 基本操作
1、top()返回一个栈顶元素的引用类型为 T。如果栈为空不能用该函数访问否则报错。
2、push(const T obj)可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
3、push(T obj)以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
4、pop()弹出栈顶元素。
5、size()返回栈中元素的个数。
6、empty()在栈中没有元素的情况下返回 true。
7、emplace()用传入的参数调用构造函数在栈顶生成对象。
8、swap(stackT other_stack)将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。
1.5 map
map是C中STL中的一个关联容器以键值对来存储数据数据类型自己定义。它的内部数据结构是红黑树所有它是有默认排列顺序的每一对中的第一个值称之为关键字(key)每个关键字只能在map中出现一次第二个称之为该关键字的对应值 第一个参数是键的数据类型第二个参数是值的数据类型第三个参数是排序规则不写的话就按照默认的排序规则也就是按照键的升序举例mapint,intmp; 定义了一个叫mp的map类型并且键值都是int类型
1.5.1 map基本操作
1.5.1.0 map头文件
#inlcude map1.5.1.1 map定义与声明
1、mapstring, int myMap;2、mapstring, int myMap { {apple, 1}, {banana, 2}, {cherry, 3}
};
3、insert
mapstring, int myMap;
myMap.insert(make_pair(apple, 1));
myMap.insert(pairstring, int(banana, 2));
myMap.insert({cherry, 3}); // C11及以后版本支持这种写法
4、复制构造函数
mapstring, int anotherMap { {apple, 1}, {banana, 2}
};
mapstring, int myMap(anotherMap); // 通过复制构造函数初始化
5、赋值构造函数
mapstring, int anotherMap { {apple, 1}, {banana, 2}
};
mapstring, int myMap;
myMap anotherMap; // 通过赋值运算符初始化 6、默认升序mapint, intm;
7、改为降序排列
mapint, int, comparem2;//注意这个有谓词的map容器的打印是要单独写的
class compare//一个名叫compare的类
{
public://在public下的作用域在类内类外都可以进行访问bool operator()(int m, int n)const//注意要在后面加const{return m n;//降序排列返回的就两个值中的较大值}
};1.5.1.2 基本操作
###############插入操作insert###################
1、使用[ ]进行单个插入
mapint, string ID_Name;
// 如果已经存在键值2015则会作赋值修改操作如果没有则插入
ID_Name[2015] Tom;
2、使用insert进行单个和多个插入
// 插入单个值
mymap.insert(pairchar, int(a, 100));
//返回插入位置以及是否插入成功
pairmapchar, int::iterator, bool ret;
ret mymap.insert(pairchar, int(z, 500));insert函数返回一个pair其中first成员是指向插入元素的迭代器second成员是一个布尔值表示是否成功插入如果键已存在则插入失败second为false。
//指定位置插入
mapchar, int::iterator it mymap.begin();
mymap.insert(it, pairchar, int(b, 300)); //效率更高,插入操作不会改变已存在元素的顺序但你可以指定一个迭代器作为插入位置的提示。这可以提高插入的效率尤其是在插入大量连续元素时。注意这只是一个提示map仍然会保持其排序属性
//范围多值插入
mapchar, int anothermap;
anothermap.insert(mymap.begin(), mymap.find(c));//anothermap将插入mymap中从begin()到find(c)不包括find(c)指向的元素范围内的所有元素。
// 列表形式插入
anothermap.insert({ { d, 100 }, {e, 200} });//使用初始化列表语法来一次性插入多个元素
###############取值操作###################
mapint, string ID_Name;
1、//ID_Name中没有关键字2016使用[]取值会导致插入
//因此下面语句不会报错但打印结果为空
coutID_Name[2016].c_str()endl;
2、//使用at会进行关键字检查因此下面语句会报错
ID_Name.at(2016) Bob;
##############容量操作###################
bool empty();// 查询map是否为空
size_t size();// 查询map中键值对的数量
size_t max_size();// 查询map所能包含的最大键值对数量和系统和应用库有关。// 此外这并不意味着用户一定可以存这么多很可能还没达到就已经开辟内存失败了
size_t count( const Key key ) const; 查询关键字为key的元素的个数在map里结果非0即1##############删除操作操作###################
iterator erase( iterator pos )// 删除迭代器指向位置的键值对并返回一个指向下一元素的迭代器
iterator erase( const_iterator first, const_iterator last );// 删除一定范围内的元素并返回一个指向下一元素的迭代器
size_t erase( const key_type key );// 根据Key来进行删除 返回删除的元素数量在map里结果非0即1
void clear();// 清空map清空后的size为0
##############交换操作###################
void swap( map other );// 就是两个map的内容互换
##############查找操作###################
// 关键字查询找到则返回指向该关键字的迭代器否则返回指向end的迭代器
// 根据map的类型返回的迭代器为 iterator 或者 const_iterator
iterator find (const key_type k);
const_iterator find (const key_type k) const;
##############操作符操作###################
operator: ! 注意 对于运算符, 只有键值对以及顺序完全相等才算成立。##############迭代器操作###################
1、共有八个获取迭代器的函数* begin, end, rbegin,rend* 以及对应的 * cbegin, cend, crbegin,crend*。
2、二者的区别在于后者一定返回 const_iterator而前者则根据map的类型返回iterator 或者 const_iterator。const情况下不允许对值进行修改。如下面代码所示
mapint,int::iterator it;
mapint,int mmap;
const mapint,int const_mmap;it mmap.begin(); //iterator
mmap.cbegin(); //const_iteratorconst_mmap.begin(); //const_iterator
const_mmap.cbegin(); //const_iterator
1.6 unordered_map
unordered_map是一个将key和value关联起来的容器它可以高效的根据单个key值查找对应的value。key值应该是唯一的key和value的数据类型可以不相同。unordered_map存储元素时是没有顺序的只是根据key的哈希值将元素存在指定位置所以根据key查找单个value时非常高效平均可以在常数时间内完成。unordered_map查询单个key的时候效率比map高但是要查询某一范围内的key值时比map效率低。可以使用[]操作符来访问key值对应的value值
1.6.0 map和unordered_map区别
运行效率方面unordered_map最高而map效率较低但 提供了稳定效率和有序的序列。占用内存方面map内存占用略低unordered_map内存占用略高,而且是线性成比例的。map map内部实现了一个红黑树该结构具有自动排序的功能因此map内部的所有元素都是有序的红黑树的每一个节点都代表着map的一个元素因此对于map进行的查找删除添加等一系列的操作都相当于是对红黑树进行这样的操作故红黑树的效率决定了map的效率。unordered_map: unordered_map内部实现了一个哈希表因此其元素的排列顺序是杂乱的无序的
map 优点有序性这是map结构最大的优点其元素的有序性在很多应用中都会简化很多的操作。 红黑树内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现因此效率非常的高。 缺点空间占用率高因为map内部实现了红黑树虽然提高了运行效率但是因为每一个节点都需要额外保存父节点孩子节点以及红/黑性质使得每一个节点都占用大量的空间 适用处对于那些有顺序要求的问题用map会更高效一些。 unordered_map 优点内部实现了哈希表加粗样式因此其查找速度是常量级别的。 缺点哈希表的建立比较耗费时间 适用处对于查找问题unordered_map会更加高效一些因此遇到查找问题常会考虑一下用unordered_map
1.6.1 unordered_map基本操作
1.6.1.0 unordered_map头文件
#inlcude map1.6.1.1 unordered_map定义与声明
unordered_mapint, string umap;16.1.2 基本操作
unordered_map与map的用法基本一直最大的区别在于
map的key是有序的而unordered_map的key为无序
void f2() {mapint, string commap;unordered_mapint, string umap;commap[1]a; commap[3]c; commap[2]b; commap[4]d;umap[1]aa; umap[3]cc; umap[4]dd; umap[2]bb;for(auto node: commap) {coutnode.first: node.secondendl;}for(auto node: umap) {coutnode.first: node.secondendl;}
}
1: a
2: b
3: c
4: d2: bb
4: dd
3: cc
1: aa1.7 set set关联式容器 集合set是一个内部自动有序且不含重复元素的容器默认按升序排列它可以在需要删除重复元素的情况下大放异彩节省时间减少思维量。 set 就是关键字的简单集合当只是想知道一个值是否存在时set 是最有用的。set 内部采用的是一种非常高效的平衡检索二叉树红黑树Red-Black Tree也称为 RB 树RB 树的统计性能要好于一般平衡二叉树。在 set 中每个元素的值都唯一而且系统能根据元素的值自动进行排序set 中元素的值不能直接被改变。 map 中的元素是一些关键字 — 值key–value对关键字起到索引的作用值则表示与索引相关联的数据。在 set 中每个元素只包含一个关键字不存储特定值关联set 支持高效的关键字查询操作 —— 检查一个给定关键字是否在 set 中。 标准库提供 set 关联容器分为 按关键字有序保存元素set关键字即值即只保存关键字的容器、multiset关键字可重复出现的 set无序集合unordered_set用哈希函数组织的 set、unordered_multiset用哈希函数组织的 set关键字可以重复出现。
1.7.1 set基本操作
1.7.1.0 set头文件
#include set1.7.1.1 set定义与声明 1、setint name;setdouble name;setchar name;setstruct node name;setsetint name;setint arr[10];2、setint anotherSet {1, 2, 3}; 3、setint mySet(anotherSet); // 通过复制构造函数初始化 4、std::setint mySet; mySet anotherSet; // 通过赋值运算符初始化 1.7.1.2 基本操作
0、 直接赋值
1、 set 不提供下标运算符operator[]来访问其元素。相反你只能使用迭代器iterator来遍历和访问 std::set 中的元素。
setint::iterator it;//set 只能通过迭代器iterator访问2、find()find(value) 返回 set 中 value 所对应的迭代器即 value 的指针地址如果没找到则返回 end()
3、删除单个元素st.erase(it)其中 it 为所需要删除元素的迭代器。时间复杂度为 O(1)可以结合 find() 函数来使用。st.erase(value)其中 value 为所需要删除元素的值。时间复杂度为 O(logN)N 为 set 内的元素个数。
4、删除一个区间内的所有元素st.erase(iteratorBegin, iteratorEnd)其中 iteratorBegin 为所需要删除区间的起始迭代器 iteratorEnd 为所需要删除区间的结束迭代器的下一个地址即取 [iteratorBegin, iteratorEnd)
5、equal_range()返回一对迭代器分别表示第一个大于或等于给定关键值的元素和第一个大于给定关键值的元素。这个返回值是一个 pair 类型第一个是键的 lower_bound第二个是键的 upper_bound。如果这一对定位器中哪个返回失败则返回 end() pr s.equal_range(3);cout 第一个大于等于3的数是 *pr.first endl;cout 第一个大于3的数是 *pr.second endl;begin(); // 返回指向第一个元素的迭代器end(); // 返回指向最后一个元素的后一个位置的迭代器clear(); // 清除所有元素count(); // 返回某个值元素的个数用于判断set中是否有该元素size(); // 返回集合中元素的数目empty(); // 如果集合为空返回true否则返回falseequal_range(); // 返回集合中与给定值相等的上下限的两个迭代器insert(); // 在集合中插入元素 setint s;//定义 s.insert(1);//插入元素1erase(); // 删除集合中的元素find(); // 返回一个指向被查找到元素的迭代器get_allocator(); // 返回集合的分配器upper_bound(); // 返回大于某个值元素的迭代器lower_bound(); // 返回指向大于或等于某值的第一个元素的迭代器key_comp(); // 返回一个用于元素键值比较的函数value_comp(); // 返回一个用于比较元素间的值的函数max_size(); // 返回集合能容纳的元素的最大限值rbegin(); // 返回set反转后的开始指针(即原来的end-1)rend(); // 返回set反转后的结束指针(即原来的begin-1)swap(); // 交换两个集合变量1.8 unordered_set
unordered_set 容器可直译为“无序 set 容器”即 unordered_set 容器和 set 容器很像唯一的区别就在于 set 容器会自行对存储的数据进行排序而 unordered_set 容器不会 不再以键值对的形式存储数据而是直接存储数据的值容器内部存储的各个元素的值都互不相等且不能被修改。不会对内部存储的数据进行排序这和该容器底层采用哈希表结构存储数据有关
1.7.1 unordered_set基本操作
1.7.1.0 unordered_set头文件
#include unordered_set1.7.1.1 unordered_set定义与声明 1、unordered_setint name;unordered_setdouble name;unordered_setchar name;unordered_setstruct node name;unordered_setunordered_setint name;unordered_setint arr[10];2、unordered_setint anotherSet {1, 2, 3}; 3、unordered_setint mySet(anotherSet); // 通过复制构造函数初始化 4、unordered_setint mySet; mySet anotherSet; // 通过赋值运算符初始化 5、myUnorderedSet.insert(1); 1.7.1.2 基本操作
基本操作与set相同三、常用函数库
3.1 优先级队列
priority_queueTYPE q;用来选取最小元素 q.push()q.top()q.pop() 对载入数据进行自动排序最小的排在顶部
3.2 链表结构体
//Definition for singly-linked list.
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};3.3 链表的插入删除操作
3.2 二叉树结构体 //Definition for a binary tree node.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) {}};1、贪心算法
1、数组重排 2、按照题目总结规律局部最优从头按规则搜索得出最优解
2 动态规划
动态规划问题的一般形式就是求最值求解动态规划的核心问题是穷举重叠子问题、最优子结构、状态转移方程就是动态规划三要素
1、 明确 base case 2、明确「状态」 3、明确「选择」 4、 定义 dp 数组/函数的含义
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):for 选择 in 所有可能的选择:# 此时的状态已经因为做了选择而改变result 求最值(result, dp(状态1, 状态2, ...))return result# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] base case
# 进行状态转移
for 状态1 in 状态1的所有取值for 状态2 in 状态2的所有取值for ...dp[状态1][状态2][...] 求最值(选择1选择2...)
