当前位置: 首页 > article >正文

算法题刷题方法记录(蓝桥杯、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:

  1. 如果百分数小数位小于0.5,+0.5之后小数位小于1,int保留整数位,实现4舍

  2. 如果百分数小数位大于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::cinstd::cout 等)与 C 标准输入输出流(stdinstdout 等)的同步。当参数为 false(零值)时,会取消同步,这样可以提高 std::cinstd::cout 的读写速度。不过,取消同步后,就不能再混用 C 和 C++ 的输入输出函数了。

if (is_file) {freopen("xxx.in","r",stdin); freopen("xxx.out","w",stdout);}:

重定向输入和输出,输入从xxx.in文件读取,输出到xxx.out文件。

dp

动态规划,换硬币哦、01 背包、完全背包、Leetcode343.整数拆分、LeetCode474. 一和零。

关键是状态转移方程

贪心是局部直接选择最优,不需要根据之前的状态来推导,与之前的状态无关

动态规划的关键解题思路:

  1. 定义dp[i]或者dp[i][j]的含义

  2. 分析转移的过程,用笔打草稿(举例模拟),心中有数

  3. 初始化已知状态,以及其他未知状态

  4. 调试的时候打印dp数组

新的一个题型:LeetCode474. 一和零:

  1. 开始的时候总想着使用二维dp来做,发现横轴没办法同时处理1和0数量

  2. 然后就看题解,定义了dp[i][j][k]的含义,建立状态转移方程

  3. 类比背包问题,发现是背包的限制条件有两个

新的一种初始化方法,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,也就是在树上搜索最佳解决方案,需要先了解三种遍历方式

第一次遇到这类题型的时候,完全不知道怎么下手,因为确定遍历方式就很困难,不知道怎么选用遍历方式(看题解写完了也没有太理解>﹏<

重新理解动态规划的三部曲!


http://www.kler.cn/a/588060.html

相关文章:

  • Spring MVC拦截器中的责任链模式深度解析
  • 深度探索DeepSeek部署的安全底线
  • 第十五届蓝桥杯大赛软件赛省赛Python 大学 C 组题目试做(上)
  • vulnhub-Hackme-隧道建立、SQL注入、详细解题、思路清晰。
  • CSS:使用内边距时,解决宽随之改变问题
  • C#通过API接口返回流式响应内容---SSE方式
  • rk3568 yt8521S phy设备层丢包定位处理
  • Smart Time Plus smarttimeplus-MySQLConnection SQL注入漏洞(CVE-2024-53544)
  • 链表题目2(leetcode24题)交换链表里面的节点
  • Flutter FloatingActionButton 从核心用法到高级定制
  • 从LLM出发:由浅入深探索AI开发的全流程与简单实践(全文3w字)
  • ElasticSearch组合查询及实际应用
  • python unity通讯数据解析2
  • WindowsPE文件格式入门01.PE头
  • [Windows] OfficeScrubber_13--office卸载清理工具
  • 【JavaEE】快速上手JSON:构建高效 Java 后端数据桥梁,开启交互新篇,以 @RequestBody 为引的探索之旅
  • 类和对象C++ (未完:对象特征)
  • linux - 基础IO之操作与文件描述符全解析:从C语言到系统调用底层实现
  • python爬虫Scrapy(5)之增量式
  • 生物角度分析