Cpp算法编程基础

常用数据结构

字符串操作

// 字符串拼接
string a="hello ";
string b="world";
a.append(b);
// 子字符串
a.substr(start_index, length);
// 数值转字符串

调用快速排序

// 基础版，从小到大排列
int n; // 数组长度
int nums[128]; // 定义数组
sort(nums, nums+n);
// 自定义排序函数
bool cmp(int x, int y){
  return x<y; // < 从小到大， < 从大到小
}
sort(nums, nums+n, cmp);
// 或者通过定义一个结构体，重载操作符的方式实现自定义排序
struct st{
  string name;
  bool operator< (const st &other) const{
    return int(name[0])<int(other.name[0]);
  }
};
st nums[128]; // 定义数组
sort(nums, nums+n);

优先级队列

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

struct pro{ // 定义结构体
    int cost;
    int profit;
    pro(int c, int p):cost(c),profit(p){} // 构造函数
};
struct cmp{
    bool operator()(const pro &a, const pro &b) const{
        return a.cost < b.cost; // 用在优先级队列中，将会得到一个最大堆
    }
};

priority_queue<pro, vector<pro>, cmp> cp;

// 闭包写法的比较函数
int main(){
      vector<vector<int>> nums;
      vector<int> next(size);
  		// 学不来的话可以采用全局变量的方式 
      auto cmp = [&](const int& u, const int& v) { // 最小优先级队列 封闭函数定义
          // 在闭包中，可以使用之外的next数组等变量。具体语法并不了解
          return nums[u][next[u]] > nums[v][next[v]];
      };
      priority_queue<int, vector<int>, decltype(cmp)> que(cmp);
  		// decltype 自动类型推导
}

在STL中默认使用()进行比较的，默认使用less（即<运算符），所以一般的排序之后，前面的元素小于后面的元素。但优先级队列中的源码虽然也使用的less，但最终得到的结果却是大根堆，这是因为优先级队列的队首指向最后，队尾指向开始。参考来源。闭包函数

输入输出

cin和cout输入输出加速

// io 流加速
ios_base::sync_with_stdio(false);
cin.tie(0);

读取和输出数据

类型	格式化	样例
int	%d	scanf("%d", &n);
long long	%lld	scanf("%lld", &n);
float	%f	scanf("%f", &fl);
float	%f	scanf("%f", &fl);
double	%lf	scanf("%lf", &db);
char	%c	scanf("%c", &c);
char数组或者string	%s	scanf("%s", str);
读取完整的一行(包括换行符)		fgets(char *, int size, stdin);

运算符

// c++ 不支持负数的移位操作
int a=-1;
int b = (unsigned int)a<<1;