必备算法技巧 -- 掌握这些可以成倍提高写算法题的效率

本文主要是介绍必备算法技巧 -- 掌握这些可以成倍提高写算法题的效率，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

写在前面：我们写算法题不是要创造算法，这是专门从事算法研究该做的事，我们就是学会一些很有用的算法，学习它们的使用方法，学习它们的使用场景。写算法题的过程不是创造算法的过程，而是利用所学的或所掌握的算法知识和算法技巧完成这道题的任务（好比在已知一些公式定理的条件下给你一些数据，让你解一道应用题）。

1. 学会写注释，一种好的写注释习惯可以成倍的提高你的编码效率，而一种不好的写注释习惯可能会浪费你大量的时间，降低你的编码效率，可以参考这篇文章：https://www.cnblogs.com/hi3254014978/p/12235417.html

2. 格式化输出

%d,
 %md, 左对齐，占m位，默认补空格
%0md,左对齐，占m位，补0
 %-md;右对齐，占m位

%.2f保留2位小数

保留两位小数（c++方法）(加iomanip.h头文件）
cout << setiosflags(ios::fixed) << setprecision(2) << 123.4567 << endl;

3. math.h头文件中包含的很有用的函数
fabs()：对double数取绝对值
round(): 四舍五入成一个小数部分全为0的double数
floor():  向下取整成一个小数部分全为0的double数
ceil(): 向上取整成一个小数部分全为0的double数

4. gets(), scanf的%s, puts()和printf的%s, getchar(), putchar();

　　注意：1.  如果用 scanf 输入一个非字符串数据后，紧接着用gets()读取一个字符串，必须在gets()之前用getchar()把上一行的 \n 读去
　　　　　2. 如果使用 getchar() 读取字符，一定在末尾加 '\0'

5. 神器：sscanf, sprintf
sscanf(sceen, "%d lf", &n, &d);　// 默认是以键盘作为标准输入
sprintf(sceen, "%d lf", n, d);　　// 默认是以显示器作为标准输出
sscanf(str, "%d lf", &n, &d);    /将str当做是标准输入（屏幕），从str中读取数据，即将数据保存在各种非字符串的变量中，实现了字符串向非字符串的转换
printf(str, "%d lf", n, d);        //将str当做是标准输出（屏幕），将数据输出到str中，即将数据保存在字符串str中，实现了非字符串向字符串的转换

　　注意：（str必须是字符数组，不能是string）

6. freopen("in.txt", "r", stdin)重定向输入，将输入从键盘重定向到文件，把输入数据放到文件中，这样测试数据十分方便，而且这个函数使用十分简单，不用去了解复杂的文件输入输出方面的知识。

　　注意：(1). return 0前最好关闭重定向：fclose(stdin);

　　　　　(2) 提交代码时必须去掉freopen()和fclose()， 因为测试机器是默认要求从键盘读取输入数据的

7. 高精度浮点数的比较 （利用宏定义）
const double eqs = 1e-8;
const double PI = acos(-1.0);

#define QUE(a, b) ((fabs((a) - (b))) < (eps))
#define MORE(a, b) (((a) - (b)) > (eps))
#define LESS(a, b) (((a) - (b)) < (-eps))
#define MORE_EQU(a, b) (((a) - (b)) > (-eps))
#define LESS_EQU(a, b) (((a) - (b)) < (eps))

8. 字符串反转，std::reverse(str, str + n)-->这个函数是C++特有的，必须加上<algorithm>和命名空间std

9. 用vector<node>Adj[N]代替邻接表存储图

10. 数组的初始化 memset(void * s, int c, size_t n)函数 和 fill() 函数
    memset()是按字节赋值，所以第三个参数是字节个数，对于字符数组可以初始化为任意字符，如果是整形int数组只能初始化为0,初始化为其他数字会出错，还可以初始化bool数组，可以将布尔数组初始化为true或false
    fill(a, a + n,  x);    将数组a 从 （0 - n）范围内的元素置位x, 按数据类型赋值，所以可以对任何数组赋予任何符合数组类型元素的值。包含在algorithm.h头文件中，但是速度比memset慢。

　　使用方式：

bool vis[maxn] = {false};      //重新初始化vis为false可以用
memset(vis, false, sizeof(vis));    //也可以用fill(vis, vis + maxn, false)

11. 二分法
12. two pointers
13. 求最大公约数的函数

int gcd(int a, int b){
    return !b ? a : gcd(b, a %b);
}

14. 求a 和 b的最小公倍数公式 a * b / gcd(a, b)

15. algorithm头文件中一些很有用的函数：
　　(1) swap(a, b) 交换两个变量的值
　　(2) reverse(a, a + 4) ; a 是一个数组或STL容器的迭代器，该函数可以是数组区间或迭代器区间的元素反转
 　   (3) max(a, b) ,min(a, b), abs(a)三个函数分别求最大值，最小值，绝对值
　　(4) sort()函数，使用非常方便，可以根据不同的情况自动使用不同的排序方式，效率较高，使用时必须加上<algorithm>头文件和using namespace std命名空间
　　　　用法：sort(首元素地址（必填）， 尾元素地址的下一个地址（必填）， 比较函数（非必填））
　　　　如：sort(a, a + 4, cmp) 或 sort(a.begin(), a.end(), cmp)
　　(5) next_permutation()函数，给出一个序列在全排列中的下一个序列，返回值是一个bool值，如果还有排列尚未枚举则返回true, 否则返回false
　　(6) fill()函数: 将数组初始化为某个值，可以是任意数字，包含在algorithm.h头文件中，但是速度比memset慢
　　(7) lower_bound()和upper_bound()函数
　　    这两个函数必须用在一个有序数组或容器中，lower_bound(first, last, val)返回容器或数组在[first, last）范围内第一个大于等于val的元素的位置指针或迭代器；upper_bound(first, last, val)返回容器或数组　　在[first, last)范围内第一个大于val的元素的位置指针或迭代器。
   　　 如过数组或容器总没有需要寻找的元素，则两个函数君返回可以插入该元素的位置的指针或迭代器（即假设存在该位置时，该元素应当在的位置）。

这篇关于必备算法技巧 -- 掌握这些可以成倍提高写算法题的效率的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！