分治
- 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想
归并&快排
- 三种O(n^2)的排序：冒泡、选择、插入
- 三种不基于比较的排序：桶、基数、计数（桶+前缀和）
归并排序
- 每次把待排序区间一分为二，将两个子区间排序，然后将两个已经排好序的序列合并
#include<bits/stdc++.h>
using namespace std;
#define maxn 5050
#define inf 0x3f3f3f3f
#define mm(a,x) memset(a,x,sizeof(a))
#define ll long long
const int N = 1e5+10;
int n;
int a[N],tmp[N];
void merge_sort(int a[],int l,int r){
if(l>=r) return ;
int mid=(l+r)>>1;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(a[i]<a[j]) tmp[k++]=a[i++];
else tmp[k++]=a[j++];
}
while (i <= mid) tmp[k ++ ] = a[i ++ ];
while (j <= r) tmp[k ++ ] = a[j ++ ];
for(int i=l,j=0;i<=r;i++,j++) a[i]=tmp[j];
}
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
merge_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);
return 0;
}
快速排序
- 选择一个基准，将小于基准的放在基准左边，大于基准的放在基准右边，然后对基准左右都继续执行如上操作直到全部有序。
#include<bits/stdc++.h>
using namespace std;
#define maxn 5050
#define inf 0x3f3f3f3f
#define mm(a,x) memset(a,x,sizeof(a))
#define ll long long
const int N = 1e6+10;
int n;
int a[N];
void quick_sort(int a[],int l,int r){
if(l>=r) return ;
int x=a[l+r>>1],i=l-1,j=r+1;
while(i<j){
do i++; while(a[i]<x);
do j--; while(a[j]>x);
if(i<j) swap(a[i],a[j]);
}
quick_sort(a,l,j);
quick_sort(a,j+1,r);
}
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
quick_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);
return 0;
}
STL
- 标准库STL，就是C++自身携带的，国际通用的，没有BUG的，老少皆宜的，令一众算法竞赛选手喜闻乐见的C++的附加产品。
- 主要分两大类：算法类（又称为操作类）和容器类。
算法类
• 最大值最小值（别看简单，C语言自身却没有这个）
• template
• _Tp min(_Tp a, _Tp b)
• _Tp max(_Tp a, _Tp b)
• 快速排序 sort(a, a + 10);
• 数据交换 swap(a, b);
• 求下一个排列 next_permutation(a,a+n)
容器类
• 字符串string
• 不限制长度的数组，vector
• 队列queue，堆栈stack，双端队列deque
• 优先队列（堆）priority_queue
• 简单红黑树（一种较高效率的平衡二叉树）set
• 通过键值来建立的平衡二叉树map
• 允许多个相同值的上述两种结构multiset和multimap
• 位集bitset
点这查看
VECTOR
- VECTOR是一个不限制数组长度的数组！（最简单的理解方式）
VECTOR实现了什么
• 首先是最基础的数据访问功能
operator[], top(), back()
• 其次是简单的数据操作:
删除erase(int index, int size)
插入insert(int index, int size)
添加到数据后面push_back(int value)
弹出最后一个数据pop_back()
• 还有一些自身属性操作：数据大小和重新整理内存单元size(), resize(int size)
• 最后是整体的操作：清空clear(), 是否为空empty()
迭代器Iterator
• 定位：既能像指针一样访问数据，又能保证整体工程的稳定性
• 实际作用：用于访问一个容器内的数据的指针。
• 具体实现了什么？
• 返回第一个元素的迭代器begin()
• 返回容器末尾的迭代器end()（同样遵循左开右闭原则）
Stack 和Queue——栈和队列
• 栈的定义：栈是限定仅在表头进行插入和删除操作的线性表（先进后出）
• 队列的定义：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操
作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入
操作的端称为队尾，进行删除操作的端称为队头。（先进先出）
• stack常用函数：
• push() ——向栈顶压入元素
• pop()——弹出栈顶元素
• top()——访问栈顶元素
• queue常用函数：
• front()——访问队首元素
• back()——访问队尾元素
• push_back()——向队尾插入元素
• pop_front()——弹出队首元素
map
• map内部使用平衡二叉树实现
• 但是我们应用的时候可以把它理解成“自定义下标的数组”，或者是一个数对的集合。
• 而且它实际上是有序的
• map<string,int> mp; • map<string,int>::iterator it; • mp[“张三”]= 90； • mp.insert(pair<string, int>(“李四”,95));
• mp.erase(“张三”);
• mp. clear(); mp.empty();
• mp.find(“张三”);
• mp.begin(); mp.end();