Codility - Iota 2011 - shortest_adj_seq

题目见 https://codility.com/demo/take-sample-test/iota2011/

思路比较明显：根据给出数据，构造无向图，求出起点到终点的最短路径即可。

显然Dijkstra算法，每条边的长度为1，可以根据此优化，一层一层往后遍历，这样就不需要单独记录每个点与起点的距离，只需记录当前是第几层，否则的话在最大的数据集上会超时（可能是跟我用了好几个map和set有关，不过有轮子可用就不想自己造了…… ）

代码见 https://github.com/phiphy/codility/blob/master/shortest_adj_seq-iota_2011.cpp

Codility - Theta 2011 - gas stations

题目见 https://codility.com/demo/take-sample-test/theta2011/

比较简单的题，思路很直接，贪心法，往后扫描，在当前的加气站如果比后面的加气站便宜的话就尽量多加。只是边界条件要特别小心，很容易出错。

代码见 https://github.com/phiphy/codility/blob/master/gas_stations-Theta_2011.cpp

Codility - Epsilon 2011 - minfuds

题目见 https://codility.com/demo/take-sample-test/epsilon2011/

最近比较忙，偶尔几天才能抽出一个小时左右来想题。而这个题又一直有个小问题，只能拿80分，找了很久没找到，很苦恼。今天突然想到自己构造数据来检查，哈哈，终于一个小时内就找到问题了，修改一提交，100！

由于n条直线最多有O(n^2)的交点，而题目要求的时间复杂度是O(nlgn)，明显暗示就是需要排序…… 所以，首先根据斜率对直线排序，斜率相同的情况下再按截距反向排。从前往后扫描排序好的直线，求出相邻直线的交点，如果该交点比前一个交点的x值还要小，则需要重新计算交点 （这个画个图最清楚了，我很懒就不画了，哈哈），求出的是定义maximum的所有交点。再从后往前扫描排序好的直线，得出定义minimum的所有交点。最后同时对两部分交点扫描，求出每个交点对应在另外一部分的值，计算y值之差后更新全局变量。

说得很乱了，要睡觉了，困。。。

代码见 https://github.com/phiphy/codility/blob/master/minfuds-Epsilon_2011.c

如果有人看到代码不懂的话，可以联系我，不过估计是没有的……

声援朱令，白宫请愿

https://petitions.whitehouse.gov/petition/invest-and-deport-jasmine-sun-who-was-main-suspect-famous-thallium-poison-murder-case-victimzhu-lin/Rd8C54p1

望法网恢恢，疏而不漏，中国能早日步入法制社会，民主社会。民主、科学还需要再喊多少年呢？

Codility - Delta 2011 - min_abs_sum

题目见 https://codility.com/demo/take-sample-test/delta2011/

这是一道很有意思的题目。有N个数的数组A，令有N个数的数组S，S中元素取值为1或-1，则定义 val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }| ，现在要求 val(A, S) 的最小值。很显然，本质是将数组A分成两部分，使得两部分的差最小。不幸的是，数组均分问题是很困难的，其实是NPC的，而题目要求时间复杂度为 O(N*max(abs(A))²) ，并且空间复杂度为 O(N+sum(abs(A))) ，似乎不可能实现…… 但是呢，题目给定了A中元素的取值范围是 [-100, 100] 中的整数，利用这个性质，就能极大地降低复杂度。

首先对数组做处理，负数转换成对应正数，零去掉，计数排序统计有多少个不同元素及其对应个数，并累加所有数的和sum，不妨记b=sum/2，不同元素个数为m，则目标转换为在m个不同元素中挑出若干个元素（每个元素可以重复多次，但少于它们的出现次数），使得它们的和不大于b并尽量接近。到了这里，应该有点熟悉的感觉了吧。对了，其实这就是0-1背包问题！

记 f[i][j] 为只允许选前 i 个元素，总和不超过 j ，则有 f[i][j] = max { f[i-1][j], f[i][j-D[i]]+D[i] }, 其中 D[i] 为第 i 个元素对应的值。由于每种元素的数量不是无穷多，因此对每个 f[i][j] ，都需要记录第 i 种元素的消耗数量，保证小于该元素的出现次数。

代码见 https://github.com/phiphy/codility/blob/master/min_abs_sum.c

Keywords: 0-1 knapsack

Codility - Gamma 2011 - count_palindromic 回文子串

这是一道Codility上的题目，见 https://codility.com/demo/take-sample-test/gamma2011/ 大意就是给定一个字符串，求出它的所有长度大于2的回文子串的个数。这与求字符串的最长回文子串的问题是等价的。

首先想到的就是遍历字符串的所有长度大于2的子串（共有2+3+...+n-1 = (n+1)(n-2)/2个），对每个子串判断是否为回文串，时间复杂度为O(n^3)

然后，我们注意到，所有的回文子串都有一个中心位置，而对于长为n的字符串，能作为回文子串中心位置的只有2n-1种可能（对于本问题，其实只有2n-3种可能，需要去除第一个和最后一个字符所在的位置），因此，只需遍历这些可能的位置，找出以该位置为中心的回文子串的数目，时间复杂度是O(n^2)。

看起来，似乎这种方法是最优的，毕竟，有2n-3个位置需要判断，而每次判断的时间复杂度是O(n)，因此最终时间复杂度是O(n^2)，看起来是不能再改善了。

但是呢，世界就是这么奇妙，就像神奇的KMP字符串匹配算法一样，居然能把字符串匹配的时间复杂度做到O(n+m)。对本问题，其实是存在O(n)时间复杂度的算法的！

为了统一处理奇数长度和偶数长度的回文串，我们在每个原字符串的每个字符之间加上一个分隔符#，并且在字符串开头加上一个终结符$，因此，当原字符串是baababa时，转换后的字符串是$#b#a#a#b#a#b#a#，这样，当回文中心是#字符时，回文长度为偶数；当回文中心不是#时，回文长度为奇数。

该算法的基本思想就是扫描处理后的字符串S，记录以每个字符为中心时的最长回文串，同时更新全局的最长回文串记录。描述如下：

待处理字符串为S，长度为N

P为长为n的数组，P[i]记录以字符i为中心的最长回文串的半边长度加1（回文串长度为 2*(P[i]-1) + 1）

K为之前的回文串到达的最右位置，j为该回文串的的中心位置

for i = 1..len(s)-1

    初始化P[i]

    逐渐增加P[i]，直至不满足回文串条件

    统计该回文串中回文数目

    if i+P[i] > K

        K = i + P[i]

        j = i

但看描述，似乎与O(n^2)的算法一样，但该算法的关键是初始化P[i]，如果每次循环之前P[i]能尽量大，那么每次循环的比较次数就很少，从而降低了复杂度。（具体时间复杂度分析比较复杂，本文不作精确分析）

那么如何确定一个较大的P[i]值呢？

不妨假设当前扫描到第i个字符，根据全局K和j值，我们有：

index            2j-i       j       i        K

char/str     A   S[i]  B  S[j]  B  S[i]  A  S[K]

由于以j为中心的回文串的最右位置为K（不包含），当K大于i的情况下，不妨假设i与K之间的字符串为A，j与i之间的字符串为B，那么根据回文串性质有2j-i与j之间字符串为B，2j-i之前存在字符串A。

可以利用2j-i与i位置的对称性，不妨假设P[2j-i] = x，那么说明B字符串的前x-1个字符与A字符串的后x-1个字符相同，因此对于i来说，只需要从i+x开始判断即可，如果i+x大于K，那么则从K开始递增。

具体代码（针对Codility题目）如下，亦可参见 https://github.com/phiphy/codility/blob/master/count_palindromic_slices.c

int imin(int x, int y) { return x < y ? x : y; }

int solution ( char *t ) {

    if (!t)

        return 0;

    int n = strlen(t);

    if (n < 2)

        return 0;

    int i, j, k, r = 0;

    int m = n + n + 3;

    char *s = (char *)malloc(sizeof(char) * m);

    int *p = (int *)malloc(sizeof(int) * m);

    for (s[0] = '$', s[1] = '#', i = 0, j = 2; i < n; ++i) {

        s[j++] = t[i];

        s[j++] = '#';

    }

    s[j] = '\0';

    for (k = 0, i = 1; i < m-1; ++i) {

        p[i] = k > i ? imin(p[2*j-i], k-i) : 1;  // update p[i], as large as possible

        while (s[i+p[i]] == s[i-p[i]])

            ++p[i];

        if (p[i] > 1) {

            r += (p[i]/2 - (s[i]!='#'));

            if (r > 100000000) {

                r = -1;

                break;

            }

        }

        if (p[i]+i > k) {

            k = p[i] + i;

            j = i;

        }

    }

    free(s); s = NULL;

    free(p); p = NULL;

    return r;

}

听说这道题也可以用后缀数组解决，不过我暂时还不懂后缀数组，这段时间研究一下。

生成字符串的全排列

递归的方法比较简单，略过。

非递归方法首先需要将字符串排序，然后循环查找下一个比当前字排列大的字符串。举例来说，当前字符串是1 5 7 6 4 3 2，我们知道下一个应该是1 6 2 3 4 5 7，怎么找到的呢？

从右边往左扫描，找到第一个比左边字符大的字符，本例中我们找到了7，然后将7左边的字符（5）与与右边的字符（6 4 3 2）比较，找到（6 4 3 2）中比5大的字符，本例中是6，将5与6交换，然后反转7右边的字符（将5 4 3 2反转成2 3 4 5）。

思路清楚之后，程序就很简单了，并且能处理重复字符的情况（如果用递归的方法，需要检测重复字符进行处理）。

void permutation(char *s, int n)

{

    std::sort(s, s + n);

    printf("%s\n", s);

    int i, j;

    while (1) {

        for (i = n-1; i>=1 && s[i]<=s[i-1]; --i)

            ;

        if (i == 0)

            break;

        for (j = n-1; j>i && s[j]<=s[i-1]; --j)

            ;

        std::swap(s[i-1], s[j]);

        for (j = n-1; i < j; ++i, --j)

            std::swap(s[i], s[j]);

        printf("%s\n", s);

    }

}

poj 1166 The Clocks

这是一道挺有意思的题目，方法也很多，值得讨论讨论。

首先想到的是搜索的方法。

分析题目可知，9种移动方法，每种方法最多使用3次（因为4次会回到初始状态），因此总的状态数为4^9=262144，不算多，因此简单的BFS就可以搞定，但是空间开销比较大，如果牺牲一点时间换取空间，可以使用限定深度的DFS方法，将深度从1开始递增到27，搜索的状态数最多是BFS的两倍，但是空间消耗少了很多。状态表示上，可以用两个bit位表示一个钟表的状态，这样只需18位就可以表示9个钟表的状态，移动方法的作用也都采用位运算来加速。

代码见https://github.com/phiphy/poj/blob/master/poj1166-dfs.cpp

其实这是一道数学题。

不妨设钟表的初始状态为A，9种移动方法对钟表的作用可以用矩阵M表示（第一列为第一种移动方法，依此类推），将移动方法用向量x表示，则有A + M.x = 0，于是解得x = M^{-1} * (-A)，注意所有的运算都需要模4，而M的逆可以事先求得，因此该解法的时间复杂度是O(1)，结束！

代码见https://github.com/phiphy/poj/blob/master/poj1166-matrix.cpp

算法导论-红黑树

Introduction to Algorithms 3rd Edition

Part III - Data Structures
Chapter 13: Red-Black Trees

为了解决二叉排序树在最坏情况下的插入、删除和查找等操作的性能，本质上是尽量将树的高度维持在lg(n)左右，出现了一些二叉排序树的变种，比较著名的有AVL树，红黑树等。一般认为，红黑树的平均性能较AVL树更好，插入、删除所需的旋转操作更少，因而应用更广泛。

红黑树具有以下性质：
    1. 每个节点非黑即红
    2. 根节点为黑
    3. 所有叶子节点（NIL）都为黑
    4. 如果一个节点为红，那么它的两个孩子都为黑
    5. 对任何一个节点，从它到所有它的叶子节点的路径上黑色节点个数相等

为了方便，定义一个全局空指针NIL，所有叶子节点都是NIL，颜色为黑，根节点的父节点为NIL。

可以证明，一棵有着n个内节点的红黑树的高度至多为2lg(n+1)。

为了保持红黑树的高度在O(lgn)，需要在插入和删除节点时对红黑树进行调整，而调整的主要手段就是对节点进行旋转，以此来维持红黑树的平衡。当然旋转之后可能会导致违背红黑树性质的情况出现，这时就需要对红黑树做进一步的调整。对一个节点左旋，是将它与右孩子旋转；对一个节点右旋，是将它与左孩子旋转。

由于红黑树特性的复杂性，相较二叉排序树，其插入和删除操作也更为复杂，下面详细分析。

对于插入操作，在二叉排序树的插入操作基础上，需要做一点修改。新插入的节点，如果将它的颜色设为黑，那么很显然会影响到红黑树的第5条特性；如果将它的颜色设为红，那么又可能会影响到第4条特性。如果违背第5条特性的话，需要的修正操作会更多更复杂，因而我们首先将新插入的节点的颜色设置为红。不妨记新插入的节点为z，如果z的父节点颜色为黑，那么不需要任何额外修正（除非z是根节点）；如果z的父节点颜色也为红，那么就需要调整操作。由于对称性，我们只考虑z的父节点z.p为左孩子的情况（z.p = z.p.p.left），在这个条件下，根据z是左孩子还是右孩子，以及z的叔叔节点的颜色，又可以分为四种情况：
a. z为左孩子，叔节点为红
b. z为右孩子，叔节点为红
c. z为右孩子，叔节点为黑
d. z为左孩子，叔节点为黑

首先来看a和b，如下图所示。在这种情况下，只需将z的父节点和叔节点都设置成黑，z的爷节点设置成红，之后，z的爷节点可能会违背性质4，因此继续重复，将z设置成z.p.p继续。

再来看c和d，如下图所示。c可以通过对z的父节点左旋来转换成d，而d则只需对z的爷节点右旋，并改变z的父节点和爷节点的颜色来完成调整。可以看出，每次调整前后，所有叶子节点的路径长度（黑色节点个数）都没有改变。因此是正确的。


具体的调整代码如下所示。注意到第17行需要把T的根节点设置为黑，这是因为当跳出循环时，z可能恰好是T的根节点并且为红，因此需要将它设置为黑。可以看出，每次插入一个节点至多会进行两次旋转操作，而一旦执行了右旋操作，必然退出循环，调整结束。时间复杂度是树的高度O(lgn)。
RB-INSERT-FIXUP(T, z)
 1      while z.p.color == RED
 2          if z.p == z.p.p.left
 3              y = z.p.p.right
 4              if y.color == RED
 5                  z.p.color = BLACK           // case 1
 6                  y.color = BLACK             // case 1
 7                  z.p.p.color = RED           // case 1
 8                  z = z.p.p                   // case 1
 9              else
10                  if z == z.p.right
11                      z = z.p                 // case 2
12                      LEFT-ROTATE(T, z)       // case 2
13                  z.p.color = BLACK           // case 3
14                  z.p.p.color = RED           // case 3
15                  RIGHT-ROTATE(T, z.p.p)      // case 3
16          else (same as then clause with 'right' and 'left' exchanged)
17      T.root.color = BLACK

至于节点的删除，仍然是在二叉排序树节点删除的基础上修改。最重要的是要记录删除之后真正缺少的颜色是什么，如果是红色那无所谓，如果是黑色，那就会影响到它的子树。
先看删除操作的代码，之后再分析删除之后调整红黑树的代码。
RB-DELETE(T, z)
 1      y = z
 2      y-original-color = y.color
 3      if z.left == T.nil
 4          x = z.right
 5          RB-TRANSPLANT(T, z, z.right)
 6      else if z.right == T.nil
 7          x = z.left
 8          RB-TRANSPLANT(T, z, z.left)
 9      else
10          y = TREE-MINIMUM(z.right)
11          y-original-color = y.color
12          x = y.right
13          if y.p == z
14              x.p = y
15          else
16              RB-TRANSPLANT(T, y, y.right)
17              y.right = z.right
18              y.right.p = y
19          RB-TRANSPLANT(T, z, y)
20          y.left = z.left
21          y.left.p = y
22          y.color = z.color
23      if y-original-color == BLACK
24          RB-DELETE-FIXUP(T, x)

代码中需要特别注意的地方是：x取代了y原来的位置，y的颜色被设置成z的颜色，因此y的颜色缺失了。如果y的颜色是红，那么不影响红黑树性质；如果y的颜色是黑，那么就可能会影响，需要进行调整。
由于x取代了y的位置，而y为黑。如果x为红，那么直接将x设为黑即可；如果x为黑，需要将x对黑的贡献改为2。具体调整代码如下：

RB-DELETE-FIXUP(T, x)

  1  while x != T.root and x.color == BLACK

 2      if x == x.p.left

 3          w = x.p.right

 4          if w.color == RED

 5              w.color = BLACK                 // case 1

 6              x.p.color = RED                 // case 1

 7              LEFT-ROTATE(T, x.p)             // case 1

 8              w = x.p.right                   // case 1

 9          if w.left.color == BLACK and w.right.color == BLACK

10              w.color = RED                   // case 2

11              x = x.p                         // case 2

12          else

13              if w.right.color == BLACK

14                  w.left.color = BLACK        // case 3

15                  w.color = RED               // case 3

16                  RIGHT-ROTATE(T, w)          // case 3

17                  w = x.p.right               // case 3

18              w.color = x.p.color             // case 4

19              x.p.color = BLACK               // case 4

20              x.right.color = BLACK           // case 4

21              LEFT-ROTATE(T, x.p)             // case 4

22              x = T.root                      // case 4

23      else (same as then clause with 'right' and 'left' exchanged)

24  x.color = BLACK

只考虑x是左孩子的情况，又可以分为四种情况：

1. x的兄弟节点w是红色。如下图所示，由于w是红色，因此x的父节点、w的孩子节点都是黑色，对x的父节点左旋，并修改x父节点和w的颜色，这时x的兄弟节点颜色为黑，转换为其它情况。

2. x的兄弟节点w为黑，并且w的孩子都为黑。如下图所示，不管x的父节点是什么颜色，可以将w改成红色，并将x修改为父节点，这样x就往上移了一个节点，继续循环。

3. x的兄弟节点w为黑，w的左孩子为红，右孩子为黑。如下图所示，将w右旋，并修改新的w及其右孩子颜色，可以将新的w右孩子改成红，转换成case 4

4. x的兄弟节点w为黑，w的右孩子为红。如下图所示，将x的父节点左旋，并修改几个节点的颜色，可以结束调整（通过将x设置为T.root）。

Exercises

13.1-3
很显然仍然是

13.1-5
最短的情况是x到叶子节点都是黑色节点，最长的情况是x到叶子节点的路径红黑相间。后者至多是前者的两倍

13.1-6
如果所有节点都是黑色，那么内节点个数为2^k-1；如果是红黑相间，那么内节点个数为2^2k -1

13.1-7
最大的比例是2，所有黑色节点的孩子都是红节点，每个黑色节点都对应两个红色节点，因此比例为2；最小的比例为0，没有红色节点

13.2-1
将LEFT-ROTATE中的x与y对换，left与right对换即可

13.2-2
因为旋转是基于两个节点的，而两个节点必然确定一条边，n个节点的树有n-1条边，因此恰好有n-1种旋转

13.2-3
如果y为黑，那么α高度加1；如果x为黑，那么γ高度减1；β高度不变

13.2-4
任何一个树至多通过n-1次右旋可以转换成right-going chain

13.2-5
1(#, 2)不能通过右旋转换成2(1, #)
如果T1能通过右旋转换成T2，那么可以这样操作：首先通过右旋操作将T1中与T2的根节点对应的那个节点旋转成根节点，之后再递归地对左右子树操作，复杂度是：
T(n) = O(n) + T(k) + T(n-1-k)，也即T(n) = O(n) + T(n-1)，因此T(n) = O(n^2)
P.S. 我也不知道这样证明对不对……

13.3-4
设置成红色节点只有在case 1和case 3才出现：将z.p.p设置成红，如果z.p.p是T.nil，那么z.p就是根节点，为黑，根本就不会进入循环；再来看case 2，我们在将z.p.p设置为红之前将z和z.p交换了，但是交换之后进行了旋转操作，z.p.p仍然不变，因此case 2也没有问题。所以这种情况不会发生

13.4-7

直接看答案吧，哈哈

二叉排序树的遍历方式

有必要把二叉排序树的几种遍历方式总结一下，只考虑中序遍历，先序遍历和后序遍历同理。

1. 递归方式

这是最简单的，代码也很简洁。

1   void inorder_walk(Node *t)

2   {

3       if(t != NULL) {

4           inorder_walk(t->left);

5           print(t);

6           inorder_walk(t->right);

7       }

8   }

2. 消除尾递归

所有的尾递归都会被编译器优化，这在编译原理中都有介绍。如果我没记错的话，原理应该是这样的：

文法 A: NIL | a | aA 具有尾递归的形式，可以改写成:

A: NIL | Ba

B: NIL | Bb

这样就消除了尾递归。消除尾递归后的遍历代码为：

1   void inorder_walk_notailrecursion(Node *t)

2   {

3       while(t != NULL) {

4           inorder_walk_notailrecursion(t->left);

5           print(t);

6           t = t->right;

7       }

8   }

3. 消除递归

操作系统在函数调用的实现上，是采用栈的形式，递归调用实际上就是将同一个函数不断压入栈中，因此要消除递归，可以在程序中用一个显示的栈来模拟。代码如下：

 1    void inorder_walk_norecursion(Node *t)

 2    {

 3        stack<Node *> s;

 4        while(1) {

 5            while(t != NULL) {

 6                s.push(t);

 7                t = t->left;

 8            }

 9            if(s.empty())

10                break;

11            t = s.top();

12            s.pop();

13            print(t);

14            t = t->right;

15        }

16    }

4. 消除递归并且不用栈

这个就比较复杂一些，基本思想是根据之前的访问的节点和当前节点的关系判断下一步的操作，具体分析和代码可以参考上一篇文章算法导论-二叉排序树。再贴一遍代码如下：

 1    void inorder_walk_nonrecursive_nostack(Node *t)

 2    {

 3        Node *prev = NULL;

 4        Node *curr = t;

 5        Node *next = NULL;

 6        while (curr != NULL) {

 7            if (prev == curr->parent) {

 8                next = curr->left;

 9                if (next == NULL) {

10                    print(curr);

11                    next = curr->right;

12                    if (next == NULL)

13                        next = curr->parent;

14                }

15            } else if (prev == curr->left) {

16                print(curr);

17                next = curr->right;

18                if (next == NULL)

19                    next = curr->parent;

20            } else {

21                next = next->parent;

22            }

23            prev = curr;

24            curr = next;

25        }

26    }

算法导论-二叉排序树

Introduction to Algorithms 3rd Edition

Part III - Data Structures

Chapter 12: Binary Search Trees

树在数据结构中是非常重要的，而二叉树又是应用最多的，重要性不言而喻。在二叉排序树中，对每个节点，其左子树中节点的值比它小，右子树中节点的值比它大，左右子树都是一棵二叉排序树。平均而言，二叉排序树具有非常均衡的插入、删除和查找性能，都是O(h)，因而备受亲睐。

对二叉排序树，查找和插入比较简单，删除稍微复杂：如果左子树和右子树至少有一个空，那么很简单；如果两个子树都不为空，那么需要找到待删除节点的后继，这时又有两种情况，该后继或者是待删除节点的右孩子，或者不是，如果不是的话多一步操作。其实也是比较简单的，画个图就能理解了，但是指针的修改要特别注意，否则很容易出错。

Exercises

12.1-2

BST中左孩子的值小于节点小于右孩子，而小顶堆中节点的值小于左子树和右子树。

当然不行了，如果可以的话，堆排序的时间复杂度就变成O(n)了，而我们知道这是不可能的……

12.1-3

一种方法是用栈。

另外一种方法的思路是：首先遍历左子树，根据之前访问的节点判断当前应该执行的操作。如果之前访问的是父节点，那么就应该先打印左子树；如果之前访问的是左孩子，那么就应该返回父节点并打印父节点，然后转向右子树；如果之前访问的是右孩子，那就应该返回父节点。因此，代码如下：

 1    void inorder_walk_nonrecursive_nostack(Node *t)

 2    {

 3        Node *prev = NULL;

 4        Node *curr = t;

 5        Node *next = NULL;

 6        while (curr != NULL) {

 7            if (prev == curr->parent) {

 8                next = curr->left;

 9                if (next == NULL) {

10                    print(curr);

11                    next = curr->right;

12                    if (next == NULL)

13                        next = curr->parent;

14                }

15            } else if (prev == curr->left) {

16                print(curr);

17                next = curr->right;

18                if (next == NULL)

19                    next = curr->parent;

20            } else {

21                next = next->parent;

22            }

23            prev = curr;

24            curr = next;

25        }

26    }

12.1-4

太简单了

12.1-5

因为中序遍历BST只需要O(n)的时间，因此构造至少需要Omega(nlgn)的时间，否则基于比较的排序就能在少于O(nlgn)的时间内完成了。

12.2-4

5(1(#, 3(2, 4)), #)

检索4时，搜索路径是5->1->3->4，因此A = {2}, B = {1, 3, 4, 5}, C为空，显然A中的2比B中的1要大

12.2-5

根据定义，显然的

12.2-7

每条边最多遍历两次，而边数是n-1，因此时间复杂度是O(n)

12.3-2

检索时还得比较插入的节点，所以多一次

12.3-3

最坏情况就是原数组有序，复杂度是O(n^2)；最好情况是随机，树的高度是lg(n)，复杂度是O(nlgn)

12.3-4

5(2(1, 4(3, #)), #), 删除1后变成5(2(#, 4(3, #)), #)，再删除2变成5(4(3, #), #)。如果先删除2则变成5(3(1, 4), #)，再删除1变成5(3(#, 4), #)。删除的顺序不同导致最后的树不同

12.4-3

当n=3时，排列共有6种：123, 132, 213, 231, 312, 321，建树之后分别为：1(#, 2(#, 3)), 1(#, 3(2, #)), 2(1, 3), 2(1, 3), 3(1(#, 2), #), 3(2(1, #), #)，其中树一共只有5种，所以随机选一种BST的话概率是1/5，但是随机选择一种输入构建BST的话，生成2(1, 3)的概率是1/3，其它4种的概率是1/6。因此二者是不同的。

Problems

12-2

将S中的字符串逐个插入到radix tree中，复杂度与字符串长度成正比，为O(n)，之后先序遍历radix tree，碰到表示字符串的节点就输出，遍历的边数最多为字符串总长的两倍，因此复杂度仍为O(n)，因此排序的复杂度就是O(n)

12-4

这个其实就是Catalan数的小例子，接下来要专门分析一下Catalan数及其广泛的形式，可以参考http://en.wikipedia.org/wiki/Catalan_number

文化是另一种宗教

在现在的分类中，文化、传统文化应该是不属于宗教的。

文化不仅能给人们带来知识，也是维系社会发展进步的纽带，也许不是民族主义的必要条件，但是无疑能增强民族主义，虽然这个东西有着好的一面，但是也会被利用，而且是很容易就被利用，说句难听的就是被人卖了还帮人数钱呢。没有文化的民族是很可悲的，也许能强盛一时，但缺少了文化，就如同地基不牢的高楼，是很脆弱的。历史上最有名的例子应该就是蒙古了。忽必烈、成吉思汗时强极一时，蒙古骑兵横扫整个欧亚大陆，无人能挡。建立元朝也是需要许多的中国士大夫文人来定国号、定服色、礼仪等等。其实皇室的终极目标就是通过一整套繁琐的仪式来维持自己神一般的存在和地位，期望永远统治世人。然而，这个民族就是缺少文化，纵然其能盛极一时，几代之后就会被各地文化民族所反扑，而几乎消失殆尽。

宗教，几乎都有一本书，也许是描述其产生于发展，也许是介绍教条和教义，以及宗教仪式，或者兼而有之。这不就是想构造出一种宗教的历史文化，"强迫"信徒们去学习、理解和发扬吗？宗教当然不能代替自然科学等文化，但是它却想代替历史文化。对于一些没有文字记录，没有多少文化的地方，如果某种宗教恰好在某个时期传入，尤其是大部分人生活比较困苦，对生活、对未来感到绝望的时期，宗教的传播应该会非常迅速，并代替其它文化。一般这种情况下，即便有好几种宗教几乎同时传入，由于一山不容二虎，因而其中一种会占主导地位，另外一种则只有较少的信徒。这点，在世界上大部分宗教国家中都存在这种现象。

如果有文化，有很深厚的历史文化，许多期望在宗教中能寻找到的东西在文化中就能找到，因而对宗教的需求和依赖就不会那么强烈，大部分时候人们可以沉浸或者陶醉在传统文化中，而不需要宗教的慰藉。如果宗教能给的，文化也能给的话，我们还需要宗教作什么用呢？

很显然，这个世界、这个社会不能仅仅依靠宗教来维系，犹如社会不能依靠道德来维系一样。虽然，在一些小的村庄，或者小的部落，是可以没有法律，只靠道德来维系的，这也是古代很多小村庄小城镇的存在方式。但是，一旦人数增长超过一定量，原有的道德体系不再能维系村庄和社会的健康发展，而需要另外的手段，比如法律、警察等。

既然如此，宗教到底有什么用呢？宗教到底能带来什么呢？

（诚然，存在一些人，他们做某些事情的时候是不考虑结果的，只是因为要做这些事情而做。但是我相信，更多的人都希望从他们所做的事情中得到些什么，即便这些事情对他们而言已经成为一种形式一种传统一种仪式，也许他们仍期望得到些什么。）

算法导论-哈希表

Introduction to Algorithms 3rd Edition

Part III - Data Structures

Chapter 11: Hash Tables

有一些应用场景需要在集合上有较多的插入、删除和查找的操作，要求时间复杂度越低越好。对于此类应用，为了通用性考虑，在不知道或者需要支持众多输入元素数据类型的情况下，一般是采用平衡的二叉树来实现，例如红黑树，这几中操作的平均性能都是O(lgn)。但是如果知道输入的数据类型，甚至知道输入数据的取值方式和范围的情况下，就存在一种更好的选择：哈希表。在理想的情况下，哈希表在插入、删除和查找上都能实现O(1)的时间复杂度，这也是我们梦寐以求的。

可以将哈希表看作一个大数组，将输入采用某种方式映射到数组中的特定位置，y = f(x)，当然，映射函数f的选择很重要，好的映射函数f能降低不同的x值取得同一个y值的概率。对于不同的数据类型，一般都会选择不同的哈希函数。设计合适的哈希函数是一个比较困难的问题。对于哈希表，由于其随机性，一般是分析平均情况下的时间复杂度。

当哈希表发生地址冲突时，解决办法一般是采用某种方法探测哈希表的另一个可用存储单元，直至找到可用的空位置。采用的方法一般有链地址法和开放地址法。链地址法比较简单，如果发生冲突，就在该地址上创建一个链表，将冲突的元素加入到链表中即可。开放地址法可以描述为 x' = x + g(i) (i = 1, 2, ...)。如果g(i) = i，就是线性探测再散列，也就是从冲突位置往后找到空位；如果g(i) = (-1)^(i+1)*((i+1)/2)^2，也即g(i) = 1^2, -1^2, 2^2, -2^2, ...，称为二次探测再散列。当然还有其它方法，比如再散列 g(i) = f'(x)等等。

不管怎样，哈希的终极目标就是在集合上的插入、删除和查找等操作的平均时间复杂度达到O(1)。

在哈希表上的时间复杂度分析比较复杂，涉及较多数学计算，在此表达不便，因此不涉及，有兴趣可以参考教材。

算法导论-基础数据结构

Introduction to Algorithms 3rd Edition

Part III - Data Structures

Chapter 10: Elementary Data Structures

在算法中，栈、队列、链表和树是几种最基础的数据结构，几乎所有高级数据结构都是对基础数据结构的扩充和变种。栈的特性是后进先出，栈在操作系统和编译器领域都是极其重要的，堆和栈是操作系统内存分配中最重要的结构，至于编译领域，函数调用都是基于栈的方式，所以所有递归的程序都可以用栈改写成非递归的形式。数组是链表的一种形式，链表的应用范围非常广泛，几乎无所不在，比如排序，内存分配、垃圾回收等。树几乎是所有高级数据结构的基础，前面介绍的堆排序用到了树结构，很多语言的标准库中的集合、哈希表的实现都是基于树，红黑树，B树，文件系统，树的应用也无所不在，这主要是因为树在查找、插入和删除等操作上的时间复杂度比较均衡，因而在很多领域是首选的数据结构。

所有基础数据结构都要熟练掌握，如果算法是内功的话，这几种数据结构就是内功的基础，基础不牢，所有高级的内功都不能消化。

Exercises:

10.1-2

两个栈向数组中间增长，直至相遇才overflow

10.1-5

用head和tail变量记录deque的头和尾

10.1-6

不妨设两个栈为S1和S2，每次ENQUEUE时PUSH到S1中，每次DEQUEUE时POP S2，如果S2为空，那么将S1中的所有元素POP到S2中。最坏情况下的时间复杂度是O(n)，平均期望时间复杂度是O(1)

10.1-7

不妨设两个队列是Q1和Q2，每次PUSH时检测Q1和Q2哪个为空，假设Q1为空，就ENQUEUE Q1，然后将Q2的所有元素DEQUEUE并ENQUEUE到Q1中。POP时将不为空的队列DEQUEUE即可。

10.2-1

DELETE需要扫描链表找到需要删除的元素。

10.2-2

PUSH时INSERT到最前面，POP时删除第一个元素。

10.2-3

增加尾指针，ENQUEUE时添加到最后，DEQUEUE时删除第一个元素

10.2-4

给L.nil.key赋值成k

10.2-6

用链表即可，将一个链表连接到另一个链表最后。

10.2-7

从前往后扫描，反转

算法导论-中位数及查找

Introduction to Algorithms 3rd Edition

Part II - Sorting and Order Statistics

Chapter 9: Medians and Order Statistics

这一章主要是介绍查找问题：查找最大值、最小值，查找第n大的数等等。

很显然，查找最大值和最小值都需要遍历整个数组，因此时间复杂度是O(n)；如果同时查找最大值和最小值，是否需要遍历两遍数组呢？其实是不需要的，只需将原数组两两分组，每组分别比较，然后在n/2个较大的数里查找最大值，在剩下的n/2个数里查找最小值，总共的比较次数是3n/2，比遍历两次数组的2n-2要少n/2左右的比较次数。这也可以算是分治思想的应用。

对于查找第n大的数，如果是有大量的查询，可以先将原数组排序，然后直接选择即可，时间复杂度是O(nlgn)。如果只有少量的几次查询，需要在线性时间内完成呢？可以借鉴快速排序的思想，随机选择一个数，将原数组分成两份，判断是在前半部分还是后半部分查找，递推即可。可以证明，该算法平均情况下的时间复杂度是O(n)，但是最坏情况下的时间复杂度是O(n^2)。

因此，能否找到一种在最坏情况下是O(n)的查找算法呢？答案是肯定的。算法思路如下。不妨设原问题的时间复杂度是W(n)，那么第2行的时间复杂度是W(n/5)，再次递归时最坏情况下的时间复杂度是W(7n/10)，因此W(n) <= W(n/5) + W(7n/10) + cn <= cn + 9n/10 + 81n/100 + ... = O(n)

SELECT(S, k)

1   将S划分成5个一组，共n_M = upper(n/5)组

2   对每组的5个数进行排序，找中位数，n_M个中位数放到集合M

3   m* = SELECT(M, upper(|M|/2)) 将S中的数划分成A, B, C, D四个集合

4   将A和D中的每个元素与m*比较，小的构成S1，大的构成S2

5   S1 = S1 U C, S2 = S2 U B

6   if k = |S1| + 1, return m*

7   else if k <= |S1|, return SELECT(S1, k)

8   else, return SELECT(S2, k - |S1| - 1)

其实，这个算法在从理论上来说是非常漂亮的，但是太不优美了，太复杂了，编程实现也不太容易，虽然是O(n)的复杂度，但是隐藏的系数很大。而且，现实中，在一个很大的集合中只查找一次的情况不太常见，因此该算法在实际上用途有限。重点仍是掌握排序算法，彻底掌握插入排序、归并排序、堆排序和快速排序。

Exercises

9.1-1

将原数组两两分组，每组分别比较，将较大的数记录在较小的数指向的链表中，递归，最后最小的数指向的链表有upper(lg(n))个数，由于找到最小的数需要n-1次比较，因此总共需要的比较次数是n+upper(lg(n))-2

9.3-1

每组7个仍然有效，但是每组3个就不成立。至少需要5。

9.3-3

每次分割选择中位数

9.3-4

?

9.3-5

找出中位数，将数组划分，再在其中某个数组中查找即可。T(n) <= T(n/2) + O(n) = O(n)

9.3-7

找出第n/2-k/2大的和第n/2+k/2大的数，然后遍历找出在其中的数即可

9.3-8

比较X[n/2]和Y[n/2]，如果X[n/2]>Y[n/2]，那么再比较X[n/4]和Y[3n/4]，依此类推，每次减少一半的数，因此T(n) = T(n/2) + 1 = O(lg(n))

9.3-9

可以证明，当pipeline在所有well的y值的中位数的位置，总长是最小的。因此就是找中位数的问题。

Problems

9-1

a. 用归并排序或者堆排序，时间复杂度是O(nlgn)

b. 建堆时间复杂度是O(n)，每次选出最大值，调整堆复杂度O(lgn)，因此总的时间复杂度是O(n + ilgn)

c. 选出第i大的数O(n)，分割O(n)，排序O(ilgi)，总时间复杂度是O(n + ilgi)

9-2

a. 显然

b. 对x排序，然后累加w值直至1/2即可

c. 选出x的中位数，将x分割，累加每部分中的x值，对大于1/2的部分递归，T(n) = T(n/2+1) + O(n) = O(n)

d. 略，有点复杂

e. 由于x和y互不影响，因此对x和y分别找出weighted median，即可确定坐标。

算法导论-线性时间排序

Introduction to Algorithms (third edition)

第八章：Sorting in Linear Time

之前介绍的插入排序、归并排序、堆排序和快速排序都是基于比较的排序方法，平均情况下的时间复杂度都是O(nlgn)（其中插入排序需要修改成二分查找而不是线性查找，但是这会影响到插入排序最优情况下的O(n)时间复杂度），本章首先证明了这也是基于比较的排序方法所能达到的最好下界。直观的解释就是考虑n个元素的比较决策树，由于n个元素的排列有n!种可能，因此决策树的深度为lg(n!) = O(nlgn)，因此基于比较的排序算法平均情况下的时间复杂度下界是O(nlgn)，所以在基于比较的大前提下，不用费尽心思去寻找O(n)的排序算法，否则就如同试着发明永动机一样。

但是不要悲观，对于一些特殊的输入数据，可以不用基于比较的排序方法，而取得线性的时间复杂度。比如，有n个数，每个数的取值范围是0~k，其中k = O(n)，在这种情况下，可以使用计数排序，时间复杂度是O(n)。计数排序的基本思想就是顺序扫描数组，统计每个数的出现次数，然后计算有多少个数比某个数小，然后再直接输出排序结果。时间复杂度是O(n+k)，由于k=O(n)，因此时间复杂度即是O(n)。

有了计数排序，再深一步，就有了基数排序。比如要排序一些十进制表达的数组，每一位的数范围都是0~9，从低位到高位，对每位上实行0~9的计数排序，就是基数排序了。不妨设每一位的范围是0~k，有d位，总共有n个数，那么基数排序的时间复杂度就是O(d(n+k))。注意必须从低位开始排序，不能从高位开始，否则会打乱之前的高位排序，造成结果错误。

RADIX-SORT(A, d)

1    for i = 1 to d

2        use a stable sort to sort array A on digit i

最后介绍的桶排序，基于输入满足均匀分布的假设，比如n个满足[0, 1)上的均匀分布的数。不妨将[0, 1)区间均分成n份，[0, 1/n), [1/n, 2/n), ..., [(n-1)/n, 1)，顺序扫描输入，将n个数加入到对应的桶中，这个步骤的时间复杂度是O(n)，然后对每个桶中的数进行插入排序，最后逐个输出桶中的数即可。如果数据分布比较均匀，每个桶中的数都比较少，可以证明，每个桶中插入排序的期望时间复杂度是O(2 - 1/n)，因此总的时间复杂度是O(n) + n*O(2 - 1/n) = O(n)

这一章介绍的排序方法都有非常优秀的时间复杂度，但是对输入有特殊要求，所以在通用性上不及之前介绍的基于比较的排序方法。但是，在某些特殊领域，或者在某些情况下，这几种排序方法还是大有用武之地的。

Exercises

8.1-1

n, when the array is in order and there is n-1 comparison

8.1-3

lg(n!/2) = lg(n!) - 1 = O(nlg(n))

lg(n!/n) = lg(n!) - lgn = O(nlg(n))

lg(n!/2^n) = lg(n!) - n = O(nlg(n))

8.1-4

for each of the n/k subsequences, needs lg(k!) = klg(k) comparisons, so the total lower bound of comparisons needed is n/k * klg(k) = nlg(k)

8.2-2

由于输出排序结果时，是从后往前扫描原数组的，因此原数组中相同的值能保持它们在输出数组中的相对顺序。如果输出数组时从前往后扫描原数组，那么排序就不稳定。

8.2-3

很显然仍能正常工作，但是不稳定。

8.2-4

顺序扫描数组，统计0~k中每个数出现的次数，记录在数组C中，然后叠加C中数组的值，使得C[i]表示原数组中小于等于i的数的个数，因此落入[a..b]中的值个数为C[b] - C[a-1]，其中C[-1]=0

8.3-2

插入排序和归并排序是稳定的，堆排序和快排不稳定。为了使得所有排序都稳定，可以额外记录每个元素的在原数组中的位置做索引，比较时如果值相等再比较索引，由于有n个元素，每个元素的索引可以用lg(n)个bit表示，因此额外的空间是O(nlg(n))。但在时间复杂度的增加上，最坏情况下是每次比较都多一次索引的标记，因此时间复杂度不变。

8.3-3

如果排序不是稳定的，那么如果输入是123和133，排序最低两位时都正常，123在前，133在后，排序最高位时，可能输出123在前，也可能输出133在前，显然是错误的，因此基数排序所使用的排序算法必须是稳定的。

8.3-4

将数写成n进制表达，不妨记x的n进制表达为ab，那么x = a*n + b，其中a，b的取值范围都是0~n-1，很显然表达范围是0~n^3-1，因此只需要在两位上做计数排序，时间复杂度是O(n+n) = O(n)

8.4-2

最坏情况下，所有的n个数落入一个桶中，而插入排序的时间复杂度是O(n^2)。将插入排序改成归并、堆排序或者快速排序等时间复杂度是O(nlg(n))的排序方法即可。

8.4-3

E(X^2) = 0*1/4 + 1*1/2 + 4*1/4 = 1.5, E^2(X) = (0*1/4 + 1*1/2 + 2*1/4)^2 = 1

8.4-4

计算点与原点的距离，将(0, 1]平均分成n份，根据每个点与原点的距离放入对应的桶中，然后对每个桶中的点排序，最后输出结果即可。

8.4-5

能说得更明白点吗？不明白啥意思呢，不过我知道使用桶排序就是了……

Problems

8-2 Sorting in place in linear time

a. counting sort

b. use the partition algorithm from quicksort

c. insert sort

d. yes, use (a), it is counting sort

e. non-stable, after computing how many numbers of each 1~k value, just fill the original array the corresponding value, it's not stable, otherwise it will need O(n) additional storage

8-3 Sorting variable-length items

a. group integers by the number of digits they have, then for each group, use radix sort

b. group strings by their first character, and in each group, recursively do this for each group

8-4 Water jugs

a. for each red jug, compare it to every blue jug until finds its pair

b. for the first red jug, there may be n available blue jug; while for the second, there may be n-1;... so the total outcome number (leaf nodes) in decision tree is n!, then the height is lg(n!) = nlg(n)

c. randomly take a red jug, and compare it to every blue jug, divide them into three categories: { B<, B=, B>}; then take one from B=, compare it to every red jug, also divides them into three categories: {R<, R=, R>}, recursively do this on {R<, B<} and {R>, B>}.

worst case is that each time either B< or B> is empty, then the time is O(n^2)

关于宗教的一点迷惑

我是没有宗教信仰的，来到一个宗教信仰的国家待了几个月，看到了很多不一样的东西，有时会思考会迷惑。

宗教是什么呢？好像也没有什么严格的定义。中国大部分的人应该都是属于没有宗教信仰的，有些信基督，有些少数民族是穆斯林，也有一些天主教徒，藏族大部分人可能信藏传佛教，但是很多人家里都有香炉，都供着观音，这个算是宗教吗？在大部分人的看来这只是一种传统，一种习俗。但其实大部分的宗教何尝又不是呢？在马来西亚，这边的华人，有些会说他们信关公，有些说信观音，也有些说信道教，如果信观音信关公是宗教的话呢，那中国那八九亿的农民大部分都是信观音的，也许可以算是道教的分支吧。

或者是不是应该说宗教只是存在于内心，自己认为是是信仰就是信仰，不用非得用个框，每个人框一下，在里面就是有信仰，否则就是没信仰。这样说的话当然也没有什么不可，但是不是有点过于唯心了呢？因为对于大部分信徒众多的宗教而言，不管复杂还是简单，总是会有某些仪式，是宗教所特有的。而宗教也一般都有一些自己的教条或者主张，大部分信徒可能会遵守会去实践，当然也有些教徒会违背。也许，祈祷（礼拜）算是普遍存在的一种宗教仪式，虽然每种宗教所祈祷的对象不一样，但是可能他们祈祷的内容是差不多的，不负责任的猜测下：应该是祈祷某个神（上帝、真主、也许某个凡人？）保佑自己克服困难，让自己（也许家庭、国家、甚至世界）一切都越来越好，向神忏悔自己做错的事情，希望能得到神的原谅，询问神下一步该怎么走。可能大概是这些或类似的吧，以后要去找人问问，不过也得要问跟自己比较熟的人才行，不然可能有些人会觉得受冒犯。

我相信，是会有不少人把祈祷当作是他们生活甚至生命中非常重要的一部分，这部分人很虔诚，在青海湖边，在西藏，总能见到朝圣的信徒，他们跪着用自己的身体拥抱大地，再走到手臂伸展的地方跪拜下一次，每个人，总要去朝拜那么一座山，或者一个湖，往往需要几个月的时间，风雨无阻，他们不是做给任何人看的，每一步都是虔诚的一步，就这样一步一步。还有穆斯林，每天礼拜五次，每年还有一次斋月，这些都不是一般人能完成的。我很钦佩能完成这些仪式的人，我也相信，对践行这些仪式的人来说，这些对他们很重要，是他们生活甚至生命中很重要的一部分。

但是同时，我也相信，任何宗教中，总是会存在那么一些人，他们违背教义，也不去践行宗教的仪式，也许他们甚至想跳出这个宗教的圈子，但是由于某些原因不能。也肯定存在这么一些人，他们也祈祷，也践行着教义，但是他们仅仅是把它们当作是形式，从来就没有想过为什么要这么做，自己为什么要信这个，宗教到底给自己带来了什么。他们也许仅仅为了某些其它的目的而去重复一些宗教仪式，他们根本就不信，仅仅是为了做而做。

是不是宗教一般都是在动荡的年代产生和流行的，是不是比较容易在没有历史没有文化的地方传播发展呢？宗教是否仅仅只是用来填补人们内心的空虚呢？

所以，为什么要有宗教呢？宗教到底能给我们带来什么呢？

算法导论-快速排序

Introduction to Algorithms (third edition)

第七章：Quicksort

快速排序是分治思想的绝妙运用，提出至今，在基于比较的排序算法中，无人出其右。快排是排序算法中最重要的一种，C++库中的排序算法就是快排的变种。快排的平均时间复杂度是O(nlg(n))，最坏情况下快排的时间复杂度是O(n²)，但由于隐藏的常数项很小，所以往往是排序算法的首选，因此必须彻底理解熟练掌握。

书中给出的分割数组方法如 PARTITION 所示。将数组的最后一个元素A[r]作为参考，从左到右扫描，每次将碰到比A[r]小的元素与最左边的比A[r]大的元素交换，最后，将A[r]与最左边的比A[r]大的元素交换，从而整个数组被分为3个部分。

PARTITION(A, p, r)
1    x = A[r]
2    i = p - 1
3    for j = p to r-1
4        if A[j] <= x
5            i = i + 1
6            swap(A[i], A[j])
7    swap(A[i+1], A[r])
8    return i+1

另外一种常见的分割方法如 PARTITION-2 所示。这种分割方法左右同时扫描，只有赋值操作，没有元素的交换操作，因此一般情况下减少了元素的复制拷贝等操作，但同时增加了比较语句。需要特别注意边界条件，否则容易出错。（暂时我还没看出下面代码中的bug，如果你发现了，请务必告诉我！）

PARTITION-2(A, p, r)
01    x = A[p]
02    i = p
03    j = r
04    while i < j
05        while i < j and A[j] >= x
06            j = j - 1
07        if i < j
08            A[i] = A[j]
09            i = i + 1
10        while i < j and A[i] <= x
11            i = i + 1
12        if i < j
13            A[j] = A[i]
14            j = j - 1
15    A[i] = x
16    return i

一般的快排代码如下所示。如果数组是有序的，那么每次分割就将数组分成0, 1, n-1三部分，相当于冒泡排序，时间复杂度是O(n²)。为了解决这个问题，可以修改参考元素的选择方法，比如随机选择，或者选择3个元素，选取中间值。通过这些修改，可以改善快排在一般情况下的最坏情况时间复杂度。为什么要说一般情况下呢，因为仍然可以通过修改输入使得针对特定修改下的快排算法，其时间复杂度是O(n²)。

QUICKSORT(A, p, r)
1    if p < r
2        q = PARTITION(A, p, r)
3        QUICKSORT(A, p, q-1)
4        QUICKSORT(A, q+1, r)

Exercises

7.1-2 PARTITION 中的第4行条件永远满足，因此i一直增加到r-2，最后返回r-1；检测这种特殊情况……

7.1-3 遍历n个数，每个数上操作都是常数级别，因此复杂度是O(n)

7.1-4 change the <= in 4th line of PARTITION to >=

7.2-1 T(n) = T(n-1) + O(n) = T(n-2) + O(n-1) + O(n) = ... = O(1 + 2 + ... + n) = O(n2)

7.2-2 O(n2)

7.2-3 same like 7.2-2

7.2-4 对于基本有序的数组，插入排序只需要很少的比较次数，而快速排序则会产生较差的分割，因而导致较差的复杂度

7.2-5 对于最小的情况，每次都是走α分支，假设第m层结束，只有一个节点，因此有nαm = 1，解得m = -lg(n) / lg(α)；对于最大的情况，每次都走1-α分支

Problems
7-4 Stack depth for quicksort
a. 显然的
b. 每次都是最坏情况下的分割 0, 1, n-1或者n-1, 1, 0
c. 每次先对分割中小的数组排序，代码如下

QUICKSORT''(A, p, r)
1    while p < r    // partition and sort the smaller subarray first
2        q = PARTITION(A, p, r)
3        if q-p < r-q
4            QUICKSORT''(A, p, q-1)
5            p = q + 1
6        else
7            QUICKSORT''(A, q+1, r)
8            r = q -1

算法导论 - 堆排序

Introduction to Algorithms (third edition)

第六章：Heapsort

基于比较的排序主要有插入排序、归并排序、堆排序和快速排序。插入排序和归并排序之前的章节已有介绍，堆排序综合了插入排序和归并排序的优点，最坏情况下的时间复杂度是O(nlgn)，需要的额外空间是O(1)。堆排序使用的是大顶堆：任何节点的值都比它的子节点的值大。注意本章讨论的树，最底层高度为0，往上逐渐增加。

建堆是从最底层的非叶子节点开始，往根节点循环，这样每次处理的节点的子树都是大顶堆，只需将该节点放到合适的位置即可。建堆需要遍历upper(n/2)个节点，处理每个节点的时间复杂度是O(lg(n))，确切的说是O(h)，建堆的时间复杂度是O(n)，而不是O(nlg(n))。证明之前，需要用到一个推论：高度为h的层至多有upper(n/2^{h+1})个节点。这可以通过归纳法来证明。由此，建堆的复杂度是\sum_{h=0}^{lower(lg(n))}(n/2^{h+1})O(h) = O(n * \sum_{h=0}^{lower(lg(n))} h/2^h，由于\sum_{h=0}^{infinite} h/2^h = 2，因此复杂度为O(n)

堆排序就是利用前面的建堆算法，然后每次选出最大值再调整堆，时间复杂度是O(nlg(n)). 堆排序的一个用处就是优先队列，这个可以用在操作系统的进程调度等领域。

堆排序是一个非常有想象力的算法，最坏情况下的时间复杂度是O(nlg(n))，这点比快速排序要好，但是由于它的常数比较大，所以实际应用也不太多，可能更多的还是优先队列的应用领域。重点是要知道分析建堆的时间复杂度和排序的时间复杂度，以及堆的调整算法等。

6.1-1

满二叉树时最多，为2^{h+1} - 1，当第0层只有一个叶子节点时最少，为2^h

6.1-2

由2^h <= n <= 2^{h+1} - 1可以推得h <= lg(n) <= h+1，因此n = lower(lg(n))

6.1-3

这就是大顶堆的性质好不好……

6.1-4

只能是在叶子节点，因为叶子节点的值总是会小于它对应的内节点的值

6.1-5

是。因为所有节点的值都比子节点的值小

6.1-6

不是。7不能是6的子节点

6.1-7

lower(n/2)不能是叶子节点，否则最大的节点只可能是2*(lower(n/2) - 1) + 1 = n - 1，小于n；lower(n/2)+1必须是叶子节点，否则它的子节点至少是2 * (lower(n/2) + 1) = n + 2，大于n。因此lower(n/2)+1是第一个叶子节点

6.2-3

nothing will happen...

6.2-4

叶子节点，没有子节点，nothing will happen...

6.2-5

while i <= A.heap-size/2

6.2-6

heapify the root node, and propagates to bottom, the height is lg(n)

6.3-3

通过归纳法证明，比较复杂，略

6.4-3

都是O(nlg(n))

6.4-4

这么废话嘛……

6.4-5

很显然的，但是严格的证明就不显然了……

6.5-4

保证调用HEAP-INCREASE-KEY的时候key > A[i]，因为不知道A[i]的值究竟是什么

6.5-6

while i > 1 and A[PARENT(i)] < key

    A[i] = A[PARENT(i)]

    i = PARENT(i)

A[i] = key

6.5-7

use a global priority value

for FIFO queue, when in, use the priority value, and decrease it by 1; when out, choose the element with the largest priority value, that is A[1], and heapify;

for stack, when in, use the priority value, and increase it by 1; when out, choose the element with the largest priority value, that is A[1], and heapify.

6.5-9

用k个lists的第一个元素建堆，每次取出最大值，并将对应list的下一个值放入堆顶，调整堆，显然建堆的代价是O(k)，每次调整的代价是O(lgk)，有n个元素需要排序，因此时间复杂度是O(k) + O(nlg(k)) = O(nlg(k))

Problem 6-1

a. 不是，考虑数组[1, 2, 3]，BUILD-MAX-HEAP结果是[3, 2, 1]，而BUILD-MAX-HEAP'结果是[3, 1, 2]

Problem 6-2

a. PARENT(i) = lower((i-2)/d + 1), CHILD(i, j) = d(i-1) + j + 1

b. lg(n) / lg(d)

c. like HEAP-EXTRACT-MAX, but needs to compares to all d children, running time is O(d * lg(n) / lg(d))

d. running time is O(h) = O(lg(n)/lg(d))

e. same...

Problem 6-3

a. [[2, 3, 4, 5], [8, 9, 12, 14], [16, INF, INF, INF], [INF, INF, INF, INF]]

b. Y[1, 1] is the smallest value, while Y[m, n] is the largest value

c. take out Y[1, 1], then compare Y[1, 2] with Y[2, 1], choose the smaller, recursively run on the rest tableaus

d.

e. EXTRACT-MIN takes O(2n) = O(n) times, n^2 numbers, so the sorting time is O(n^3)

f. start from left-bottom most or right-top most

算法导论（二）

Introduction to Algorithms (third edition)

第五章：Probabilistic Analysis and Randomized Algorithms

通过人员招聘问题，引入算法的随机性分析，最好、最差、期望运行时间分析。介绍并证明随机洗牌算法。最后介绍了几个有趣的应用。

生日悖论：至少需要多少个人才能保证有50%的可能性使得其中两人的生日相同？

不妨假设一年有n(n = 365)天，人数为k。所有k个人生日不同的概率为 A(n, k) / n^k = n! / ((n-k)! n^k)，令该式小于1/2，解得k >= 23

另外，可以求近似解：假定知道i的生日，则j的生日与i相同的概率是1/n，因此期望生日相同的人数对为C(k, 2)*1/n = k*(k-1)/2n，令该式大于1，解得k>=28，也即至少28个人中，我们期望能找到两个人的生日相同。

Coupon Collector's Problem: 有b种礼券，每次收到每种礼券的概率相等，问期望收集多少份礼券之后能集齐所有礼券。

假设已经收集了i-1种礼券，则下一次收集到新礼券的概率是b-i+1/b，期望次数是b/(b-i+1)，因此第i次收集到新礼券的期望次数是b/(b-i+1)，于是集齐礼券的期望次数是1 + b/(b-1) + ... + b/1 = b(1 + 1/2 + 1/3 + ... + 1/b) = b(lnb + O(1) （调和级数收敛到lnb，可以用积分上下界方法证明）

Streaks: 扔一枚均匀（正反面出现概率相等）的硬币n次，则连续的正面朝上或朝下次数的期望是多少呢？

O(lgn)

证明比较复杂，以后再看……

人员招聘问题：假设有n个候选人，首先查看前k个候选人，记录最高分，再检查剩下的候选人，如果比之前记录的最高分要好，则雇佣该人。如果都比之前的最高分低，则雇佣最后一个人。

可以证明，雇佣到最优候选人的概率是k/n * \sum\_{i=k}^{n-1} 1/i，通过积分方法确定上下界，可以求得k = n/e时最大概率是1/e，真的很神奇！

5.1-2

RANDOM(a, b) = RANDOM(0, b-a) + a, assume 2^{k-1} < b-a <= 2^k, then invoke RANDOM(0, 1) k times, convert binary to digit, if bigger than b then drop else use

5.1-3

01 -> 0, 10 -> 1, both have probability of p(1-p), expected running time is O(1/2p(1-p))

5.2-1

if the best candidate is in 1st order, then hire one time, the probability is 1/n;

if the candidates are in ascending order, then hire n times, the probability is (1/n)*(1/(n-1))*...*1 = 1/n!

5.2-2

candidate 1 has rank i <= n-1, while all candidates whose ranks are i+1, i+2, ..., n-1 must be interviewed after the candidate whose rank is n.

\sum_{i=1}^{n-1}1/(n-i) * 1/n

5.2-3

1*1/n + 2*1/n + ... + n*1/n = (n+1)/2

5.2-4

everyone has a change of 1/n to get his own hat back, so the expected number is n * 1/n = 1

5.2-5

there are n*(n-1)/2 pairs, and each pair has a probability of 1/2 to be inversion, so the expected number of inversions is n*(n-1)/4

5.3-2

NO. for any i, A[i] will be swap to A[i+1..n], it can't stay where it was

5.3-3

NO. this will produce n^n permutations, but we just want n!, and n^n maybe can't be divided by n!

5.4-6

for each of the n bins, the probability for any bin to be empty is (1 - 1/n)^n, so the expected number of empty bin is n * (1 - 1/n)^n, as n approaches infinite, (1 - 1/n)^n approaches 1/e, so the expected number approaches n/e;

for each of the n bins, the probability for any bin to get exactly one ball is C(n, n-1)(1 - 1/n)^{n-1}1/n = (1 - 1/n)^{n-1}, so the expected number is n * (1 - 1/n)^{n-1}, as n approaches infinite, the expected number approaches n^2/(e(n-1))

Problem 5-1

a. for each INCREMENT, it has 1/(n_{i+1} - n_i) probability to increase n_{i+1} - n_i, so the expected increase value is 1, that means, after n times such operation, the expected value will be n

b. with 1/100 probability to increase 100, and 99/100 to stay the same, for each operation, Var = E(X^2) - E(X)^2 = (0^2 * 99/100 + 100^2 * 1/100) - 1 = 99. so the final Var is 99n

算法导论（一）

Introduction to Algorithms (third edition)

第一章：The Role of Algorithms in Computing

概述：算法就是对将输入转化为输出的计算过程的描述，能解决很多现实问题，对同一个问题，不同的算法有不同的效率，我们的终极目标就是为所有问题找到最有效、最优的算法。

第二章：Getting Started

由插入排序问题引入算法的正确性分析，主要分为三步：初始化、执行、结束，算法的正确性分析就是要从这三方面着手。通过分析算法的运行时间，引入O表示。通过引入归并排序，介绍算法设计中分治（divide-and-conquer）思想，并分析归并排序的时间复杂度。

Q2.3-7: 将S排序，头尾各放一指针，比较头尾指针所指的两数之和与x的大小，移动指针，直至找到所求或者遍历完S。排序复杂度O(nlgn)，遍历复杂度O(n)，总复杂度O(nlgn)。

第三章：Growth of Functions

详细介绍O、o等复杂度记法，简要介绍一些基本的数学知识，主要是理论知识介绍，不涉及算法。

第四章：Divide-and-Conqur

专门用一章来讲分治算法，可见分治思想在算法设计中的重要性。其实不仅是在算法中，在现实生活中，分治思想也是很重要的：当碰到一个难题时，不妨想想能不能将难题化小，通过解决一个个的小问题逐渐将难题解决。用最大子段和、矩阵相乘做例子，其实个人感觉用最大子段和做例子不太恰当，因为练习中也提到了存在O(n)的算法解决这个问题，所以如果用平面上的最近点对问题来做例子是不是更恰当点呢？至于矩阵相乘，这个算法确实很有想象力，但是太复杂了，不用参考书应该没几个人能推导出来那么复杂的计算方式吧？最后，给出了master定理，对T(n) = aT(n/b) + f(n)的复杂度分析给出了一般性的结论，并证明了master定理，如果不是搞算法研究的话证明这些细节就不用去看了。

4.1-1 return the largest negative value of course

4.1-5 dp[i] = max {dp[i-1] + a[i], a[i] }, O(n)

4.2-7 let X = ac, Y = bd, Z = (a+b)(c+d), then ac-bd = X - Y, ad+bc = Z - X - Y

4.3-1 T(n) = T(n-1) + n = T(n-2) + n-1 + n = ... = 1 + 2 + ... + n = n*(n+1)/2 = O(n^2)

不仅仅是台湾的野火集

很早就听说过龙应台这个人，还以为是个男作家呢，不过一直也只是听说，没有去看过她写的书。上周一个偶然的机会翻了翻《人在欧洲》，立刻就被作者的文字和思考所吸引，书里提到的一些现象我也有看到过，一些问题我也有思考过，但是一般都没有作者深入，虽然对于有些现象，作者也流露出怀疑或者矛盾的心理，但是我想作者是有自己的想法的，只是可能有些不便与表达出来或者是作者仍然在思考着应该怎么看待这个问题。虽然是写人在欧洲，但是不仅仅是欧洲，台湾、大陆都有涉及，通常都是以小见大，往往是稀疏平常的一些小事，我们可能都习以为常了，但是到了其它的国家，见识了迥异的社会文化，你才开始重新思考以前见到的总总，也许到那时，你才发现，原来这一切我们太想当然了，我们都太习惯于这些以致麻木了，也许换一种方式会更好呢，不是吗。

读完《人在欧洲》之后，就开始翻《野火集》，短短的几篇杂文，铿锵有力，以致书评都有超越原文长度的趋势。不过我一向是不怎么看书评的，就算是书评写得好，也应该另外出版啊，为什么要和原文放在一起呢，不然人们读到还以为是作者的思想呢，其实作者的所思所想都通过原文表达出来了，书评写的再好也只是再解释，也许还会有误呢，放那么多岂不是误导读者吗。

这把野火，只是烧给台湾的吗？看到有人评论上，当时大陆出版该书的时候，人们就说"这不就是在说中国嘛"，过去了差不多三十年，书中披露的问题，环境污染、城市文化建设、教育、社会民主等等，在台湾基本都得到了解决，台湾的国际地位也逐渐升高，当时的台湾向往着大陆，现在则是反过来，更多的人则是向往着台湾，把台湾视为中华文化的传承者，固然二者都有偏颇的地方，但是事实是：二十多年来，这把野火在台湾熊熊燃烧，烧掉了很多肮脏、腐败、堕落的东西，台湾逐渐走向光明与美好，走得很快；而反观大陆，我也不知道当初这把野火当时在大陆燃烧了没有，即便燃烧，应该也是淹没在其它的熊熊大火里。二十多年过去了，把《野火集》中的台湾二字改成大陆，台北改成北京，其它一字不改，这把野火就是专门为大陆而燃烧的！书中提到的所有问题，都是现在中国社会中都存在的，而且情况更加严重。环境污染：官方耗资10亿调查国家土壤问题，却定义为"国家机密"，不敢公布；2013年以来3个多月，北京只有很少的几个蓝天，发生过很多起严重的雾霾事件，以后中小学课本不用再列举伦敦的毒雾污染了，直接说北京的就可以了，大家更熟悉，更有说服力。食品安全问题：每天吃着有毒的食物，地沟油问题，奶粉，牛奶问题，现在有几个人敢喝中国造的牛奶，特别是奶粉？有能力的都是从海外买，旅游回来带的最多的不是香水化妆品，而是奶粉，为此香港甚至出台法律限制外带奶粉的数量。城市文化建设问题：到处都是推倒老旧房子，把古迹也一并推倒，然后再重新建古迹，就像是明明有一块纯天然的处女膜，非得戳破它，再做手术补一块，当然了，这能带来GDP。上哪里去寻找传统文化？仅仅是几个建筑，几块牌匾就是传统文化了吗？如果社会不尊重传统文化，谈何自己有上下五千年的中华文化？我看文化是被强奸了才对！社会民主问题：翻翻看二三十年代的人民日报和现在的人民日报，就能看出差别了。明明不是民主国家，对于别人的指责，不想着反思改进，反而攻击别人别有用心，另一方面又说自己是民主的，真的得是多精神分裂才能说出这种话，得有多无耻才能做出这些事情啊，真的是前无古人，后无来者。教育：很长时间以来，我认为这一切的根源都在教育，我也不知道对不对，如果教育能够多把一些顺民培养成公民，让更多的人有独立判断的能力，有积极促进社会进步的动力，不再畏畏缩缩，不再被洗脑，不再被灌输极权思想，这把野火应该早就燃烧起来了吧。

野火总有一天会烧起来的，你点一根火柴，火就会更旺一些，最后也就烧得更彻底！

让野火来得更猛烈些吧！

一个常见问题的推广

你可能之前碰到过下面这些问题：

1. 有n个数，其中一个出现1次，另外的数出现2次，求出现1次的那个数。

2. 有n个数，其中一个出现1次，另外的数出现3次，求出现3次的那个数。

3. 有n个数，其中一个出现2次，另外的数出现4次，求出现2次的那个数。

要求时间复杂度O(n)，空间复杂度O(1)

你应该知道第1个问题可以用异或轻松解决：将n个数作异或，剩下的那个数即为所求。

另外的两个问题就有点棘手，不是那么容易解决的。不妨再将这个问题一般化：有n个数，其中一个出现x次，另外的数出现y次，求出现x次的那个数。（通常x<y）

这个问题有一个通用的算法：将每个数写成二进制表达，对每位做加法，然后模y，则结果要么是0，要么是x。如果是0，说明所找的数在该二进制位上为0，否则为1。对所有的n个数循环32遍，即可得到所找的数。时间复杂度为O(n)，空间复杂度O(1)，满足要求。

其实，还可以对这种方法作一点改进，只需要一步循环：考虑数组m[y]，其中m[i]的二进制表达中为1的位表示在n个数在这些位上的和加起来模y的结果是i。初始化是m[0]的所有位都是1，其它m[i]都是0，之后对n个数循环，每次更新m[i]时，需要用到上一次的m[i-1]的结果，具体看代码：

int f(const int *a, int n, int y, int x)  // usually x < y

{

    unsigned int m[y] = {-1, 0, 0, ... };   // change this in actual code

    unsigned int mb;

    for (int i = 0; i < n; ++i) {

        mb = m[y-1];

        for (int j = y-1; j > 0; --j)

            m[j] = (m[j] & ~a[i]) | (m[j-1] & a[i]);

        m[0] = (m[0] & ~a[i]) | (mb & a[i]);

    }

    return m[x];

}

其中，m[j] = (m[j] & ~a[i]) | (m[j-1] & a[i])这句最关键，解释如下：当遍历到第i个数后，m[j]的第k位是1有两种可能：要么遍历第i个数之前m[j]的第k位就是1，同时第i个数的第k位为0，也即(m[j] & ~a[i])；或者是遍历前m[j-1]的第k位是1，同时第i个数的第k位为1，相加后即可得m[j]的第k位为1，也即(m[j-1] & a[i])。同时，由于计算m[j]需要用到上次m[j-1]的结果，计算m[0]需要用到上次m[y-1]的结果，所以从y-1遍历到0比较方便。

如果想明白了这个问题，那么以后碰到类似的问题就可以直接给出终极解决方案了，世界从此清静了。。。。。。

poj 1112 Team Them Up!

这道题得纪念一下，花了挺多时间的，做完回头看也不太难的，就是比较麻烦，要比较仔细。

题目大意是：有一群人，他们之间有些人互不认识，要将他们分组，使得每个组中的所有人都互相认识，并且两个组的人数之差最小，可能不存在分组满足要求条件。

很显然是一个图论的题目，将人考虑成点，不认识的人之间加一条边，则可以得到若干个连通图，对每个连通图作广度优先搜索，将互不认识的人分在不同的小组，如果此过程发现不满足要求的情况直接退出，否则就可以将所有人分成若干块，每块中有两组人员。用程序语言就是：

    S = {{X1, Y1}, {X2, Y2}, ..., {Xn, Yn}}, 将所有X和Y分成两组，满足Xi与Yi在不同的组，且两组的数量和之差最小。

这个可以用动态规划求解：

    dp(i, x) 表示第i组，第一组的数量为x时的两组数量和之差，则有递推方程：

    dp(i, x) = min (dp(i-1, x-Xi), dp(i-1, x-Yi))

因为Xi和Yi中任何一个都可以被分到第一组。

在动态规划的过程中，记录每次X和Y的分组情况即可。

读《人月神话》

本应该大三的时候读这本书的，当时软件工程课的老师也向我们推荐过，还列为课外必读的参考书，不过那会不怎么爱学习，就没有读。其实现在想想，当时就算读了，也不过是囫囵吞枣，是理解不了多少的，因为根本就没有多少的工程实践经验，很多东西根本理解不了。就跟老师当时还推荐的《设计模式》一样，其实基本上可以说是完全看不懂的，当然我现在也没看过，应该说是前几年翻过一些，不过实在是看不下去。

书中的例子年代比较久远，可能很多事物现在觉得很平常，当时就是不敢想象了，不过思想总是不会过时的，所以就算是过去了几十年，这本书仍然有众多的读者；就是是过去几十年，书中提出的"没有银弹"的观点，到如今仍然正确。

软件这个领域确实不同于以往的任何领域，比如建筑、制造等领域，在以往的领域中，流水线的发明大大的提高了生产效率，只需增加流水线，增加工作人员，虽然生产效率不会提高，但是产量会提高。而软件领域则不同，对于一个软件产品，没有人能够将它流水线化，然后每个人生产其中的一部分。对于大的软件产品而言，是可以细分成模块的，模块也能细分，但是却不能无限细分，而且模块与模块之间并不是完全不相关的，并不能像制造领域，大的产品是由小的零件组合起来，只要小零件符合规定要求，那么拿过来就能用。但是对大的软件而言，却不能这样。一个原因是大型软件是非常复杂的，没有人能够完全明白其中的每一个细节，不同的模块之间需要通信，必须组合起来测试，不能实现完全的"热插拔"。这个问题至少现在还没有"银弹"，没有人或者公司提出或实践了什么突破性的理论或技术，能够完全解决这个问题，这也导致现在大型软件非常难开发、维护代价昂贵。

另外一个就是软件开发的方法。如今，瀑布模型的应用应该非常非常少了，现在一般都是采用敏捷开发：将系统分成若干小模块分别开发，首先构建整体框架并保证系统能运行，对每个模块进行增量开发，保证任何时刻系统都是能运行的，直至最后系统的完成。其中，"保证系统任何时刻都是可运行的"这点非常重要，这也是我在2011年在雅虎实习学到的非常重要的知识。当时刚去实习，mentor让我开发一个数据显示系统，其实就是调用一些库，将数据以flash的直观方式显示出来。刚开始我的做法是实现每个小的部分，然后把它们合起来，有问题再分别改，因为我喜欢看到自己合成组装的东西一次性就能跑起来的那种很爽的感觉。很显然，过了一天仍然没做完，mentor就问题哦进度如何，我就说如何如何，mentor就问能跑起来看看吗，我就回答说我还在搭底层的模块，搭完了才能跑。mentor就教育我说应该先搭个大框架出来，保证能运行，然后慢慢添加模块进去实现完整功能，这样不仅方便调试而且开发效率更高，因为系统一旦能运行，不管运行结果是对还是错，至少是从0到1的突破，对开发人员的激励作用是很大的，现在大型的软件及互联网公司基本都是采用这种开发模式。后来的经历也让我更加深刻地理解了这种思想。

几十年过去了，软件领域出现了一些新的编程语言，新的编程开发工具，在很大程度上提高了软件的开发效率，现在人们能以更高的效率开发更大型的软件。但是本质问题仍然没有解决，能否像传统工程领域一样，增加人手就能提高对应的产出？什么时候能够实现软件的组装：可以从市场是购买相应的小模块，组合成复杂的软件系统？真正到了这个时候，软件也就实现了流水线生产，《人月神话》也就可以扔了。

会有这么一天吗？

求割点与割边的算法

以下的讨论基于无向连通图。假设图G中点个数为n，边数为m

割点（Articulation Point）：去除该点后图变成非连通。

割边（Bridge, cut edge）：去除该边后图变成非连通。

首先考虑求割点的算法。

根据定义，首先想到的算法就是遍历图中所有的点，每次去除该点及对应的边，检测图是否连通（可用DFS或BFS）。该算法的时间复杂度为O(n*(n+m))

另外由Tarjan提出的算法的原理是：

对图作DFS遍历得到一棵树T，一个点u属于割点的充分必要条件是：

    1. u是T的根节点，也就是DFS访问的第一个点，并且u有至少两个孩子节点

    2. u是T中其它节点，u至少存在一个孩子节点v，通过v及其任何子树不能访问到u的任何祖先节点

其中，条件1很明显，也很容易编程实现；至于条件2，在DFS中，我们需要记录每个节点通过它的子节点能访问到的最早的节点。

为此，用一个数组d记录图中每个节点被DFS访问的顺序，另外一个数组low记录每个节点通过它的子节点能访问到的最早的节点，因此有：

low[u] = min(d[u], d[x] (x是通过u的子树能访问到的所有节点))

       = min (d[u],

                    d[v], (u, v)为后向边（返祖边），等价于d[v] < d[u]且在DFS生成树中不是u的父亲节点

                    low(v), (u, v)为树枝边（父子边），u是v的父亲节点

              )

因此，割点的充分必要条件即是：

    1. u是T的根节点，且u至少有两个孩子节点

    2. u不是T的根节点，(u, v)为树枝边（u为v在搜索树中的父亲），使得d[u] <= low[v]

如果图是用邻接表存储的话，时间复杂度是O(n+m)

对于割边的问题，基于同样的算法，一条边是割边的充分必要条件是：

    1. (u, v)是树枝边，u是v的父节点，low[v] > d[u]

最后，推荐一个不错的参考资料：slideshare-articulation

记录，是为了更好地理解

读了很多书，看了很多书，很多知识以为自己理解了，但是却无法向别人解释明白。如果一个知识点，你不能向专业内的其他人讲明白，更无法向专业外的人讲明白，那说明你对知识没有完全掌握，理解还不透彻，也许在某些情况下你能运用它，但是换一个场景或者改一点背景，你可能就不能运用自如，因此从现在起，要逐步将所学的知识，用自己的语言再重新写一遍，如果能够在不看参考资料的情况下，自己写出来，那么就说明自己暂时算是弄真正弄明白了。

就像武侠小说中学武功，如果仅仅是将招式什么的记住，却不能融会贯通，那就只能表演而已，不能用于实战。

多记录，加深理解，变强大。

何必那么纠结

其实不必考虑那么多，何必那么纠结呢，对自己，追求完美，不断超越自己；对别人，多一点宽容，不必要求别人跟你一起进步。

如此简单的问题，怎么就是想不明白呢……

悲催的处女座

星座这个东西其实是信则有，不信则无的。

处女座的人是以挑剔出名的，其实挑剔本身无所谓对错，关键是自己的位置和挑剔的对象。

从小到大，我的朋友都不多，一个原因是小时候只知道读书，玩的比较少当然朋友就少点；另一个是兴趣爱好特长比较少，俗话说臭味相投，没什么特长的话朋友也会少很多，因为世人交朋友或者是共鸣或者互补，别人跟你找不到共鸣，你也没有什么能帮到别人让别人欣赏的，别人何苦成为你的朋友呢；再一个就是喜欢挑刺。回想起来，我也是有过不少好朋友的，但最后都因为吵架或者什么原因谁也不肯先道歉就不了了之了。

我所见过的绝大部分人，或者说所有人，应该是通用的，只要不是圣人，当然圣人谁也没见过所以拿出来说是没有意义的，都是喜欢听到别人的赞扬，不喜欢你说他们的缺点，即便这些缺点很明显，当然不同的人的忍耐程度不一样，一般情况下是与你跟他的亲密程度成正比的。想想也是，如果一个人有事没事说你这也不对，那也不对，即便这些事情真的是不对，我可能还会想"你他妈谁啊，轮得到你说吗？"，所以说，不要轻易说别人的不对，即便这件事情他们真的不对，除非你到了一个比较高的位置，大家都很尊敬你，而且越是社会地位（这里用社会地位可能有点不合适，也许你会拿人人平等来说事，我没有看不起人看不起某些工作的意思，只是确实有某些人某些事情在普通大众的眼里就是比较低贱，只不过他们不承认罢了）比较低，自尊心就更加脆弱，更加受不了别人的批评指正。

以前虽然我也知道这个道理，我也被提醒过不要总是挑刺，要多看到事情的正面，看到一些闪光点，多说一些积极正面的东西，这样别人也会喜欢你，因为没人会喜欢听你抱怨，大家都喜欢跟积极乐观的人相处。但是我真的是天性如此，虽然我也做了一些改变，但还是不彻底，加上以前的环境大家都是比较明事理的人，一般情况下都是就事论事，所以还不太有所谓。只不过现在有一些变化。现在的工作需要跟很多公司部门不同等级的人打交道，有一项机制是大家每天填一张卡片，记录你看到遇到的不爽的事情，比如说食物比较难吃，房间打扫不干净，某项工作流程不对之类种种。一开始我还天真的想这个机制真不错，大家一起来挑刺，每天改进进步一点点，世界也就会变成美好的明天。但是，我没有想到，真的没有想到，执行这些工作的都是人，实实在在的有血有肉的人，而不是机器人，人都是有感情的，都是不喜欢批评的，都是喜欢别人的夸奖，所以一旦他得到一个举报，即便他知道这只是针对某件具体的事情本身，但是他不会仔细去区分，他也许觉得没必要，一旦他知道是你写的，立刻他就会针对你，以后也许你有需要他帮忙的地方，即便那是他的本质工作，他也可以拖拖拉拉，甚至故意做错。人的优越感不是来源于自己有多好多幸福，而是别人比自己更差。因此，为了跟他们打交道，你就必须写他们的好，即便那是他们的本质工作，当然这也是有正面作用的，因为一般来说，被表扬的人一般情况下都会把工作做得更好，当然也有骄傲做得更差的情况，只不过对成年工作的人来说，后一种比较少见而已。

这些事情跟我内心的信仰是冲突的，但是为了工作为了生活，很多时候必须妥协，向它们低头，而我是一个不喜欢低头的人。那就暂时这样吧，等我变得强大了，一切是不会就会不一样呢？

你也许会说，这世间是有很多不完美的地方，但是还有很多美好阳光积极美丽的地方呢，你就不能看到吗？当然我是看到的，但是一般情况下我都把它们当成理所当然，我认为世界本该如此，唯有不断改进才能变得更完美，让一切变得更完美不好吗？

如果所有的一切都完美了，是不是会更好呢？Matrix里创造matrix的老头说，之前建造的世界是完美的，所有人都健康，没有事故，大家的需求都能得到满足，本以为会一直完美下去，但是这个世界却很快终结了。反倒是有着疾病，饥饿的世界能延续更长的时间。《三体》里也有类似的情节，最初的十维（还是十二维？九维？）宇宙中，光速是无穷的，人与人之间没有距离，想去哪里一瞬间就能到，不用向现在这个三维宇宙一样需要那么长的时间，从某个方面来说，这个宇宙确实是完美的，但是很快（其实是没法统计时间的，因为光速无穷，也许没有时间），这个宇宙就毁灭了，之后每下降一个维度，光速慢下来，宇宙存活的时间就更长些。也许宇宙最终是要走向灭亡的，只不过光速慢下来拖慢了它的速度而已。

完美是什么，该不该追求完美？该怎么追求？

面朝大海，春暖花开

从明天起，做一个幸福的人

喂马、劈柴，周游世界

从明天起，关心粮食和蔬菜

我有一所房子，面朝大海，春暖花开

从明天起，和每一个亲人通信

告诉他们我的幸福

那幸福的闪电告诉我的

我将告诉每一个人

给每一条河每一座山取一个温暖的名字

陌生人，我也为你祝福

愿你有一个灿烂的前程

愿你有情人终成眷属

愿你在尘世获得幸福

我只愿面朝大海，春暖花开