算法常用函数（不包含c++11新特性）

在算法题中，用库函数会减少我们很多代码量，这里来记录平时使用的比较多的方法。至于为什么不包含c++11新特性，是因为我基本不使用c++11，并且蓝桥杯也不允许使用c++11。

（持续更新中） 

stl

map

map自动会根据键进行排序。

插入

插入有两种，如下所示。

两种方法的区别是，第一种方法当插入重复的key值时，并不会覆盖前一次的value,第二种是会覆盖的。 

find()

查找函数，传入key值，如果map中有相应的key，则会返回相应的指针，否则返回end()。

count()

传入key值，如果map中有相应的key，则会返回1，否则返回0。

删除

erase(key)

遍历

    map<char,char> a;
	a.insert(pair<char,char>('a','b'));
	a['b'] = 'c';
	a['c'] = 'd';
	map<char,char>::iterator it = a.begin();
	for(;it!=a.end();it++){
		cout<<it->second<<" ";
	}

vector

vector直接可以比大小，比较规则和string类似。

push_back()

插入元素。

pop_back()

删除最后一个元素。

back()

返回最后一个元素。

构造方法

(length,0)    (length)

删除

ve.erase(ve.begin()+index)

set

set会自动排序，按从小到大进行排序。下面看一个排序的典型例子：

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
int n,m;
map<vector<int>,int> ma;
set<pair<int,vector<int> > > se;

int main(){
	int i,j;
	cin>>n>>m;
	for(i=0;i<n;i++){
		vector<int> ve(m);
		for(j=0;j<m;j++){
			cin>>ve[j];
		}
		ma[ve]++;
	}
	map<vector<int>,int>::iterator it = ma.begin();
	for(;it!=ma.end();it++){
		pair<int,vector<int> > pa;
		pa.first = -1*(it->second);
		pa.second = it->first;
		se.insert(pa);
	}
	int size = se.size();
	cout<<size<<endl;
	set<pair<int,vector<int> > >::iterator iter = se.begin();
	for(;iter!=se.end();iter++){
		cout<<-(*iter).first;
		for(i=0;i<m;i++){
			cout<<" "<<(*iter).second[i];
		}
		cout<<endl;
	} 
	return 0;
} 

set的元素为pair<int,vector<int> >，insert进去元素的时候要先定义要插进去的pair，并给pair的first和second赋值。set进行排序的时候，会首先按照pair的first进行排序，当first相同时，再按照second进行排序。

count()

参数为元素值，如果存在，返回1，否则返回0。

erase()

参数为元素值，删除不存在的元素不会报错。

queue

push()

插入

front()

返回队头元素

back()

返回队尾元素

字符串

判断字符是不是字母数字字符（大小写字母和数字）

isalnum(ch)

头文件：<cctype>

大小写字母转换

转小写：tolower(ch)

转大写：toupper(ch)

头文件：<cctype> 

字符串截取

s.substr(开始下表，截取的字符个数）

排序

函数：sort(a.begin(),a.end())

头文件：<algorithm>

数字

int最值

最大值：INT_MAX

最小值：INT_MIN

头文件：<climits>

转成字符串

如代码所示：

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main(){
	stringstream s;
	string ss;
	s<<-1;
	ss = s.str();
	cout<<ss;
	return 0;
} 

 s.str("")：清空s

字符串转成数字

如代码所示：

#include <iostream>
#include <sstream> 
using namespace std;

int main(){
    istringstream s("1234");//或者赋值：s.str("1234")
    int a;
    s>>a;
    cout<<a;
    return 0;
}

数组

清零

函数：memset(0,sizeof(数组名))

头文件：<cstring>

示例：

    int rows[9][9];
    int columns[9][9];
    int subboxes[3][3][9];
        
    memset(rows,0,sizeof(rows));
    memset(columns,0,sizeof(columns));
    memset(subboxes,0,sizeof(subboxes));

交换元素 

函数：swap(a[i],a[b])

头文件：<algorithm>

sort()函数常用方法

普通数组排序

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int a[5]={5,23,7,1,4};
    sort(a,a+5);
    for(int i=0;i<5;i++){
    	cout<<a[i]<<" ";
	}
    return 0;
}

自定义排序

以结构体为例：

#include <iostream>
#include <algorithm>
using namespace std;
struct demo{
	string name;
	int score;
}a[5];

bool cmp(demo& a,demo& b){
	//升序用"<"号(a在前，b在后) 
	return a.score < b.score;
}

int main(){
    a[0].name = "aaa",a[0].score = 34;
    a[1].name = "bbb",a[1].score = 14;
    a[2].name = "ccc",a[2].score = 57;
    a[3].name = "ddd",a[3].score = 23;
    a[4].name = "eee",a[4].score = 68;
    //按照成绩升序排序 
    sort(a,a+5,cmp);
    for(int i=0;i<5;i++){
    	cout<<a[i].name<<":"<<a[i].score<<endl;
	}
    return 0;
}

二叉树

下标

记根节点下标为index。

根节点下边从0开始：左子树下标为2*index+1，右子树下标为2*index+2。

根节点下边从1开始：左子树下标为2*index，右子树下标为2*index+1。

遍历

已知前序和中序求后序

直接看代码吧，代码中有注释。

输入：第一个整数n为二叉树中节点的个数，随后两行，每行n个整数，第一行为前序遍历，第二行为中序遍历。

输出：后序遍历。

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> qx,zx,hx;//分别代表前序 中序 后序 

//root为前序中根节点的下标，start end分别是在中序中树开始和结束的下标 
void buildTree(int root,int start,int end){
	if(start > end){
		return;
	}
	int i = start;
	while(i<=end && qx[root]!=zx[i]){//找到根节点在中序中的下标 
		i++;
	}
	//递归遍历左右子树 
	buildTree(root+1,start,i-1);//在前序中，根节点后的第一个节点为左子树根节点 
	buildTree(root+i-start+1,i+1,end);//整个左子树的长度为i-start 
	hx.push_back(qx[root]);
}

int main(){
	int i;
	cin>>n;
	qx.resize(n);
	zx.resize(n);
	for(i=0;i<n;i++){
		cin>>qx[i];
	}
	for(i=0;i<n;i++){
		cin>>zx[i];
	}
	buildTree(0,0,n-1); //构建二叉树 
	cout<<hx[0];
	for(i=1;i<n;i++){
		cout<<" "<<hx[i];
	}
	return 0;
} 

已知后序和中序求前序也是一样的思路。 

层次遍历

以天梯的一道题为例：

#include <iostream>
#include <map>
using namespace std;
int hx[35],zx[35];
map<int,int> cx;

//root为后序中根节点的下标，start和end分别是中序中树开始和结束的下标，
//index是根节点在层序遍历中的下标（按照完全二叉树来计算的下标） 
void buildTree(int root,int start,int end,int index){
	if(start > end){
		return;
	}
	int i = start;
	while(i<=end && hx[root]!=zx[i]){//找根节点在中序中的下标 
		i++;
	}
	cx[index] = hx[root];//记录根节点 
	//右子树的长度为end-i，则左子树在后序中根节点的下标为root-(end-i)-1 
	buildTree(root-(end-i)-1,start,i-1,2*index);//遍历左子树 
	buildTree(root-1,i+1,end,2*index+1);//遍历右子树 
}

int main(){
	int n,i;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>hx[i];
	}
	for(i=0;i<n;i++){
		cin>>zx[i];
	}
	buildTree(n-1,0,n-1,1);//建树，根节点的下标为1 
	//map会按照键值自动排序，依次输出就好 
	map<int,int>::iterator it = cx.begin();
	cout<<it->second;
	it++;
	while(it!=cx.end()){
		cout<<" "<<it->second;
		it++;
	}
	return 0;
}