C++算法实现

2018/06/27 C 共 3105 字,约 9 分钟

C++语法及函数

输入输出

//格式化输出
	printf("%03d", n);
	double a = 3.4134;
	printf("%5.3f", a);
//读取一行
    getline(cin,str);
//long long
	long long n;
	scanf("%lld", &n);
	printf("%lld", n);

输入输出重定向

    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

文件读写

c++文件读写 link

//写入到文件
    ofstream fout;
    fout.open("test.txt");
    fout<<"write something";
    fout.close();
//读取文件
    ifstream fin("test.txt");
    char ch;
    fin>>ch;//从文件中读取一个字符
    string line;
    getline(fin,line);//读取一行转换成字符串

数据类型

int 9位 double 15位 Long long19位

INT_MAX和INT_MIN宏

    string s(10000,'0');  //全0字符串
    //发现第一个非0字符的位置,npos为结束标志
    if (s.find_first_not_of('0') == string::npos)
        cout << "0" << endl;
    else
        cout << s.substr(s.find_first_not_of('0')) << endl;
        //从非0开始的子串

二维vector声明

vector<vector<int>> v(5, vector<int>(5, 0));

字符串和数字相互转换

对于string与int的转换, 刷题用stoi(string)函数和to_string(int)函数

对于char数组和int的转换,刷题用sscanf和sprintf函数

    sprintf( buffer,"   String:    %s\n", s );
    // 给定一个字符串iios/12DDWDFF@122,获取 / 和 @ 之间的字符串,
    // 先将 "iios/"过滤掉,再将非'@'的一串内容送到buf中
    sscanf("iios/12DDWDFF@122", "%*[^/]/%[^@]", buf);
    printf("%s\n", buf);
    // 结果为:12DDWDFF 

    // 给定一个字符串““hello, world”,仅保留world。(注意:“,”之后有一空格)
    sscanf(“hello, world”,  "%*s%s",  buf);  
    printf("%s\n", buf);
    // 结果为:world

char数组可以直接赋值给string, string转换为char数组需要借助strcpy()函数和string.c_str()函数

    string a = "feafhh";
	char p[100];//这里必须为数组,不能是*p
	strcpy(p, a.c_str());
	printf("%s", p);

map

#include<utility>
pair<T1, T2> p;
pair<T1, T2> p(v1, v2);
make_pair(v1, v2)
p.first
p.second

int main(){
    pair<int, string> p1(0, "Hello");
    printf("%d, %s\n", p1.first, p1.second.c_str());
    pair<int, string> p2 = make_pair(1, "World");
    printf("%d, %s\n", p2.first, p2.second.c_str());
    return 0;
}

map查找遍历

    map<int, int>::iterator it_find;
    it_find = mp.find(0);
    if (it_find != mp.end()){
            it_find->second = 20;
    }else{
            printf("no!\n");
    }

    map<int, int>::iterator it;
    for (it = mp.begin(); it != mp.end(); it++){
            printf("%d->%d\n", it->first, it->second);
    }

优先队列自定义排序

link

struct cmp{
    bool operator()(int &x,int &y){
        return test[x]>test[y];
    }
};
priority_queue<int,vector<int>,cmp> que1;

// OR

struct node{
    int x, y;
    bool operator<(const node &nod)const{
        return x>nod.x;//x越小,优先级越高
    }
};
priority_queue<node>que3;

反转

link

string s=str;
reverse(s.begin()+2,s.begin()+7);//和下面一句效果一样

char str[]="abcdefgh";
reverse(str+2,str+7);
// or
reverse(begin(str),begin(str)+7)

reverse(begin(a), begin(a) + n);
reverse(begin(a), begin(a) + m);
reverse(begin(a) + m, begin(a) + n);

fill和memset

link

    int arr[10];
    fill(arr, arr + 10, 2);

    vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    fill(v.begin(), v.end(), -1);

next_permutation

link

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main() {
        string s = "0123456789";
        int n;
        cin >> n;
        int cnt = 1;
        do {
            if(cnt == n) {
                cout << s;
                break;
            }
            cnt++;
        }while(next_permutation(s.begin(), s.end()));
        return 0;
    }

swap()

    vector<int> a;
    a.push_back(3);
    a.push_back(4);
    swap(a[0],a[1]);
    cout<<a[0]<<" "<<a[1]<<endl;

sort

sort需要引入algorithm

对于数组

int arr[10];
sort(arr,arr+10,cmp);

对于vector

vector<int> arr;
sort(arr.begin(),arr.end(),cmp);

对于常见类型: int double char等 cmp可替代为

greater<int>()和less<int>(),别忘了加括号
需要引入头文件functional.h

也可自定义比较函数,返回bool

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

对于自定义结构体

struct d{int c,d;};

需要自定义比较函数

bool cmp(d a,d b){
    return a.c>b.c;
}

Search

    Table of Contents