关于c++:算法笔记经典模板

BFS 模板

void BFS(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        取出队首元素 front;
        访问队首元素 front;
        将队首元素出队；将 front 的下一层结点中未曾入队的结点全副入队，并设置已入队
    }
}

DFS 模板

递归

priority_queue 的 cmp 函数模板：

struct fruit{
    string name;
    int price;
}

struct cmp{bool operator () (fruit f1,fruit f2){return f1.price > f2.price;}
}

int main(){
    priority_queue<fruit,vector<fruit>,cmp> q;
    return 0;
}

中序序列和先序序列、后序序列、层序序列配合重建二叉树的模板：

// 记住 create 函数模板，不论中序和谁配合，模板如下
//postL 是后序序列的左端点
//postR 是后序序列的右端点
//inL 是中序序列的左端点
//inR 是中序序列的右端点
//postOrder 是后序序列
//inOrder 是中序序列
node* create(int postL,int postR,int inL,int inR){if(postL>postR){return NULL;}
    int in = postOrder[postR];
    node* root = new node;
    root->data = in;
    int k;
    for(k=inL;k<=inR;k++){if(inOrder[k]==in){break;}
    }

    int numLeft = k-inL;// 这一步肯定要有

    root->lChild = create(postL,postL+numLeft-1,inL,inL+numLeft-1);
    root->rChild = create(postL+numLeft,postR-1,inL+numLeft+1,inR);
    return root;
}

并查集寻找根节点的模板：

// 递归写法
int findFather(int n){if(n==father[n]){return n;}
    else{
        // 小括号和中括号要离开
        return findFather(father[n]);
    }
}

并查汇合并汇合的模板：

void unionS(int a,int b){int fA = findFather(a);
    int fB = findFather(b);
    if(fA != fB){father[fA] = fB;
    }
    return;
}

迪杰斯特拉算法 + 新增点权 + 求最短门路条数：

void Dij()
{
    // 以下三行是初始化工作：// 终点到终点的间隔是 0；// 终点到终点的最短门路有 1 条；// 终点到终点累计能够取得的最大资源 = 该终点自身领有的资源
    d[now]  = 0;
    shortestNum[now] =1;
    maxRescue[now] = cityRescue[now];
    
    // 整个 for 循环中没有用到 i 的中央，i 只用来计数
    for(int i=0; i<cityNum; i++)
    {
        int u = -1;
        int minLen = inf;
        // 寻找以后间隔终点间隔最短的点
        for(int j=0; j<cityNum; j++)
        {if(!vis[j] && d[j]<minLen)
            {
                u = j;
                minLen = d[j];
            }
        }
        
        if(u==-1)
        {return;}
        // 阐明 u 曾经被拜访过了
        vis[u] = true;
        int len = save[u].size();
           // 通过 u 来更新
        for(int j=0; j<len; j++)
        {int number = save[u][j].num;
            int roadLen = save[u][j].road;
            // 首先要确定该结点没有被拜访过
            if(!vis[number])
            {if(d[number]> d[u]+roadLen)
                {d[number] = d[u]+roadLen;
                    shortestNum[number] = shortestNum[u];
                    // 如果最短门路变了，那么累计取得的最大资源要无条件扭转
                    maxRescue[number] = maxRescue[u]+cityRescue[number];
                }
                else if(d[number]==d[u]+roadLen)
                {shortestNum[number] += shortestNum[u];
                    // 如果最短门路没变，那么累计取得的最大资源要有条件扭转
                    if(maxRescue[u]+cityRescue[number]>maxRescue[number]){maxRescue[number] = maxRescue[u]+cityRescue[number];
                    }
                }
            }
        }
    }

}

弗罗伊德算法模板

void Floyed()
{for(int k=0; k<n; k++)
    {for(int i=0; i<n; i++)
        {for(int j=0; j<n; j++)
            {if(dis[i][k]!=INF && dis[k][j]!=INF && dis[i][k]+dis[k][j]<dis[i][j])
                {dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }

}

普里姆算法模板

// G 为图, 个别设置成全局变量; 数组 d 为顶点与汇合 S 的最短距离
Prime(G,d[]){
    初始化;
    for(循环 n 次){u = 使 d[u]最小的还未被拜访的顶点的标号;
        记 u 已被拜访;
        for(从 u 登程能达到的所有顶点 v){if(v 未被拜访 && 以 u 为中介点使得 v 与汇合 S 的最短距离 d[v]更优){将 G[u][v]赋值给 v 与汇合 S 的最短距离 d[v];
            }
        }
    }
}

求素数模板

// 给定一个数，判断它是不是素数
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

// 外围代码
bool isPrime(int n){if(n<=1){return false;}
    int a = (int)sqrt(1.0*n);// 向下取整
    for(int i=2; i<=a; i++){if(n%i==0){return false;}
    }
    return true;
}


int main()
{
    int n;
    scanf("%d",&n);
    bool is = isPrime(n);
    if(is){printf("Yes");
    }
    else{printf("No");
    }
    return 0;
}

求素数表模板（埃氏筛法）

// 求 1 到 n 之间的所有素数，#include <iostream>
#include <stdio.h>
using namespace std;
const int maxn = 1000;
bool is[maxn] = {false};
int prime[maxn];
int p=0;
int n;

// 外围代码
void findPrime(){for(int i=2;i<=n;i++){if(!is[i]){prime[p] = i;
            p++;
            for(int j=i+i;j<=n;j = j+i){is[j] = true;
            }
        }
    }
}


int main()
{scanf("%d",&n);
    findPrime();
    for(int i=0; i<p;i++){printf("%d\n",prime[i]);
    }
    return 0;
}

求解最大公约数的模板

// 给定两个数 n 和 m，求 n 和 m 的最大公约数 a
#include <iostream>
#include <stdio.h>
using namespace std;


// 外围代码；不用关怀 a 和 b 的大小，默认 a >b，就算 a <b，通过一轮迭代之后，也会变成 a >b
int gcd(int a,int b){if(b==0){return a;}
    else{return gcd(b,a%b);
    }
}


int main()
{
    int n;
    int m;
    scanf("%d%d",&n,&m);
    int a = gcd(n,m);
    printf("%d",a);
    return 0;
}

求解最小公倍数的模板

// 给定两个数 n 和 m，求 n 和 m 的最小公倍数 b
#include <iostream>
#include <stdio.h>
using namespace std;

// 外围代码
int gcd(int a,int b){if(b==0){return a;}
    else{return gcd(b,a%b);
    }
}


int main()
{
    int n;
    int m;
    scanf("%d%d",&n,&m);
    int a = gcd(n,m);
    int b = (n/a)*m;// 先求最大公约数，而后再求最小公倍数
    printf("%d",b);
    return 0;
}

求斐波拉契数列模板（动静布局办法）

一个问题能用动静布局办法求解，须要满足以下两个条件：

1. 存在重叠子问题。
2. 存在最优子结构（全局问题的最优解能够由部分问题的最优解形成）

// n 为 45 的时候，F(n)就曾经有 10 位数了，超过 45 的时候，就超过 int 的极限了，而 int 是有符号数，符号位产生了扭转
#include <iostream>
#include <stdio.h>
using namespace std;
const int maxn = 1000;
int dp[maxn];

// 外围代码
int F(int n){if(n==0 || n==1){return 1;}
    // 这一步让计算复杂度升高很多
    else if(dp[n]!=-1){return dp[n];
    }
    else{dp[n] = F(n-1)+F(n-2);
        return dp[n];
    }
}


int main()
{for(int i=0; i<maxn; i++){dp[i] = -1;
    }
    int n;
    scanf("%d",&n);
    int a = F(n);
    printf("%d",a);
    return 0;
}

sort 函数

应用 sort 函数前，进行如下申明：

#include <algorithm>
using namespace std;

sort(首元素地址（必填），尾元素地址的下一个地址（必填），比拟函数（非必填）)

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;
#define EQU(a,b) (fabs((a)-(b))<eps)
#define GREATER(a,b) (((a)-(b))>eps)
#define LESS(a,b) (((a)-(b))<(-eps))
#define GREATER_EQU(a,b) (((a)-(b))>(-eps))
#define LESS_EQU(a,b)  (((a)-(b))<(eps))

struct node{
    int id;
    string name;
    double grade;
}tmp[3];

bool cmp2(node a,node b){if(EQU(a.grade,b.grade)){
        // 问题雷同时依照字典序排列
        return a.name >b.name;
    }
    else{
        // 问题高的在后面
        return GREATER(a.grade,b.grade);
    }
}


bool cmp(double a,double b){return a>b;}

int main() {double a[] = {1.2,4.3,-2.34,23.44};
    sort(a,a+3);
    for(int i=0; i<4; i++){printf("%lf\n",a[i]);
    }
    printf("---------------------------------\n");

    double b[] = {1.0,2.0,3.0,4.0};
    sort(b,b+4,cmp);
    for(int i=0; i<4; i++){printf("%lf\n",b[i]);
    }
    printf("---------------------------------\n");

    tmp[0].grade=12.33;
    tmp[0].id=1;
    tmp[0].name="Jack";

    tmp[1].grade=12.33;
    tmp[1].id=2;
    tmp[1].name="Rose";

    tmp[2].grade=13.33;
    tmp[2].id=3;
    tmp[2].name="Tom";
    sort(tmp,tmp+3,cmp2);
    for(int i=0; i<3; i++){printf("%d\t%s\t%.2f\n",tmp[i].id,tmp[i].name.c_str(),tmp[i].grade);
    }
    return 0;
}

priority_queue 中自定义优先级

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

struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1,fruit f2){return f1.price>f2.price;}
}f1,f2,f3;

int main() {
    priority_queue<fruit> q;
    f1.name = "taozi";
    f1.price = 3;
    f2.name = "lizi";
    f2.price = 4;
    f3.name = "pingguo";
    f3.price = 1;
    q.push(f1);
    q.push(f2);
    q.push(f3);
    cout<<q.top().name<<endl<<q.top().price<<endl;
    return 0;
}

将 string 类型变量转化为 int、long、float、double 型变量

C 语言转换模式:

std::string str;
int i = atoi(str.c_str());

C++ 转换模式(C++11):

std::string str;
int i = std::stoi(str);

同样, 能够应用 stol(long), stof(float), stod(double) 等.

参考文章

将 int、long、float、double 型变量转化为 string 类型变量

to_string()函数办法是 C ++11 新增的对数字转为字符串 string 类对象的新性能，次要函数接口如下：

std::to_string
  C++  Strings library std::basic_string  Defined in header <string>
std::string to_string(int value);
std::string to_string(long value);
std::string to_string(long long value);
std::string to_string(unsigned value);
std::string to_string(unsigned long value);
std::string to_string(unsigned long long value);
std::string to_string(float value);
std::string to_string(double value);
std::string to_string(long double value);

性能真的很弱小而且也很不便。应用如下：

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

string str = to_String(123405);

参考文章

将单个字符 char 转化为 string

应用 push_back()

char c = 'a';
string s1;
s1.push_back(c);

更多办法：

const char c = 'a';
//1. 应用 string 的构造函数
string s(1,c);

//2. 申明 string 后将 char push_back
string s1;
s1.push_back(c);

//3. 应用 stringstream
stringstream ss;
ss << c;
string str2 = ss.str();

// 留神 应用 to_string 办法会转化为 char 对应的 ascii 码，起因是 to_string 没有承受 char 型参数的函数原型，// 有一个参数类型为 int 的函数原型，所以传入 char 型字符，理论是先将 char 转化为 int 型的 ascii 码，而后再转变为

//string，以下输入后果为 97

cout << to_string(c) << endl;

参考文章

将单个字符 string 转化为 char

应用 c_str()将 string 转化为 char 数组，这个数组其实只有一个元素，就是咱们要的 char 元素

string f = "m";
const char *g1 = f.c_str();
printf("%s\n",g1);

数字字符和数字的相互转换

// 对于 1 位数字而言，其整数模式和字符模式差一个 '0'
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    // 字符变数字
    char a='3';
    int b = a-'0';
    int c = b+2;
    printf("%d\n",c);
    
    // 数字变字符
    int d = 6;
    char e = d+'0';
    printf("%c\n",e);
    return 0;
}

小写字母和大写字母的相互转换

// 小写字母比大写字母大 32
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    char a = 'A';
    printf("%c\n",a+32);
    char b = 'g';
    printf("%c\n",b-32);
    return 0;
}

将 int 型数组转换为 int 型整数

// 用户指定输出 a 位数，而后输出 a 位数，造成 int 型数组，而后将 int 型数组转化为 int 型整数
#include <iostream>
#include <stdio.h>
using namespace std;
const int maxn = 1000;
int num[maxn];
int a;

int toInt(){
    int sum = 0;
    for(int i=0; i<a; i++){sum = sum*10 + num[i];
    }
    return sum;
}

int main()
{scanf("%d",&a);
    for(int i=0; i<a; i++){scanf("%d",&num[i]);
    }
    int result = toInt();
    printf("%d",result);
    return 0;
}

将 int 型整数转换为 int 型数组

写上面这段代码时失去一个 教训：

全局变量和局部变量不能同名，否则会呈现无奈发现的谬误

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
const int maxn = 1000;
int n;
int num[maxn];
int k=0;

// 外围代码
void toArray(){for(int i=0; i<k; i++){num[i] = n%10;
        n /=10;
    }
}

int main()
{scanf("%d",&n);
    while(n>=pow(10,k)){k++;}
    toArray();
    for(int i=0; i<k; i++){printf("%d\n",num[i]);
    }
    return 0;
}

sscanf 和 sprintf 模板

作用是实现 字符串 和数字 的转换。

sscanf和 sprintf 均在 stdio.h 头文件下。

scanf("%d",&n);
printf("%d",n);

能够写成上面的样子，screen 代表屏幕：

scanf(screen,"%d",&n);// 将屏幕上用户输出的字符串写到 n 里（自左向右）printf(screen,"%d",n);// 将 n 的内容以字符串的模式显示在屏幕上（自右向左）

把 screen 换成 字符数组str，就是 sscanf 和 sprintf 的用法：

sscanf(str,"%d",&n);// 将 str 中的内容写到 n 里（自左向右）sprintf(str,"%d",n);// 将 n 的内容以字符串的模式写到 str 上（自右向左）

典型利用如下：

#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{char str[10] = "123";
    int a;
    sscanf(str,"%d",&a);// 将字符串转化为数字
    printf("%d\n",a);
    int b = 124332;
    char stt[20];
    sprintf(stt,"%d",b);// 将数字转化为字符串
    printf("%s\n",stt);
    return 0;
}

高级利用如下：

先修常识 1：

读入 double型变量的语法：

double a;
scanf("%lf",&a);

输入 double型变量的语法：

printf("%f",a);

或者

printf("%.2f",a);

先修常识 2：

初始化字符数组的办法：

char str[100]= "123a";

// 正文中为谬误写法
//char str[100];
//str= "123a";

// 正文中为谬误写法
//char str[100];
//str[100]= "123a";

正式利用 1：

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n;
    double db;
    char str[100] = "2048:3.14,hello";// 初始化字符数组的办法
    char str2[100];
    sscanf(str,"%d:%lf,%s",&n,&db,str2);// 读入 double 型变量的语法：printf("%d\n",n);
    printf("%.2f\n",db);
    printf("%s\n",str2);
    return 0;
}

正式利用 2：

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int n=12;
    double db = 3.1415;
    char str[100];
    char str2[100] = "good";
    sprintf(str,"%d:%.2f,%s",n,db,str2);
    printf("%s",str);
    return 0;
}

圆周率与浮点数比拟

浮点数在计算机中的存储并不总是准确的，须要引入一个极小数 eps 对这种误差进行修改，eps 个别取 1e-8

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

const double eps = 1e-8;
const double Pi = acos(-1.0);
// 留神，Equ 前面要跟小括号
#define Equ(a,b) ((fabs((a)-(b)))<(eps))
#define More(a,b) (((a)-(b))>(eps))
#define Less(a,b) (((a)-(b))<(eps))
#define MoreEqu(a,b) (((a)-(b))>(-eps))
#define LessEqu(a,b) (((a)-(b))<(eps))
int main()
{
    cout << "Hello world!" << endl;
    return 0;
}

读入未知个数的 string 类型字符串

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;


int main()
{
    string str;
    vector<string> now;
    //getline(cin,str)!=NULL 和 getline(cin,str)!=- 1 都是错的
    while(getline(cin,str)){now.push_back(str);
    }
    int len = now.size();
    for(int i=0; i<len; i++){cout<<now[i]<<endl;
    }
    return 0;
}

取得单链表从后往前第 k 位

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {int now[5002];
        int i=0;
        while(head->next != NULL){now[i] = head->val;
            i++;
            head = head->next;
        }

        i = i-2;
        ListNode* tmp;
        tmp = head;
        while(i>=0){ListNode* a = new ListNode(now[i]);
            tmp->next = a;
            tmp = a;
            i--;
        }
        return head;
    }
};

参考书目：《算法笔记》