Just for Life.

寒气逼人的惨淡秋招终于 tnnd 的结束了，4月中旬开始投递，10月中旬拿到 offer，耗时6个月。就业形式异常艰难，简历挂，笔试挂，面试挂，感谢信收割机。一种被累垮的感觉。

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

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

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

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

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

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

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

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