0%

上一次正儿八经写博客是今年 2 月,5 月做了个比赛总结,其余的博客竟然都是刷题和算法,实属无聊。艰难的日子已经过去,准备学点模型部署相关的东西以及参与一个实际的开源项目,争取数据、算法和工程全链路打通。众所周知,对于一个不是很常用的东西,学完就忘,如 spark, Go 等学过的但很少用的东西,已经被我抛到九霄云外了。所以,这次学完模型的 trace 之后,尝试部署一些能实际运行的软件。

这几天接连遇到了一些双指针的问题,但是说实话,并没有从这些题中看到一种通用的东西,也就不是能很好的做一个总结,但不得不说双指针是一个很神奇的东西,所以做一道记一道吧。

闲来无事,在面经上看到了一个问题:在物理机只有 1G 内存的情况下,能否 malloc 出 4G 大小的数组。奇怪的是,这个问题在网上搜不到特别好的解答,于是突发奇想试着解答一下。

本文集中写链表的反转问题,因为其他的链表相交、链表数量等问题比较简单,即使没啥算法经验也能写个差不多,而链表反转也算一种经典的递归问题。这个文章的文字描述太乱了,有时间回来补图。

主要收录深度优先遍历和宽度优先遍历,深度优先遍历一般可以与回溯、递归、树等方法联用,达到优雅遍历的效果,而宽度优先搜索可以用到最短路问题的求解中。

  • 为什么不用 bfs 去遍历?第一是因为 bfs 写起来麻烦,不如 dfs 直观。第二是在某些查找到满足情况即可退出的应用而言,bfs 需要一层一层的去检查,效率很低。
  • 为什么不用 dfs 去求最短路?如上所示,bfs 可以一层一层的检查,相对 dfs 更容易查到最短路。

回溯算法是一种暴力枚举的算法。但是,枚举是一个技术活,枚举过程如何保证不重复、剪纸、不遗漏和优先处理可能的结果,这并不简单。

回溯应该是算法系列中除动态规划外最难的一个,需要很好的明确回溯入口,退出条件,两者保证回溯的不遗漏。而下一步如何回溯,以及如何退出当前状态要保证回溯的不重复。也许有些抽象,我们来看具体例子。

之前从未意识到位运算的强大威力,认为与或非只存在大一 C 语言的考试或单片机的设计中,直到今天才发现我错了。做一个常用的位运算和数学运算的整理。