Posts

成都49中的事情尘埃落定后，我的愤怒也随之消退。这次事件引起这么大的风波是我意料之外的，有很多人（包括我在内）这几天都在持续地质疑官方公布的消息，尤其是通告里“排除刑事案件”、“家属表示无异议”等暧昧不清的用词更让人浮想联翩。从警方公布的结果来看，很多质疑都落了空，例如校方故意销毁监控、尸体直接火化、抢占留学名额等。同时，有人开始劝导其他人要相信通告，相信警方，相信政府。 ...

一年一度的五一小长假就这样过去了。说是五天的小长假，实际上有两天是周末，还有两天是通过国务院的“调休”政策、把另外两个周日设为工作日换来的。众所周知，周末是用来躺的。既然这五天假有四天都取自周末，那我岂有不躺的道理？ ...

我们的消费原则就是，不需要原则。 我和女朋友在一起七个月，感情比较稳定，平时经常一起看生活组的家常话题，也被一些奇葩的送礼故事逗笑过。看到经常有豆友纠结对象送的礼物够不够用心，红包够不够大，或者要不要扶贫，我也想分享一下我俩的消费情况，看看礼物和红包是不是真的那么重要。 ...

其实不只是这一本教材，国内对英文计算机文献的翻译质量普遍不高，以至于我直接读英文原著都要比读这种狗屁不通的汉语句子流畅许多。下面这个例子是第14章开头的第一段话，我来试试把原版翻译改良一下，你们品评一下有没有好读许多。 ...

本章提及了数据结构的“扩张”概念。当我们需要支持一种特殊操作的时候，应该优先考虑去扩展现有的数据结构，而不是自创一种。扩展的方法就是“加信息”，然后用原有的基本操作去维护它。作为例子，本章讲了“顺序统计树”和“区间树”，并给出了扩展数据结构的一般方法。 ...

并查集的基本操作 并查集是一种由不相交集合组成的数据结构，它可以用 S={S1,S2,...,Sk}S=\{S_1,S_2,...,S_k\} 表示，其中 SiS_i 是由若干元素组成的集合，任意两个集合之间的交集都为 ∅\empty，每个集合都有一个元素作为它的代表。 并查集需要支持以下操作： MAKE-SET(x)创建一个仅含 x 的新集合（x 不得同时属于其他集合） UNION(x,y)将集合 x、y 合并到一起，形成新的集合 FIND-SET(x)返回集合 x 的代表 一般来说，每个元素都会先通过 MAKE-SET 形成只包含自己的集合，然后通过 UNION 相互兼并。MAKE-SET 和 UNION的运行次数是有限的，不会超过所有元素的总数 nn。与此同时，外部会通过FIND-SET查询某个元素当前属于哪个集合，该操作的次数没有上限。所以，一个并查集的运行效率可以通过两个变量衡量——MAKE-SET 的运行次数 nn，以及上述所有三种操作的总次数 mm。这里假设了每个元素都会先形成自己的集合。 ...

这一章主要研究这几个问题： 怎么求最大/最小 怎么同时求最大&最小 怎么求第二大/小（习题9.1-1） 怎么求第k小 这些问题的算法并不难，本质上我们是想探讨它们所需要的最小比较次数，所以希望大家把重点放在理解证明过程上，学习证明思路，理解排序的本质。下文中，数据规模都用 nn 表示。 ...

今天来讲个有挑战性的内容——红黑树。这是我从本科开始一直没敢去碰的东西，主要是嫌麻烦，实际编程中又不怎么用，但最近就想看着玩。本文只能让你了解红黑树大概的样子，真要理解并形成深刻印象，还得去看《算法导论》的第12、13章。第12章（平衡二叉树）的笔记在上一篇文章里。 ...

本文简单介绍二叉搜索树，为下一篇文章讲红黑树作铺垫。 二叉搜索树 二叉搜索树(Binary Search Tree, BST)是一棵二叉树，每个结点都记录着左子left、右子right、父结点p、关键字key。BST里的关键字总是满足二叉搜索树性质：对于每个结点，其关键字都大于或等于它的任意左子，小于或等于它的任意右子。简单来说，就是“左小右大”。下面比较结点大小时，指的就是比较结点关键字的大小。 ...

一道并不怎么难的题，提交了N次才成功，究其原因是边缘情况特别多，所以一定得好好复盘，练好我一直写不清楚的二分法——我经常绕不清楚奇偶两种情况，也常常照顾不好数组越界。 ...