[关闭]
@thousfeet 2020-01-11T08:17:37.000000Z 字数 12923 阅读 849

模板整理

LeetCode

C++文件读写

(include < fstream > )

  1.     ifstream ifile;
  2.     ifile.open("xx.in");
  3.     double N;
  4.     ifile >> N;
  5.     ifile.close();
  7.     ofstream ofile;
  8.     ofile.open("xx.out");
  9.     ofile << N << endl;
  10.     ofile.close();

控制输出精度

C++（include < iomanip > ）

  1.     cout << N << endl; // 10.468565425
  2.     cout << setprecision(4) << N << endl; //4精度浮点数 10.47
  3.     cout << fixed << setprecision(4) << N << endl; //精确到小数点后4位 10.4686
  5.     cout << setw(4) << setfill('0') << int(N) << endl; //前补0至占4位

C

  1.     printf("%.4f\n", N); //精确到小数点后4位
  2.     printf("%04d\n", (int)N); //前补0至占4位

字符串与数字互转

stoi
（include < string >）

  1. //默认按照十进制转换
  2.   string str = "10086";
  3.   int a = stoi(str);
  5.   string str = "0.1111";
  6.   float b = stof(str);
  8. //其他进制
  9.   std::string str_hex = "40c3";
  10.   std::string str_bin = "-10010110001";
  11.   std::string str_auto = "0x7f";
  13.   int i_hex = std::stoi (str_hex,nullptr,16);
  14.   int i_bin = std::stoi (str_bin,nullptr,2);
  15.   int i_auto = std::stoi (str_auto,nullptr,0);

to_string

  1. string str = to_string(a);

C++ streanstream

（include < sstream >）

数字转字符串

（直接转化时默认6位小数 如需固定精度则 ss << fixed << setprecision(8) << i;

#include <sstream>
#Include <string>
string num2str(double i)
{
        stringstream ss;
        ss<<i; 
        return ss.str();
}

字符串转数字

int str2num(string s)
 {   
        int num;
        stringstream ss(s);
        ss>>num;
        return num;
}

要同一个ss复用的话记得清空：ss.str("");

上面方法很简便, 缺点是处理大量数据转换速度较慢，用下面的c的库函数会更快

C sprintf, sscanf

可以用sprintf函数将数字输出到一个字符缓冲区中. 从而进行了转换（头文件< string > ）
例如：
已知从0点开始的秒数(seconds) ，计算出字符串"H:M:S", 其中H是小时, M＝分钟，S＝秒

数字转字符串

int H, M, S;
string time_str;
H=seconds/3600;
M=(seconds%3600)/60;
S=(seconds%3600)%60;
char ctime[10];
sprintf(ctime, "%d:%d:%d", H, M, S);             // 将整数转换成字符串
time_str=ctime;                                  // 结果

字符串转数字

与sprintf对应的是sscanf函数, 可以将字符串转换成数字

char str[] = "15.455";
int i;
float fp;
sscanf( str, "%d", &i );         // 将字符串转换成整数   i = 15
sscanf( str, "%f", &fp );        // 将字符串转换成浮点数 fp = 15.455000

printf( "Integer: = %d ", i);
printf( "Real: = %f ", fp); 
return 0;

常用库函数

erase()

（include < string > ）

删去字符串中的一段。一般用的参数是 (位置，删去的长度) 或是（起始位置，结束位置）

  std::string str ("This is an example sentence.");
  std::cout << str << '\n';
                                           // "This is an example sentence."
  str.erase (10,8);                        //            ^^^^^^^^
  std::cout << str << '\n';
                                           // "This is an sentence."
  str.erase (str.begin()+9);               //           ^
  std::cout << str << '\n';
                                           // "This is a sentence."
  str.erase (str.begin()+5, str.end()-9);  //       ^^^^^
  std::cout << str << '\n';
                                           // "This sentence."

insert()

（include < string > ）

插入一串字符串。一般用的参数是（位置，插入的字符串）

  std::string str="to be question";
  std::string str2="the ";
  std::string str3="or not to be";
  std::string::iterator it;

  // used in the same order as described above:
  str.insert(6,str2);                 // to be (the )question
  str.insert(6,str3,3,4);             // to be (not )the question
  str.insert(10,"that is cool",8);    // to be not (that is )the question
  str.insert(10,"to be ");            // to be not (to be )that is the question
  str.insert(15,1,':');               // to be not to be(:) that is the question
  it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question
  str.insert (str.end(),3,'.');       // to be, not to be: that is the question(...)
  str.insert (it+2,str3.begin(),str3.begin()+3); // (or )

  std::cout << str << '\n';

substr()

（include < string > ）

取一段子串。一般用的参数是（起始位置，要取的长度），如果要从某个位置开始一直取到末尾则是单一参数（起始位置）

  std::string str="We think in generalities, but we live in details.";

  std::string str2 = str.substr (3,5);     // "think"

  std::size_t pos = str.find("live");      // position of "live" in str

  std::string str3 = str.substr (pos);     // get from "live" to the end

  std::cout << str2 << ' ' << str3 << '\n';

compare（）

（include < string > ）

判断两字符串相等。若相等则返回0。
一般的用法即为str1.compare(str2)，若要将子串和str2比对则参数是（子串起始位置，长度，str2），若是两字符串的子串比对则是（str1子串起始，str1子串长度，str2，str2子串起始，str2子串长度）

  std::string str1 ("green apple");
  std::string str2 ("red apple");

  if (str1.compare(str2) != 0)
    std::cout << str1 << " is not " << str2 << '\n';

  if (str1.compare(6,5,"apple") == 0)
    std::cout << "still, " << str1 << " is an apple\n";

  if (str1.compare(6,5,str2,4,5) == 0)
    std::cout << "therefore, both are apples\n";

getline()

（include < string > ）

读入一行字符串。

string s;
getline(cin,s);

默认是换行为分隔符。
也可以用其他字符作为分隔符，如用空格作为分隔符。

string s;
getline(cin,s,' ');

append()

（include < string > ）

在字符串str的后面追加字符串。常用的参数是（追加的字符串）也即整串追加，或只追加一段，则是（追加的字符串，起始位置，长度）

  std::string str;
  std::string str2="Writing ";
  std::string str3="print 10 and then 5 more";

  str.append(str2);                       // "Writing "
  str.append(str3,6,3);                   // "10 "
  str.append("dots are cool",5);          // "dots "
  str.append("here: ");                   // "here: "
  str.append(10u,'.');                    // ".........."
  str.append(str3.begin()+8,str3.end());  // " and then 5 more"
  str.append<int>(5,0x2E);                // "....."

sscanf()

（include < cstdio > ）

从一个字符串中读进与指定格式相符的数据。

经常碰到一串固定格式字符串中有需要处理的数据，比如 0:23:21 -:–:– ：

sscanf(s.c_str(),"%d:%d:%d",&hh,&mm,&ss);

sprintf()

（include < cstdio > ）

把格式化的数据写入某个字符串。

int num;
char s[1000];
sprintf(s,"%d",num);

reserve()

（include < string > ）

翻转字符串

reverse(s.begin(),s.end());

next_permutation()

（include < algorithm>）

比当前char型数组排序大的下一种排序

next_permutation(c,c+strlen(c));

经过上面那条语句后，c[]=”abcd”变为 abdc

memset()

（include < cstring > ）

对于对int之类的数组，只能用memset对其初始化为0或-1。

如：

int a[]; memset(a,0,sizeof(a));

而对于char型，可以赋任何字符。

如：

char a[]; memset(a,'0',sizeof(a));

fill()

（include < iostream > ）

把那一块单元赋成指定的值

 char s[100];  
 fill(s,s+100,'a');

如果用memset给d[100]赋值1会出事 这时候就应用fill函数

int  d[100];  
fill(d,d+100,1);

find()

（include < string > ）

找到则返回第一个字符的索引
没找到则返回 string::npos（或者判一下int found > -1）

参数是：（待查字符串，被查字符串的起始位置，代查字符串的前几位）

  std::string str ("There are two needles in this haystack with needles.");
  std::string str2 ("needle");

  // different member versions of find in the same order as above:
  std::size_t found = str.find(str2);
  if (found!=std::string::npos)
    std::cout << "first 'needle' found at: " << found << '\n';

  found=str.find("needles are small",found+1,6);
  if (found!=std::string::npos)
    std::cout << "second 'needle' found at: " << found << '\n';

  found=str.find("haystack");
  if (found!=std::string::npos)
    std::cout << "'haystack' also found at: " << found << '\n';

  found=str.find('.');
  if (found!=std::string::npos)
    std::cout << "Period found at: " << found << '\n';

  // let's replace the first needle:
  str.replace(str.find(str2),str2.length(),"preposition");
  std::cout << str << '\n';

杂碎

string 和 char * 互转

string s转char c[]

strcpy(c,s.c_str());

char c[] 转 string s

s = c;

vector

1.声明和初始化

  1.     vector<int> vec;        //声明一个int型向量
  2.     vector<int> vec(5);     //声明一个初始大小为5的int向量
  3.     vector<int> vec(10, 1); //声明一个初始大小为10且值都是1的向量
  4.     vector<int> vec(tmp);   //声明并用tmp向量初始化vec向量
  5.     vector<int> tmp(vec.begin(), vec.begin() + 3);  //用向量vec的第0个到第2个值初始化tmp
  6.     int arr[5] = {1, 2, 3, 4, 5};   
  7.     vector<int> vec(arr, arr + 5);      //将arr数组的元素用于初始化vec向量，注意：其中不包括arr[5]元素，末尾指针都是指结束元素的下一个元素，

二维向量初始化为0

  1.     vector<vector<int>>vec(m,vector<int>(n,0));

2.基本操作

(1). 容量

向量大小： vec.size();
向量最大容量： vec.max_size();
更改向量大小： vec.resize();
向量真实大小： vec.capacity();
向量判空： vec.empty();
减少向量大小到满足元素所占存储空间的大小： vec.shrink_to_fit(); //shrink_to_fit

(2). 修改

多个元素赋值： vec.assign(); //类似于初始化时用数组进行赋值
末尾添加元素： vec.push_back();
末尾删除元素： vec.pop_back();
任意位置插入元素： vec.insert();//v1.insert(v1.end(), v2.begin(), v2.end()); /把v2加到v1末尾
任意位置删除元素： vec.erase(); //vec.erase (vec.begin()+5);  vec.erase (vec.begin(),vec.begin()+3);
交换两个向量的元素： vec.swap();
清空向量元素： vec.clear();

(3)迭代器

开始指针：vec.begin();
末尾指针：vec.end(); //指向最后一个元素的下一个位置
指向常量的开始指针： vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容，但还是可以通过其他方式修改的，而且指针也是可以移动的。
指向常量的末尾指针： vec.cend();

(4)元素的访问

下标访问： vec[1]; //并不会检查是否越界
at方法访问： vec.at(1); //以上两者的区别就是at会检查是否越界，是则抛出out of range异常
访问第一个元素： vec.front();
访问最后一个元素： vec.back();
返回一个指针： int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组，所以可以返回一个指针指向这个数组。这是是C++11的特性。

遍历

  1. vector<int>::iterator it;
  2. for (it = vec.begin(); it != vec.end(); it++)
  3.     cout << *it << endl;
  4. //或者
  5. for (size_t i = 0; i < vec.size(); i++) {
  6.     cout << vec.at(i) << endl;
  7. }

翻转

  1.     #include <algorithm>
  2.     reverse(vec.begin(), vec.end());

排序

  1.     #include <algorithm>
  2.     sort(vec.begin(), vec.end()); //从小到大排序
  3.     sort(vec.begin(),vec.end(), greater<int>() ); //从大到小排序
  4.     //或采用下面方法:
  5.     bool Comp(const int& a, const int& b) {
  6.         return a > b;
  7.     }
  8.     sort(vec.begin(), vec.end(), Comp);

查找元素

  1. if(find(v.begin(), v.end(), val) != v.end()){...} //val为待查找元素
  3. //用如下方法返回待查元素出现的下标
  4. find(v.begin(), v.end(), val)-v.begin();

求和

accumulate() 前两个参数指定要累加的元素范围，第三个是累加的初值。容器内的元素类型必须与第三个实参的类型匹配，或者可转换为第三个实参的类型

  1. int sum1 = accumulate(vec.begin(),vec.end(),0);
  2. double sum2 = accumulate(vec.begin(),vec.end(),0.0);
  3. string sum3 = accumulate(v.begin() , v.end() , string(" "));//从空字符串开始，每个元素连接成一个字符串。

next_permutation

用来计算全排列的函数，如果存在下一个greater permutation则返回true，否则返回false。

  1. next_permutation(nums.begin(), nums.end())

deque

声明双端队列

deque<int> que;

使用

  1.     que.push_front();
  2.     que.push_back();
  3.     que.pop_front();
  4.     que.pop_back()

priority_queue

声明

priority_queue <int> i; //默认从大到小
priority_queue <int,vector<int>,greater<int> > q; //从大到小
priority_queue <int,vector<int>,less<int> >q; //从小到大

队列中的也可以是结构体，需要重载‘<’符号
比如：

  1. struct node
  2. {
  3.     int x,y;
  4.     bool operator < (const node & a) const
  5.     {
  6.         return x<a.x;
  7.     }
  8. }k;
  9. priority_queue <node> q; //x从大到小排序

不重载 < 的办法：

  1. struct node
  2. {
  3.     int fir,sec;
  4. }input;
  6. struct cmp
  7. {
  8.     bool operator () (const node &x,const node &y) const
  9.     {
  10.         return x.fir<y.fir;
  11.     }
  12. };
  14. priority_queue<node,vector<node>,cmp> q; //按fir值从大到小

基本操作

q.size();//返回q里元素个数
q.empty();//返回q是否为空，空则返回1，否则返回0
q.push(k);//在q的末尾插入k
q.pop();//删掉q的第一个元素
q.top();//返回q的第一个元素

Map

插入数据

mapStudent.insert(pair<int, string>(1, "student_one")); //方式1
mapStudent[1] = "student_one"; //方式2

删除数据

mapStudent.erase(1);

获取map的大小

int nSize = mapStudent.size();

map的遍历

正向迭代器

  1.     map<int, string>::iterator it;  
  3.     for(it = ma.begin(); it != ma.end(); it++)  
  4.         cout<<it->first<<"  "<<it->second<<endl;

反向迭代器

  1.     map<int, string>::reverse_iterator it;  
  3.     for(it = ma.rbegin(); it != ma.rend(); it++)  
  4.         cout<<it->first<<"  "<<it->second<<endl;

数组形式

  1.  int nSize = ma.size();  
  3. //注意，是 for(int nindex = 1; nindex <= nSize; nindex++)  
  4. // 而不是 for(int nindex = 0; nindex < nSize; nindex++)  
  6.     for(int nindex = 1; nindex <= nSize; nindex++)  
  7.         cout<<ma[nindex]<<endl;  
  9. }

查找元素

第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况返回1

第二种：用find函数来定位数据（key）出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器。

map<int, string>::iterator iter;  
iter = mapStudent.find(1);  
if(iter != mapStudent.end())  
   cout<<"Find, the value is "<<iter->second<<endl;  
else  
   cout<<"Do not Find"<<endl;

第三种：
lower_bound函数，用来返回要查找关键字的下界(是一个迭代器)
upper_bound函数，用来返回要查找关键字的上界(是一个迭代器)

例如：map中已经插入了1，2，3，4的话，如果lower_bound(2)的话，返回的2，而upper-bound（2）的话，返回的就是3

Equal_range函数返回一个pair，pair里面第一个变量是Lower_bound返回的迭代器，pair里面第二个迭代器是Upper_bound返回的迭代器，如果这两个迭代器相等的话，则说明map中不出现这个关键字，

    pair<map<int, string>::iterator, map<int, string>::iterator> mappair;  
    mappair = mapStudent.equal_range(2);  
    if(mappair.first == mappair.second)  
        cout<<"Do not Find"<<endl;  
    else  
        cout<<"Find"<<endl;

map按value降序排序

（转换为vector然后排序）

  1.   struct cmp 
  2.     {   
  3.         bool operator()(const pair<int,int>& l, const pair<int,int>& r) {    
  4.             return l.second > r.second;    
  5.         }    
  6.     };
  7.     vector<pair<int,int>> vec(ma.begin(), ma.end());    
  8.     sort(vec.begin(), vec.end(), cmp());

unordered_map

std::map对应的数据结构是红黑树。红黑树是一种近似于平衡的二叉查找树，里面的数据是有序的。在红黑树上做查找、插入、删除操作的时间复杂度为O(logN)。而std::unordered_map对应哈希表，哈希表的特点就是查找效率高，时间复杂度为常数级别O(1)， 而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况，使用std::unordered_map容器，但是std::unordered_map对于迭代器遍历效率并不高。而如果对内存大小比较敏感或者数据存储要求有序的话，则可以用std::map容器。

用法是和map一样的。

Set

insert() 　　 ,插入元素

begin() 　　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear() 　　 ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

rbegin　　　　 ,返回的值和end()相同

rend()　　　　 ,返回的值和begin()相同

结构体set的遍历

  1.     struct A  
  2.     {  
  3.         int age;  
  4.         string name;  
  5.     };
  7.     for (set<A>::iterator it = setA.begin(); it != setA.end(); it++)  
  8.     {  
  9.         A a = (A)(*it);  
  10.         printf("age = %d, name = %s \n", a.age, a.name.c_str());  
  11.     }

图论

邻接表存图

https://www.cnblogs.com/ECJTUACM-873284962/p/6905416.html

  1. struct Edge  
  2. {  
  3.     int to;  
  4.     int val;      
  5. }edge[2*MAX_M];  
  7. void addEdge(int u ,int v, int w)  
  8. {  
  9.     edge[++tot].to = v;  
  10.     edge[tot].val = w;  
  11.     next[tot] = head[u];  
  12.     head[u] = tot;  
  13. }

并查集

  1. struct UF    
  2. { 
  3.     int fa[MAX_N]; 
  4.     void init() { for(int i = 1; i < MAX_N; i++) fa[i] = i;} 
  5.     int find(int a) { return fa[a] == a ? a : fa[a] = find(fa[a]);} 
  6.     void mix(int a,int b) { fa[find(a)] = find(b);} 
  7.     bool isSame(int a, int b) { return find(a) == find(b);} 
  8. } uf;

最小生成树

图中所有边的权值都不同时，最小生成树唯一
如果有2条或以上的边有相同权值，最小生成树不一定唯一（但最小的权值和唯一）

考虑n结点m条边的图中的最小生成树算法：

Prim算法（选点）

设集合V为已选结点集合，集合U为未选结点集合。
一开始所有结点的dist都为INF，起始结点的dist更新为0。每次从U中选一个dist最小的结点 i 加入V中，更新 i 结点所能到达全部结点 j 的dist值为dist[i]加上i，j间的边权。这样直到所有结点都加入V中为止。
时间复杂度O（n*n），主要与结点数有关，适用于稠密图。

【示例代码】
dis存的是结点到已被选中的这些点的最短路径

  1. void Prim() {  
  2.     int i;  
  3.     memset(vis,false,sizeof(vis));  
  4.     memset(dis,0x3f,sizeof(dis));  
  5.     cnt=dis[1]=0;  
  6.     while(true) {  
  7.         //寻找dis最小的结点u
  8.         u=0;  
  9.         for(i=1;i<=n;++i)  
  10.             if(!vis[i]&&dis[i]<dis[u])  
  11.                 u=i;  
  12.         if(u==0)  
  13.             return ;  
  14.         //将u加入集合V
  15.         vis[u]=true;  
  16.         ++cnt;  
  17.         //用u更新所有能到达的结点的dis 
  18.         for(i=1;i<=n;++i)  
  19.             dis[i]=min(dis[i],g[u][i]);  
  20.     }  
  21. }

Kruskal算法（选边）

设集合E为已选的边集合，集合U为未选的边集合。
把所有边的边权val排序后，每次选一条最短的边（即遍历边），判断下这条边的两个结点是否已经相连（并查集维护结点间是否相连），若没有则加入集合E。执行n-1次的加入操作后退出。（生成树的边数为n-1）
时间复杂度O（mlog（m）），主要与边数有关，不适用于稠密图。

  1. void kruskal(int num)
  2. {
  3.     int ned = num-1;
  4.     uf.init();
  5.     for(int i = 0; i < top && ned; i++)
  6.     {
  7.         if(!uf.isSame(e[i].x,e[i].y)) 
  8.         {
  9.             uf.mix(e[i].x,e[i].y);
  10.             ned--;
  11.         }
  12. }

最短路

单源最短路

SPFA算法

初始时所有点dist为INF，只有起始点的dist为0。然后建立一个队列，初始时队列里只有起始点，之后不断弹出队首结点 i 去更新它能到达的所有点 j 的dist值，如果dist[j] > dist[i]+value[i][j]则更新成功，再判断下被更新的结点若不在队列中（vis=0？），则把该点加入到队列。这样重复执行直到队列为空。

  1. void spfa() //源点到结点距离dist  
  2. {    
  3.     queue<int> que;    
  4.     que.push(s);    
  5.     vis[s] = true;    
  7.     while(!que.empty())    
  8.     {    
  9.         int u = que.front();     
  10.         for(j = head[u]; j ; j = next[j])    
  11.         {    
  12.             int v = edge[j].to;  
  13.             if(dist[u]+edge[j].val < dist[v])    
  14.             {   
  15.                 dist[v] = dist[u]+edge[j].val;  
  16.                 if(!vis[v])     
  17.                 {    
  18.                     que.push(v);    
  19.                     vis[v] = true;    
  20.                 }  
  21.             }  
  22.         }   
  23.         que.pop();   
  24.         vis[u] = false;   
  25.     }    
  26. }

所有顶点间最短路

Floyd算法

逐点试探，看加入这个点是否会影响结果。

for(k=1;k<=n;k++)   
    for(i=1;i<=n;i++)   
        for(j=1;j<=n;j++)   
            if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j];

代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，来进行松弛操作。

Floyd算法允许负权边不允许负权图。（否则可以一直走负圈）

技巧算法

快速幂

  1. LL power(LL bas, LL exp)
  2. {
  3.     LL ans = 1, sqr = bas%MOD;
  4.     while(exp > 0)
  5.     {
  6.         if(exp & 1) ans = (ans*sqr) % MOD;
  7.         sqr = (sqr*sqr) % MOD;
  8.         exp >>= 1;
  9.     }
  10.     return ans;
  11. }

树状数组

查询和修改复杂度都为log(n)
原理：https://blog.csdn.net/c20190102/article/details/70841745

  1.     int lowbit(int t)
  2.     {
  3.         return t&(-t);
  4.     }
  6.     void update(int x,int val)
  7.     {
  8.         for(int i=x;i<=n;i+=lowbit(i))
  9.             tree[i]+=val;
  10.     }
  12.     int getsum(int x)
  13.     {
  14.         int ans=0;
  15.         for(int i=x;i>0;i-=lowbit(i))
  16.         ans+=tree[i];
  17.         return ans;
  18.     }
  20.     //在main中的初始化
  21.     for(int i=1;i<=n;++i)
  22.     {
  23.         scanf("%d",&a[i]);
  24.         update(i,a[i]);
  25.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注