CodeEveryday

每天在力扣上面的刷题记录，大概是每天三道题的样子，包括同专题的两道简单＋一道中等或困难，以后会逐渐增加难度的！前期刷题代码库当中可能还是会有参考样例吧，因为先是模仿然后再产出。

4/14 二叉树 1 & 双指针

今天是第一天，做了三道二叉树的题，好想一天做很多题，因为自己不会的东西真的太多了。积少成多，每天就算只做几道题做几个月也能将基本知识全部掌握。

P124 二叉树的最长路径（困难）

这道题做了好久，最后参考了题解，学会了怎么用 MAXINT 进行做题，类似的想法可以从求二叉树的最值元素当中引申出来。

本质是自底而上！在更新顶部的 result 的时候底部的 result 就已经被更新过了，所以全局变量 result 就完成了维持 result 的过程。

晚上没事做，又做了几道双指针的题。

P15 三数和（中等）

学会了双指针，一遍过，两个 90％。感觉是很神奇的方法，符合直觉并且真的是对的，本质上是一个二叉树的结构，有：

graph LR
1,n-->1,n-1-->1,n-2
1,n-1-->2,n-1
1,n-->2,n-->2,n-1
2,n-->3,n

P16 最近的三数和（中等）

一样的方法，不过需要变通一下，学一下题解看看怎么优化时间，用时有点长，不过内存还 ok。哦原来是有个判断放错地方了，多了一个 $O(n)$ 的判断时间，修改之后已经 96% 了，真不错。

P18 四数和（困难）

和三数和差不多，但是其实要简单一点。不过坑是真的多，自闭了有点。

（4/15 更新：其实用递归就行了，昨天头疼没想清楚，今天想明白了，对于任意的 $k$ 可以通过双指针 + 递归的方式实现 $O(n^{k-1})$ 的复杂度。那么可以做得更好吗？有空查阅相关信息）

4/15 树状数组 1

今天看到了这一个特殊的结构，打算把该专题下的 6 道题目全部做完，加油加油。（晚上更新，今天事情太多了，不过认真学会了，不过明天一定好好学！今天全是课 TAT，而且这个优美的结构比较难，得花点时间学。

P307 区域和检索 - 数组可修改（中等）

我用前缀和做的，太慢了。然后认真学习了树状数组的知识。实际上就是树状数组的直接运用。

P493 逆序对（困难）

这道题之前做过，用递归可以做。用树状数组做逆序对也是一个很经典的方法，一步一步填进去，然后通过计算部分和进行比较就可以知道逆序对了。用树状数组也是一种方法，类似于应付普通的逆序对，往一个底层数组填进去 2 就行，然后读取部分和——也就是逆序对数了。不过这道题还有一些小技巧，离散化之类的。

4/16 学习 Golang 以及复习

今天复习期中去了，打算明天把树状数组剩下的几道题都做完。另外今天决定使用美国版的力扣了，中文网实在太卡……另外美国版使用 UTC 计时，就不会像今天这样过了零点了，比较符合作息时间。

4/17 树状数组 2& 正则表达式学习

今天认真学习正则表达式的语法，学习笔记放在了仓库根目录下面。今天逛了逛各大厂实习的招聘，越来越感觉自己要学的东西还有好多好多，就投了个小米的 Golang，所以等通知这些天还是要用 Golang 把题目刷好！今天认真学习的题就只有以下的：

P218 天际线（困难）

这道题可以用希尔伯特形容费马大定理的一句话来形容——“会下金蛋的母鸡”，通过这一道题能够学会两种数据结构，分别是树状数组、线段树，还有扫描线算法。同时在其中也了解到了“离散化”的概念。下面简单对于这道题的不同做法做一个剖析：

线段树

我们将横坐标离散化之后建立线段树，然后对于每个楼的横向区间进行 Add() 操作，建立这样的线段树之后再从左至右历遍这棵树的叶子节点（也就是底层线段）看每一段的 Value，也就是区间的最大值，就可以得出来所需要的 Skyline 了。

扫描线算法

同样需要对横坐标进行离散化，之后考虑扫描线从左至右不断地前进，或者更通俗地说，我们可以想想一个人在 Skyline 上面奔跑的过程来理解，可以发现实际上我们这样一种前进的过程需要维护的就是我们脚底下的楼房集合，同时我们的 Skyline 就是这些楼房的最高点，也就是脚踩的地方。注意用来存储这个楼房最高点的数据结构应该同时很好地支持元素增减，所以最大堆不是很合适，我们使用二叉搜索树的结构就好了。

树状数组

不像线段树，我们可以直接读取每一步当前小区间的 Value，所以没有办法向线段树一样走一步看一步（即每次都 QuerySegTree(i,i+1)）直接求出 Skyline，所以我们需要换一种思路。

虽然看起来树状数组的做法和线段树类似，但实际上完全不一样，树状数组的思路是：我们在从左至右的过程中逐步建树，这样遇到边界的时候，我们如何判断是否需要变化高度呢？关键就在于“一边建树一边从左至右”的顺序了，由于树状数组底层支持的是单点查询，如果我们用 QueryBIT(i+1) 表示查询当前（这一点非常重要！因为在建树的过程中会不断刷新树状数组，请记住这个修饰词）的 $\max[1,i]$，那么会发现根本没有办法判断是否应该变化高度！这是为什么呢？原因是此时你会发现 QueryBIT(i+1) 没有任何意义，因为他只能代表过去的最高楼，而不能给当前是否应该变化高度带来任何信息（可能有人会想到存在一个问题，我们需要录入楼房的信息，这实际上是需要我们区间修改；但是在维持最值的树状数组里区间修改并不能使用差分数列的技巧）即使我们可以完成维护，我们也会发现树状数组对这道题的作用和线段树的作用完全不一样。

那么我们应该怎么办呢？@halfrost 神之一手，把 QueryBIT(i) 的意义改成了 $\max[i,+\infty)$，这看起来并没有什么特别的，但是整个意义对于当前来讲非常重要，因为这个时候我们会发现，查询 QueryBIT(i+1) 的时候真正是关注此时此刻的信息，为什么？因为在之后的高楼根本还没有录入！

这一段解释我想了数个小时，@halfrost 本人可能能够知道自己的算法是怎么处理的，但是他在自己题解上的解释却让我更加困惑了，他说：

最大值既然难以“去除”，那么需要考虑如何让最大值“来的晚一点”。解决办法是将 Query() 操作含义从前缀含义改成后缀含义。Query(i) 查询区间是 $[1,i]$，现在查询区间变成 $[i,+\infty) $。例如：$[i,j]$ 区间内最值是 $\max [i,j]$，Query(j+1) 的结果不会包含 $\max[i,j]$ ，因为它查询的区间是 $[j+1,+\infty)$ 。这样更改以后，可以有效避免前驱高楼对后面楼的累积 max() 最值的影响。

将前一种方法的失效归因于“最大值难以去除”（这一点也算说的对），于是就要使用后一种方法来”让最大值来的晚一点”，这个解释就有些不知所云了，似乎指的是延迟更新树状数组的结构？但显然不是这样。“例如”后面的解释更加让人有点不明白了，因为在这道题当中不会涉及到 $\max[i,j]$ 这一个区间查询的操作，可能他只是想用这个例子来说明后面那句话：“这样更改以后，可以有效避免前驱高楼对后面楼的累积最值的影响”。是的，我们不想要累计信息，我们需要当前的信息，但是他的说法似乎在说要将“前驱高楼”和“后面楼的累计最值”，如果没有理解的人比如说前几个小时的我，就会把这里的“累计最值”仍然看成是前一种方法的 QueryBIT() 方法，但是这是自相矛盾的，因为这个累计最值本来就自然会包含前驱高楼的信息，所以才会让人很困惑。

说到底，这种困惑造成的原因是这些解释将问题矛盾归结于“前驱高楼”和“累计最值的矛盾”，但实际上矛盾的两个主体为“当前的点最值”和“累计最值的矛盾”：我们希望从累计信息当中得到点信息，但是没有相减操作的我们没法完成这样的信息推理，那么怎么办呢？让他们两个是同一个东西就好了。这才是这个问题使用树状数组的关键所在。

总结

这道题非常值得深入地思考，特别是树状数组解题的相关部分。注意线段树不同于其他两种做法，它虽然看似在线生成一个 Skyline，但实际上还是离线生成一个线段树然后在这个树上求解出答案的离线算法，这一点可以从这两者的可分离性看出来，这也是树状数组做法和线段树做法让人感觉到相似但不同的原因所在（或者说，本质还是维护最值的树状数组没有办法进行小区间查询，它只有形如 $(x-\mathop{\text{lowbit}}(x)]$ 的信息）。

4/18 哈希表

今天考一门期中考没有考好，下午休息了一会重新调整好了，下半学期努力:face_with_head_bandage:！今天做哈希表相关的题目，并在做题的过程中体会这种数据结构的本质和使用方法。从今天开始我打算详细地写自己做题的过程，这样更有收获，不过花的时间更多，希望能够找到平衡点吧。（4/19）感觉自己写东西有些啰嗦，还是要简洁一点。

P3 最大无重复子序列（中等）

自己的解法：记录最后一次出现的指标

感觉很简单！我们用贪婪的算法，考虑一个“窗口” s 从左出发向右前进，遇到了 s 没有的元素 'a' 就 append(s,'a')，如果遇到了存在的元素 'a' 就将这个字节原来所在位置之前的全部减去，然后将新遇到的添加到 s 当中，然后我们再维护最大长度就行了。

那么问题就在用什么去动态存储 s 呢？需要满足以下几个方法：

能够完成删去 s 开头的一段的操作
能够获取 s 的长度
能够添加新元素
能够很快地查找一个元素

看到后两条似乎要用哈希表了（当然确实要用），但是前两个怎么处理呢？我们可以用抽象的办法去完成前两个操作，也就是不实际上存储 s，只用两个端点：

维护一个 LeftIndex 表示 s 此时的左端点，右端点不需要存储，这是由于 s 的右端点就是当前读取到的 index 减 1，这样我们就可以动态地获取 s 的长度了，当然你可以选择直接维护 s 的长度。
维护一个哈希表 H[x]=LastIndex(x)，这里的 LastIndex(x) 函数表示 x 最后一次出现的 index，那么每次我们读取到 InputS[index]，那么 H[InputS[index]] 就应当更新为 index。

但是这里有个问题，如果 InputS[index] 当中存储的位置已经不在 s 当中了，那么我们实际上不应该更新 s 的长度。当然这个非常好解决，我们只需要判断 LeftIndex <= H[InputS[index]] 是否成立就可以了，如果成立才更新。另外还有一个小问题，如果用 H[x] 存储的是 index 的原始值，在实际操作的时候，它会被初始化为 0，在循环中会被认为是对于任意的 x，它一开始都在字符串的第 0 位出现，这会导致我们的代码不简洁，此时我们只要将 H[x] 的意义加一就可以避免这种情况。

题解：记录出现在窗口内的频率

关于判断字符是否出现在窗口内，题解使用了另外一种方法，也就是使用数组 freq[x] 记录元素在窗口内的次数，这种记录方式将“窗口”的存在感增加了，也就是实际存储了窗口，而我想的更加抽象一点；另外一方面，就本题而言，使用 freq[] 在移动左窗口的时候是一步一步移动的，会比我的做法慢一点。

P992 K 个不同字符的子字符串（困难）

这道题还是用上一道题类似的“窗口”想法，维护一个有 k 个不同值的窗口。注意这题要把计算答案和移动窗口分开，移动窗口要更加懒惰一些。有以下两种做法（这道题类似于上一题，用两种记录元素的方式都哦可以）：

维护三个指针

这种做法就是窗口的自然推广，注意我们如果遇到了一个元素，我们就需要读取一个窗口中间的指针，这个指针指向第一个窗口移动到此处后一个位置就会使得窗口内元素类减 1 的位置 Mid（其实也可以不存，每次构造一个左指针的副本向右移动到元素内减一，但是这样的话会浪费很多时间），我们需要利用它去完成两个事情：

计算答案
移动左指针，维护窗口

那么我们的流程表就出来了，通过解耦和优化可以变得比较简洁。维护完指针之后我们就可以进行计算答案了，当且仅当现在窗口内有 k 种元素就让 res+=Mid-Left+1 即可。

分解题目

这种做法本质上和上一种做法没有什么不同（想想为什么）：将题目答案考虑成两个问题的差，即最多出现 k+1 种和最多出现 k 种的子串个数之差，这样的话（对于单个）问题就不需要维护中间那个指针。

4/19 线段树

今天要准备复习离散数学了，可能做的题没有那么难，还要花时间学学 Golang 怎么写 web 应用。今天的知识点是线段树，主要目标是实操怎么写线段树。

P303 区域和检索 - 数组不可修改（简单）

这道题是简单题，主要用来练习怎么写线段树，代码库中放的是前缀和的写法。似乎这道题的算排名和运气有关。

P699 掉落的正方形（困难）

这题真的和天际线好像啊，直接用维护最大值的线段树应该就行了。先离散化之后，之后每一步先查询区间然后再区间更新，注意维护全局最大值。

P715 范围模块（困难）

二叉查找树想法

这道题用线段树当然可以做，但是真的太慢。用二叉查找树是最优的解法，这是由于“存在”的这个状态并不像“维持最值”一样需要数据结构一直存储每个小线段的状态，前者完全可以用是否在“数据结构”中存在来验证，这也就说明我们完全不需要对所有的线段进行存储，而是只需要存储确实被查询到的线段就可以了（其实我觉得这道题真的就是样例的问题，如果样例使得二叉树也很大，和线段树的大小差不多，那就两个算法差距没那么大了）。

大概思路是用一个 BST 存储一段一段的线段（它们不会相交）

每次 Add() 或 Remove() 一个线段 [a, b] 的时候我们就把其放到 BST[] 当中进行搜索，遇到了 [c, d]：
- 如果 b<c||a>d，则将 [a, b] 放到 [c, d] 的左（右）边继续查找；
- 若两个区间有交：
  - 若新来的区间被包含：
    - 若是 Add() 操作，则什么也不做；
    - 若是 Remove() 操作，则将 [c, d] 拆分为两个，并在原有位置上产生一个特殊的 EMPTY 节点，他只是表示一个位置。并把拆分而来的两个小区间变成这个空节点的两个儿子节点。
  - 若新来的区间未被包含，假设 a<c，另一边类似：
    - 若为 Add() 操作，那么我们观察新区间是否和左儿子有交，若和左儿子有交，说明左儿子和 [a, b] 中间的节点，也就是左儿子右子树的那些节点都被覆盖了，我们就应该将左儿子和当前节点合并，事实上我们此时需要递归，搜索到第一个有交但不被 [a, b] 完全覆盖的左儿子，然后把其左子树变为合并后的顶点的左子树；
    - 若为 Remove() 操作，我们同样需要观察和左儿子是否有交，递归搜索到第一个有交但不被 [a, b] 完全覆盖的左儿子，将其变为 [c, d] 的左儿子，然后删去其右子树。

如果我们这样做的话就会发现对于查询来说非常友好，但是对添加和删除需要我们去进行递归删除节点，否则会内存泄漏。

我们能不能懒惰一点呢？我经过一个小时的讨论没有想到什么好的讨论办法能够使得查询返回正确的结果的，同时如果不合并重复的区间，整个数据结构就会冗余到一团糟，这不是一个很好的现象。

学习题解以及分析

题解的方法有一个值得注意的地方：其实我们不需要完成合并的操作，只需要在递归下去操作的时候截断一下就好了，这样虽然空间会多一些，但是实际上空间已经 100% 了，所以没什么好节省的，但是速度可以大大提升，因为不需要考虑泄露的问题。

事实证明，二叉查找树会比线段树快整整 6-7 倍。LeetCode 上面速度最快的题解居然是用有序列表存储这些线段：我们记二叉查找树的高度为 $h$，记列表的长度为 $l$，我们假设每种操作（增加和删除）和查询的数量分别为 $m,n$：注意 $h=O(\alpha \log m)$ （只有增加会添加树的结点数，删除有可能不减少树的结点数），$l=O(\beta(m+n))$ （增加可能会减少树的节点数，如果这种减少的比较多，常数会大大减小），所以我们得到：

数据结构	时间复杂度	空间复杂度
二叉查找树	$(m+n)O(h)$	$O(2^h)$
有序列表	$mO(l)+nO(\log l)$	$O(l)$
线段树	$(m+n)O(\log (m+n))$	$O(m+n)$

我猜测之所以有序列表很快是因为检测例子使得如果我们维护不交的线段组成的数据结构，这个数据结构当中的结点个数虽然也是 $O(m+n)$，但是其常数却很小。

明天想学红黑树啥的。今天真的花了好多时间，感觉以后不可以这样了，一天花在代码上的时间不能超过 2 小时。

4/20 休息一天，期中复习

今天休息一天，主要是需要复习明天的考试，今天任务就是继续学习 Golang 教程的第 15 章同时复习一下 Python 的基本方法，过些天还得复习 Pandas 啥的，为了面试做准备。原来明天中科院推研就结束了，今天也没有时间学了，顺延一天。

P1840 最高建筑物高度（困难）

本质是为了要找到每个被限制的建筑“真正”被限制到了什么高度。当然有一个暴力的做法，是 $O(n)$ 的，但是这显然不好。我们就要想怎么去做这件事情。如果我们每次都对最低的那个限制考虑其周围的限制建筑，那么就可以了，关键是要维持住最值结构，显然就要使用堆。注意剪枝，已经操作过的限制建筑无需再操作。实际操作上，我们 push() 被修剪过的限制，这个限制比原来要小，所以会先出队列，所以不用担心会有非真实限制的建筑进行修剪。

4/21 学习 Golang 以及调整心态

今天离散数学考的不是很好，简单的题目没做出来，导致一天心情都很差，然后还有保研的事情也没有弄好，今天调整心态吧。另外今天还做了一个很有趣的事，把大一上的程设期末复盘了一下，虽然都是很简单的题，但是当时真的考的很不好，也算是一种破除心魔的感觉吧，直面过去的失败，是为了今后变强。

今天继续学了学怎么写前端，明天继续努力。

4/22 學習數據結構：高級的樹結構（参考）

TREAP 樹

TREAP 树是一种由搜索二叉树和堆组合产生的数据结构，在二叉树的结点基础上添加一个叫做 priority 的字段，并且按照 priority 进行堆的性质排序，这两者是可兼容的，并且产生的数据结构会期望平衡，也被称作 弱平衡。

無旋 TREAP 树

無旋 TREAP 树支持两种操作，分裂 (split) 以及合并 (merge)。

分裂接受两个参数：关键值 key 以及根指针 root，将一个 TREAP 树从 key 的位置分裂开来；合并接受两个参数：左 TERAP 树根指针 u 和右 TREAP 树指针 v，并且满足左树的 priority 值小于等于右子树的 priority 值，利用递归合并即可。

有旋 TREAP 树

旋转 TREAP 树分为左旋和右旋，为插入的时候进行旋转方向的修饰。

Splay 树

规定每次插入一个结点，都需要将新结点旋转到根结点的二叉查找树。其支持重要操作即 Splay 操作和合并操作。

AVL 树

在更新的时候通过旋转维护左右两边子树的高度（需要存储的字段）。如下图所示（分别为根据 A C 两点子树深度的不同情况）：

可以参考演示网站

替罪羊树（参考）

替罪羊树 (Scapegoat Tree) 从一个简单的想法引申而来，即控制左右子树的大小 (node.left.size, node.right.size) 的比值 $\alpha$ 在一个范围之内。$\alpha=1$ 的情况就是极端的、绝对平衡的二叉树；$\alpha=\infty$ 的时候就是没有任何限制。

替罪羊树的想法很简单，其他操作都和一般的二叉树一样，只是在涉及到插入以及删除的时候有一些小变化：

插入

在插入的时候我们考虑插入路径上的点，如果不平衡了我们就需要重构操作。

删除

在删除的时候我们采取懒惰的方式，如果删除一个顶点，我们就给他打上标记，以后调用的时候直接跳过即可；在重构的时候需要将删除过的节点清除。如果树中被标记的坏顶点过多也需要重构树。

笛卡尔树

笛卡尔树实际上就是同时满足二叉查找树和堆的树，其实就是 TREAP 啦，不过 TREAP 其实是为了保存 key 强行随机构造了 priority 而已。可以证明笛卡尔树唯一。

栈构建

将元素排序，然后从右链一个个插入，这种栈的构造方式，为 $O(n)$ 复杂度的。

跳表

构造一个随机的至多 MAXLEVEL 层（一般为 32 层）的链表，使得最底层的链表是有序列表，并且每一个底层的元素以一个固定的概率 $p$ 出现在顶上一层，那么我们在搜索 a 的时候就可以通过从顶上搜索到最大的小于 a 的元素之后变到下一层继续进行搜索。可以证明空间复杂度是 $O(n)$ 的，同时查询等操作都是 $O(\log n)$ 的。

做一道跳表的题作为最后结尾吧。

P1206 设计跳表（困难）

没什么好说的x 就是构造一个跳表。

4/23 并查集

相比于其他复杂的数据结构，并查集并没有复杂的结构，同时也拥有着优秀的时间和空间复杂度，代价是能做的事局限于查询（祖先、或者说是所在分组）和合并等基础操作。

P128 最长连续序列（中等）

并查集思想的运用，实际上对于这种能够合并的（在此题当中是同一段线段）我们都可以考虑使用并查集的结构。在这道题中，我们就只需要统计祖先（线段的右端点）的长度，统计长度就回推就好了。我们还可以使用压缩路径等方式使得空间复杂度和时间复杂度进一步降低。

P721 账号合并（中等）

这道题看似想法很简单，但是实施起来不太容易，要写好更不容易。这道题的想法是将每个邮箱账号分组，并将其和“直接分组”也就是第一次出现这个邮箱账号时候的对应的分组绑定，之后如果出现在别的分组当中我们就将那个分组和这个直接分组进行 Union() 操作。注意我们使用并查集的数据不是邮箱账号，而是分组 group 结构。

这道题中还涉及到一个技巧，在 Golang 当中可以使用 map 结构键值唯一性来构造 Python 当中的 Set 数据结构。

P765 牵手情侣（困难）

？这道题和并查集什么关系，直接一步一步将第一个元素配对递归（可以完全不用递归写）配对就好了，@halfrost 的题解说这道题将情侣看成并查集，那么答案就是对于相邻两两元素 Union() 的次数，其实没有必要。

4/24 栈

数据结构其实都学的差不多了，接下来的练习都是巩固，所以接下来有以下的几点要求：

每日挑战一定要做
尝试使用 Python 写题，用来复习
每日坚持练习新的和困难的知识点

P71 简化路径（中等）

真的好简单，构造目录的栈就行。

P42 捕获雨水（困难）

考虑维持高度的栈，栈顶的高度最低，一旦弹出就计算累计的雨水，相当于把雨水从横向的角度一层一层分解，不同于竖向的分解，分解为竖向的时候我们比较难判断这个地方的高度是多少，这样非常慢。

P726 原子个数（困难）

数括号！经典的栈运用！

4/25 复习 Python

今天初步复习 Python 的相关知识，相关的代码在另外一个库当中更新，参考书是《Python 编程：从入门到实践》，是一本比较简单的入门书，明天有空会看《Python 学习手册》真正复习好怎么用 Python 写程序。

4/26 复习 Python

今天把《Python 编程：从入门到实践》看完了，比想象的要看得久，主要是当初看第一遍的时候没有看后面利用 Django 构建 web 应用的部分，所以今天花了很多时间在这个上面，明天应该就恢复正常的每日做题了。

4/27 回溯

从今天开始，可能我会将每日挑战我觉得有意思的题目写一写感想，但是不管写不写我都会把相应代码放到本仓库的 DailyChallenge 文件夹中。

P1202 最小交换字符串（中等）

这道题最主要的就是认清楚一个简单的事实：只要两个位置通过若干个 swap 操作连通，则我们就可以将他们两者交换，那么问题显然就转化为了一个并查集的问题，但我们需要读取一个分类里面的所有的 index，再注意我们是要对 index 进行构建并查集，他们的范围是 1 - len(str)，从而我们可以用数组的方式构建一个双向的字典，然后解决问题。

4/28 休息

今天好累啊，休息一天。主要在看《Go 并发编程实践》，学到了很多并发的理论知识。

4/29 休息

今天一天都是课，不过把制造工程体验的单片机的代码部分写完了，还挺开心的，周五一天都是课，真的好累TAT，明天开始五一假期，争取把《Go 并发编程实践》上面的两个项目都实现完，之后继续复习 Python 数据处理的那本书。要开始学编译原理那些课啦。

4/30 白天考试夜里哭

今天佳期一轮笔试，太丢脸了，数学是一道题没做出来，算法倒是全做出来了，好离谱。休息一会，晚点先看论文，再做每日一题。

5/1 学习汇编

今天和明天估计都在学习汇编，相关的内容在另外一个库更新。今天在实验室搞了一本数据结构的 C 语言实现，可以看完用来复习 C 语言，冥冥之中感觉佳期的笔试能过啊，基本功还是要打好，实验室那边论文进展也不是很顺利 TAT，每日一题不能荒废！

5/4 回溯

今天重新开始做算法题。突然想起来这个 README 如果越来愈长的话，我还得学学怎么用网站保存一下……今天的主题是回溯 (backtracking)，最经典的应用例子莫过于 DFS 深搜了，当一条道路没有办法走到头的时候我们就需要通过回溯之前走过的道路来重新寻找一个新的道路。接下来是几道非常经典的例题：

P51 N 皇后（困难）

非常经典的回溯题，类似于 DFS 的过程，不像那些题解构造一个表格的实例，我直接使用的函数式编程以及 path 的实例进行解题，比较好理解。其中 step() 和 back() 方法分别代表：

对于没有冲突的 path 我们尝试将其延长
对于不符合要求的 path 我们回退寻找下一个字典序的 path

P37 数独（困难）

类似地，我们只需要更改 check() 函数即可，其余类似。

5/5 另外的几棵树

自顶而下伸展树

一般来说我们在使用伸展树的时候需要从上至下插入节点，然后再从下至上进行伸展，实际上我们可以使用自顶而下的方法完成这两个操作：

#ifndef _Splay_H
struct SplayNode;
typedef struct SplayNode *SplayTree;
 
SplayTree MakeEmpty(SplayTree T);
SplayTree Find(ElementType X, SplayTree Y);
SplayTree FindMax(SplayTree T);
SplayTree FindMin(SplayTree T);
SplayTree Initialize(void);
SplayTree Insert(ElementType X,SplayTree T);
SplayTree Remove(ElementType X,SplayTree T);
ElementType Retrieve(SplayTree T);

#endif

大名鼎鼎的红黑树

红黑树是将顶点红黑 2 染色的一种平衡树。在红黑树当中，满足以下几点性质：

根是黑色的
红色顶点只能有黑色儿子
每个顶点到 NULL 顶点的路中黑色顶点的个数都是相等的

练习

为了训练 C 语言的能力，这两天会用 C 完成书上的某些练习，更新会放在新的库当中更新。可能也会尝试用 C 做一下每日一题。编程真是太有意思了！接下来继续学习汇编。

5/7

今天面试感觉自己 C++ 还得复习一下，弄本 C++ Primer 看看，接下来的时间主要还是用 C++ 刷题吧。自己的习惯确实不是很好，不能把 C++ 当作 C with class 用。今天做的每日一题做的有点迷糊，实际上就是一个单调栈就好了，用来寻找不小于当前位置的最近位置，用单调栈就可以解决。

loftea/CodeEveryday