算法题刷题方法记录（蓝桥杯、Leetcode）
Algorithm exercises
尘封已久的算法，又要重新开始刷题了，不知道题量能不能达到预期
研一寒假期间，断断续续的，平均下来大概每天一题，懒懒散散的，开学来了继续刷。
记录下让人眼前一新的算法题
喜欢就要勇敢去爱，对一件事，对一个人，如何付出，如何去追求，如何去爱，在付出的的过程中又如何去确定自己的内心？在追求一个目标或者一个人的时候，如何确保自己在付出的时候也是开心的？ ^_^
加油<(￣︶￣)↗[GO!]
持续学习中：Algorithm-exercises Github, 欢迎Star ^o^y
isPrime
判断质数，仅仅使用了sqrt，没有使用欧拉筛法、埃拉托斯特尼(Eratosthenes)筛法（记不住O(∩_∩)O哈哈~
bigInt
大数的计算模板，重载运算符
qpow
快速求幂的方法：递归的方式，时间复杂度是O(logn)
bfs
广度优先搜索（广搜）：在图中找一条最短路径、扫雷
dfs
深度优先搜索（递归，还可以dfs转bfs！
rounding
将得到的百分数四舍五入。
利用int来保存最终结果，将得到的百分数+0.5：
-
如果百分数小数位小于0.5，+0.5之后小数位小于1，int保留整数位，实现4舍
-
如果百分数小数位大于0.5，+0.5之后小数位大于1，整数位+1，int再保留整数位，实现5入
bigWhileTLE
一般的计算机每秒可执行约 108∼109 次运算，而 10^18 级别的循环需要的时间是不可接受的。
所以得控制好while循环的次数，如果次数太大，会超时。
model
算法题模板，在solve函数中写题，rep、all、SZ、ll这些比较常用。
ios::sync_with_stdio(0):
std::ios::sync_with_stdio 是一个静态成员函数，用于控制 C++ 标准输入输出流（std::cin、std::cout 等）与 C 标准输入输出流（stdin、stdout 等）的同步。当参数为 false（零值）时，会取消同步，这样可以提高 std::cin 和 std::cout 的读写速度。不过，取消同步后，就不能再混用 C 和 C++ 的输入输出函数了。
if (is_file) {freopen("xxx.in","r",stdin); freopen("xxx.out","w",stdout);}:
重定向输入和输出，输入从xxx.in文件读取，输出到xxx.out文件。
dp
动态规划，换硬币哦、01 背包、完全背包、Leetcode343.整数拆分、LeetCode474. 一和零。
关键是状态转移方程
贪心是局部直接选择最优，不需要根据之前的状态来推导，与之前的状态无关
动态规划的关键解题思路：
-
定义
dp[i]或者dp[i][j]的含义 -
分析转移的过程，用笔打草稿（举例模拟），心中有数
-
初始化已知状态，以及其他未知状态
-
调试的时候打印
dp数组
新的一个题型：LeetCode474. 一和零：
-
开始的时候总想着使用二维
dp来做，发现横轴没办法同时处理1和0数量 -
然后就看题解，定义了
dp[i][j][k]的含义，建立状态转移方程 -
类比背包问题，发现是背包的限制条件有两个
新的一种初始化方法，LeetCode322. 零钱兑换，总结经典题目分类与初始化方式：
| 题目类型 | 题目 | DP 数组初始化方式 |
|---|---|---|
| 计数问题 | 组合总数、排列总数 | dp[0] = 1，其余 0 |
| 可行性问题 | 01 背包是否可行 | dp[0] = 1，其余 0 |
| 最短路径问题 | 最少硬币问题 | dp[0] = 0，其余 INT_MAX |
| 最长路径问题 | 最长上升子序列 | dp[i] = 1 |
| 最大值问题 | 01 背包求最大价值 | dp[0] = 0，其余 -∞ |
treeDP
树形DP，也就是在树上搜索最佳解决方案，需要先了解三种遍历方式
第一次遇到这类题型的时候，完全不知道怎么下手，因为确定遍历方式就很困难，不知道怎么选用遍历方式（看题解写完了也没有太理解＞﹏＜
重新理解动态规划的三部曲!