算法查漏补充

2019-02-25 约 2672 字预计阅读 6 分钟收录于算法

常用函数

math常用函数

取绝对值：fabs(double x)
向下取整、向上取整：floor(double x),ceil(double x)
次幂：pow(double r, double p) t^p
算数平方根：sqrt(double x)
自然对数：log(double x)，常规对数可用换底公式
asin(double x)，acos(double x)，acos(double x)
四舍五入：round(double x)

algorithm常用函数

max(a,b)、min(a,b)
swap(a,b);
reverse(it, it2) 将数组指针在[it,it2)中的元素反转
fill(a, a+5, 23) menset的升级版，数字类型对应范围内的任一值
sort()
lower_bound(first, last, val)、upper_bound(first, last, val) 分别返回第一个值大于等于val的元素位置、和第一个值大于val的元素位置

STL标准模板库

vector： push_back()、pop_back()、size()、clear()、insert(it, val)、erase(it)、erase(first, last)、empty()
list: 双向链表，push_back()、pop_back()、push_front()、pop_front()、splice()
- l1.splice(l1.begin(), l1, l1.begin()+1) 效果l1:1-2-3 -> l1:2-1-3
- splice 字符串拼接，重要
set：内部有序且元素不重复；set内自动对元素递增排序，且去除重复元素
insert(val)、find(val){ 找到则返回迭代器，否则返回s.end()}、erase(it)、size()、clear()、
string： length()/size()、insert(pos, string)、erase(it)、erase(first,last)、clear()、substr(pos, len)、find(str)、find(str,pos)、replace(pos,len,str)、replace(it1,it2,str) str.find(s) != string::npos
- 如果有字符串时候不要用+,会提高时间复杂度和而且很吃内存，可使用push_back()添加字符和append添加字符串
map： it->first、it->second、find(val)、erase(it)、erase(key)、erase(it1,it2)、size()、clear()
默认由关键字从小到大排序，find()找不到返回m.end()
插入操作mapTest.insert(std::make_pair(3, “test3”)); mapTest.insert(std::pair<int, std::string>(4, “test4”))
queue： push()、pop()、front()、back()、empty()、size() 使用front和pop必须先用empty判空
priority_queue： push()、pop()、top()、empty()、size()
stack： push()、pop()、top()、empty()、size()
pair： #include 也可用#include来代替，应为map头文件包含了utility
对容器的操作多用迭代器，对数组的额操作多用指针

vector定义二维数组

//定义一个二维数组
vector<vector<int>> arr;

//定义一个3行4列的数组
vector<vector<int>> arr(3,vector<int>(4));
//二维数组的行数
arr.size()
//二维数组的列数
arr[0].size()

浮点数比较

const double eps=1e-8;
if(fabs(f1-f2)<eps) 则可视为f1==f2

对ASCII字符计数用数组就行，不必用unordered_map

如对字符串s统计不同的字符个数，首先想到用散列表进行映射，这自然可以
但在这种情况下，字符是属于ASCII码的，ASCII码是有数值范围(0-127)的，所以用一个int数组即可int ch[128]

unordered_map与map

unordered_map<char, int> hash;  // 无序的hash表，底层hash表,时间复杂度是O(1)

对于键值对，其中值为int型的数据来说，unordered_map初始化为0，如hash[‘a’]++后其值则为1，而不是异常值,故不必初始化为0
map对应的数据结构是红黑树，红黑树是一种近似于平衡的二叉查找树，里面的数据是有序的，查找操作的时间复杂度为 O(logN)。unordered_map对应哈希表，元素无序，哈希表的特点就是查找效率高，时间复杂度为常数级别 O(1)
在C++中若要实现哈希表，则也使用unordered_map来实现

sort

只能对线性容器进行排序

如vector，list，deque，而对非线性容器如map、set(内部为红黑树实现)等无法排序
若相对map按值(map默认按键排序)进行排序，可将map元素添加到vector<pair<char,int»容器中，然后用sort

bool cmp(const pair<char,int> &x,const pair<char,int> &y) {
	return x.second < y.second;
}
vector<pair<char,int>> arr;
for (map<char,int>::iterator it = mp.begin(); it != mp.end(); ++it)
    arr.push_back(make_pair(it->first,it->second));
sort(arr.begin(), arr.end(), cmp);
//遍历一
for (vector<pair<char,int>>::iterator it = arr.begin(); it != arr.end(); ++it)
//遍历二
for (auto item : arr)

比较函数cmp

struct Less {
    bool operator() (const int& x, const int& y) {
        return x < y; //从小到大排序
    }
};

int main() {
    vector<int> a = {1,3,7,43,2,0,3};
    sort(a.begin(), a.end(), Less());
    for (auto i : a) 
        cout << i << " ";
    return 0;
}

递归相关

将递归程序改为遍历程序时要借助栈，如树的遍历
- 对于树的遍历来说，根在前好遍历即先序遍历程序比较好写，故写后序遍历时先将遍历顺序改为根-右-左，再将其逆置即变为左右根的后序即可

文件操作(C语言)

FILE *fp;
fp = fopen("C:\\Users\\17806\\OneDrive\\桌面\\Score.txt", "r");  //只读方式打开文件
char s[10]; fscanf(fp, "%s", s); 读取字符串，因无法读取'\0'结束符，故不能用puts()输出，只能遍历字符数组输出

while (!feof(fp))   //读取一行
{
    c=fgetc(fp);
    if (c == '\n')
        break;
    putchar(c);
}

int i=0;  //读取整个文件放在字符数组s[]中
while (!feof(fp))
{
    s[i++] = fgetc(fp);
}

字符串

sstream

sstream头文件含有istringstream和ostringstream

ostringstream：将字符串写入输出流，即保存字符串

//ostringstream将输出的字符、字符串、整数、浮点数都转换成字符串存在输出流中
ostringstream outstr;
outstr << "12 3";
outstr << "ldf ";
//获取指针位置
long int pos = outstr.tellp();  
cout << pos;     //输出：8
// 将指针指向位置6
outstr.seekp(6);
outstr << 123;
outstr << 'a';
//获取字符串用.str()方法
cout << outstr.str(); //输出：12 3ld123

istringstream：将字符串写入输入流，即读取字符串

//从输入流中读取数据，根据接收类型的不同将数据转换成不同类型
// 遇到空格停止输入且跳过空格，即使用char和string来接收也不行
istringstream instr(outstr.str());
int a;
instr >> a;
cout << a;  //输出：12

char c;
instr >> c;
cout << c;  //输出：3

string s;
instr >> s;
cout << s;  //输出：3ld123

//连续读取  用eof()来判断是否到达末尾
string str;
while (!instr.eof()) {
    instr >> str;
}

字符串转整数–整数转字符串

string str = to_string(整数)
int a = stoi(字符串)

其他

const double pi=acos(-1)
空间换时间：10^5用数组就可以 10^9则要用散列
最大公约数gcd

int gcd(int a, int b)
{
    if (b == 0) return a;
    else return gcd(b, a%b);
}

目录