算法题刷题方法记录(蓝桥杯、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,也就是在树上搜索最佳解决方案,需要先了解三种遍历方式
第一次遇到这类题型的时候,完全不知道怎么下手,因为确定遍历方式就很困难,不知道怎么选用遍历方式(看题解写完了也没有太理解>﹏<
重新理解动态规划的三部曲!