Just for Life.

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

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

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

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

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

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

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

听到滑动窗口这个词，让我想起了计算机网络中的 TCP 传输和拥塞控制，可惜时隔多年还给老师了，那老师讲课还很不错。我的大部分本科老师都有着很多年的工作经验，并不像部分硕博留校那种只擅长验证玩具理论和咬文嚼字，而从未到实际环境中实习过一次。所以他们讲课十分形象具体，结合理论和实际环境告诉你这是个什么东西。

说远了，回到正题。滑动窗口一般用于求接子串中满足某种情况的最值，可以简单的划分为三类：

1. 给一个字符串，求满足条件的最长子串
2. 给两个字符串，求其中一个字符串是否能覆盖另一个字符串
3. 给定一个数组和窗口大小，窗口没滑动一次，求一次最值

今晚翻了一下 todo list，发现这个条目堆积在未完成列表的末尾，于是来学习一下 C++ 中的四种类型转化方式，而 C++ 的复习也告一段落。我知道我还差得很远，等某天 C++ 功底足够深厚，来写一下 C++ 的内存模型。