0. 前提条件

自己是学生，具有edu.cn或edu的邮箱。如果没有的话，据说使用学生证也可。

1. DigitalOcean上VPS的作用

DigitalOcean就是卖虚拟机的，包括全球多个机房（如旧金山、纽约、新加坡等）。用户购买虚拟机可以干很多事情，包括但不限于：

• 安装shadowsocks穿越防火长城GFW。从此，无障碍访问互联网；
• 部署个人博客/网站；

2. 免费/低价使用的步骤

1) 获取Github Student Developer Pack

Github为学生提供了很多福利，包括100刀的DigitalOcean券，免费注册.me域名（一年）等等。

首先，访问https://education.github.com/pack，获取自己的pack（使用edu/edu.cn的邮箱）。

然后，在DigitalOcean那一项获得100刀的促销码。

2) 注册DigitalOcean账号

访问https://www.digitalocean.com/?refcode=65b0f33ddec8注册DigitalOcean账号。前面这个注册链接带了我的推荐小尾巴，使用我的推荐链接注册你可以额外获得10美刀。当然也可以直接搜索官网，然后注册。但是，不会有这10美刀。

注册完，在Billing页面输入刚刚获取的100刀促销码。此时，账号里已经有110刀（推荐链接送10刀 + 100刀促销码），但账号并没有激活。

3) 激活DigitalOcean账号

一共有两种方式，使用双币信用卡免费激活或者使用PayPal付5美元激活。如果使用信用卡，那么就可以免费激活账号（认证信用卡时会临时扣钱，但会退还）。后期只要账户里有余额，使用没超，就不会扣钱。我选择了使用PayPal付5美元注册。

访问https://www.paypal.com/c2/webapps/mpp/get-started注册PayPal账户，账户类型选“个人”。注册完以后就可以使用银联卡进行美元支付，跟平时使用支付宝一样一样的。但是需要注意的是不能使用中国银行的长城借记卡，PayPal会识别为Discover的一个卡。这是因为长城借记卡的卡号没有按照银联标准走。5美元约合人民币30元多一点点。

4) 购买虚拟机(Droplets)

可以在多个机房中选（我选了旧金山机房），也可以选择多个实例。如果选择最便宜的5美刀的实例，那么账户里100多刀就可以用20多个月。

我购买虚拟机后，目前只是安装了shadowsocks。看优土鳖，vimeo上的视频还是很流畅的，基本无卡顿（教育网）。从此，自由上网。

使用免费的Goagent自由上网存在一些安全风险，见：http://www.williamlong.info/archives/3882.html

基本纲领

树形结构的特征很明显：子树也是树（废话）…所以，首先要想到的解法就是递归。然后具体方法又分为自顶向下（Top-down）和自底向上（Bottom-up）。

图的算法就那么多吧…这章就一个图的题。

4.1 实现一个函数判断一个二叉树是不是平衡的。

• 解法1：一个函数求树的高度，然后判断当前树是否平衡。如果平衡就判断子树是否平衡（Top-down）。这个解法的缺点是重复访问底层的节点。
• 解法2：递归到最底层，然后从下往上计算各个节点的高度（不需要单独一个函数计算）。然后再从底向上判断树是否平衡（Bottom-up）。 优点就是每个节点只会访问一次。

代码在此

4.2 判断图中两个节点的连通性

可以使用BFS和DFS。代码在此

4.3 通过一个有序数组创建二叉搜索树，使得其高度最低（平衡二叉树吧）

方法很简单，选中间的节点作为根节点，然后使用前半段区间递归生成左子树，后半段区间生成右子树。代码在此

4.4 将树的每层节点串起来成D个链表，D是树的高度

这里显然要用到层次遍历。但是要稍微修改下传统的层次遍历。由于这里最终结果是D个链表，那么就不需要使用队列了。用链表模拟队列。同时维护两个链表。一个链表包含当前这层的节点，另一个链表包含下层节点。然后一层一层往下。将每层节点的链表直接添加到result中。代码在此

4.5 检查一个二叉树是否是二叉搜索树

• 解法1：自顶向下，维护一对minVal和maxVal。只有当前节点的值在这个区间，才是二叉搜索树。
• 解法2：使用二叉搜索树的特性。它的中序遍历必然是有序的。然后只需要一个变量指出它的前驱节点就好了（通过中序遍历）。当前节点需要大于（或等于）其前驱节点。

代码在此

4.6 需找二叉搜索树中一个节点的后继

后继就是：1）如果有右子树，那么右子树最左边的节点就是其后继。2）往父节点走，第一个右父节点（自己体会下右父节点的意思，第一个向右走的父节点）就是其后继。

代码在此

4.7 寻找两个节点第一个共同祖先，不使用某数据结构存放额外节点

情形一：节点中包含parent指针

书上描述的太复杂，实际上有个很简单的解法：把parent当做list的next指针。然后需要做的是：1）找到node1的root节点，并将他们连成一个环：root->parent = node1；2）现在问题就变成了node1和node2是否相交，如果相交，找出第一个相交节点。就是进入环的节点。解法就很简单了，list里做过的。完事后记得还原root->parent。

情形二：节点中不包含parent指针

• 解法一：自顶向下。1）写个函数covers判断某树是否包含某节点)； 2）判断左子树是否包含node1，右子树是否包含node2。如果是这样，那么root就是第一个祖先了；3）如果不是，那么遍历包含两个节点的子树。缺点就是重复访问底层节点。
• 解法二：自底向上。我想的，跟书上不太一样。用一个元祖(p1, p2)维护包含(node1, node2)的祖先。从最底层开始（初始(null,null))。直到某个节点p1和p2都不再是nullptr。那么就找到第一个公共祖先了。

代码在此

4.8 两个二叉树：T1有百万节点，T2有数百个节点。判断T2是否是T1的子树（注意，中间那一部分是不能叫子树的）

• 解法一：这是根据树的性质来的，如果是子树，T1那么两种遍历（前序+中序，其他也可以）产生的字符串里必然包含T2的遍历结果。这种方法快（O(m + n)）。但是需要大量的空间（O(m + n))。
• 解法二：自顶向下。写一个函数判断两棵树是否相同。然后依次判断T1是否和T2相同，T1的子树（左右）是否和T2相同。这种方法慢（最差O(mn)），但需要的空间小（递归产生的空间O(log(m) + log(n)))。
• 解法三：有更好的解法么？题目强调了百万，就在想是不是有更好的解法。最开始想的是解法二，以为这是很笨的解法。结果答案里也是这解法…

代码在此

4.9 二叉树的节点包含一个数值，设计个算法，打印一条路径使得它的总和等于一个给定值。这条路径不需要从root开始或以leaf结束

• 解法一：自顶向下。用数组维护自开始节点以来的路径，只要结果等于sum就打印路径，一直遍历到null。然后开始回溯，直到数组为空，然后设定子树的根节点为起始节点，重复操作。这个解法会重复访问底层节点。
• 解法二：自顶向下。优化上面的解法，使得不需要重复遍历节点。使用数组维护自根节点到当前节点的path，然后在path里从后往前累加，只要累加值等于给定的值，就打印这个path。所有节点只需遍历一遍。

代码在此

总结

树的题目一般有两个解法：自顶向下和自底向上：

• 自顶向下解法直观，但通常会重复访问底层的节点。
• 自底向上需要维护额外的变量，用来纪录底部以来的状态。好处是通常只遍历每个节点一次。

Arena可以单次申请内存，但不能单次释放内存。只有当Arena析构时，才会释放所有申请的内存。另外，Arena允许浪费内存，所以整个Arena的实现就很简洁。

1
2
3
4
5
6
7
8
9
10

inline char* Arena::Allocate(size_t bytes) {
  assert(bytes > 0);
  if (bytes <= alloc_bytes_remaining_) {  //如果有足够的剩余内存，就直接分配
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }
  return AllocateFallback(bytes);  //否则就从新分配的一块内存里分配
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

char* Arena::AllocateAligned(size_t bytes) {
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8; //最小8字节对齐
  assert((align & (align-1)) == 0);   // Pointer size should be a power of 2
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1); //当前指针超出对齐边界的字节数
  size_t slop = (current_mod == 0 ? 0 : align - current_mod); //需要调整的字节数
  size_t needed = bytes + slop;
  char* result;
  if (needed <= alloc_bytes_remaining_) { //有足够的剩余内存，就直接分配
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  } else {
    // AllocateFallback always returned aligned memory
    result = AllocateFallback(bytes);  //否则就从新分配的一块内存里分配
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
  return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

static const int kBlockSize = 4096;

char* Arena::AllocateFallback(size_t bytes) {
  if (bytes > kBlockSize / 4) {  //申请大内存，就直接申请一块
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  //前面剩余的内存就浪费掉了
  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}

1
2
3
4
5
6

char* Arena::AllocateNewBlock(size_t block_bytes) {
  char* result = new char[block_bytes];
  blocks_memory_ += block_bytes;
  blocks_.push_back(result);
  return result;
}

1. 牛顿法

先猜一个初值，然后依次迭代，直到结果足够精确。比如求number的平方根：

• X0 = guess
• X1 = (X0 + number / X0) / 2
• X2 = (X1 + number / X1) / 2
• ……
• Xn = (Xn-1 + number / Xn-1) / 2

结束条件可以是 abs(Xn * Xn – number) 小于某个数，或者两次迭代结果 abs(Xn – Xn-1) 小于某个数.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <cmath>
#include <limits>

using namespace std;

double sqrt_newton(double x)
{
    if (x <= 0)
        return x;

    double val = x, prev;

    do {
        prev = val;
        val = (prev + x / prev) / 2;
    } while(abs(val - prev) > numeric_limits<double>::epsilon());

    return val;
}

注意：上面这个代码不能使用第一个条件判断。因为此时求sqrt_newton(3)时，abs(val * val – x)最后一直是4.44089e-16，而numeric_limits::epsilon()是2.22045e-16。这样就导致了死循环。这应该是由于浮点数的精度问题导致的。 如果要使用第一个条件，可以用 abs(val * val – x) > 0.00000001。

2. 二分法

二分法就是每次取中间的值，然后比较。直到结果足够精确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

double sqrt_bi(double x)
{
    if (x <= 0)
        return x;

    double low = 0, high = x;
    double mid = (low + high) / 2, prev;

    do {
        if (mid * mid > x)
            high = mid;
        else
            low = mid;

        prev = mid;
        mid = low + (high - low) / 2;
    } while(abs(mid - prev) > numeric_limits<double>::epsilon());

    return mid;
}

3. 不知所云法

QUAKE-III里用来计算1/sqrt(x)的算法，速度快。 这里的float不能改成double，改成double就不对了。

还有个问题是，下面这个算法求出的结果精度会有点问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

float sqrt_magic(float x)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5;

    x2 = x * 0.5;
    y = x;
    i = * (long *) &y;
    i = 0x5f3759df - (i >> 1);
    y = * (float *) &i;
    y = y * (threehalfs - (x2 * y * y));
    y = y * (threehalfs - (x2 * y * y));

    return 1 / y;
}

补充知识：C++中的numeric_limits

numeric_limits定义于limits头文件中，主要用于取代C语言中limits.h中的那些宏。具体见它的参考页面

比如，

• INT_MAX和INT_MIN使用numeric_limits<int>::max()和numeric_limits<int>::min()代替。

• DBL_EPSILON使用numeric_limits<double>::epsilon()代替

References：

[1] 一个Sqrt函数引发的血案

[2] 维基百科-牛顿法

重点推荐1.8

1.1 查看字符串中的字符是否唯一的，如果不使用额外的数据结构怎么做？

A： 核心思路是记录每个字符出现的次数，如果某个字符出现第二次，就返回false。否则返回true。有下面3种解法，代码在此:

• 最简单的方法是使用Hash表。
• 因为字符最多只有256个，可以用一个包含256个元素的bool数组。
• 使用位图，只需要256位，也就是大小为32的char数组。

1.2 实现void reverse(char *str)

A: 使用前后指针同时操作。但这个函数必须保证str是字符数组，而不能是字符串常量。比如reverse(“haha”)就会报段错误。正确的函数应该是返回一个指向reversed字符串的指针。代码在此

1.3 给定两个字符串，判定一个字符串是否是另一个字符串的排列

A：借用1.1的思路，使用包含256个元素的数组，统计两个字符串上的元素是否都一样。代码在此

1.4 写一个函数将所有的空格替换成%20

A：先统计有多少个空格，从字符串尾部开始将字符移动到正确位置，当遇到空格时，就使用%20替换。简单的题目要写出bug free的代码。代码在此

1.5 压缩字符串，如果压缩后的长度不比原来的字符串短，就返回原来的字符串。比如aabcccccaaa –> a2b1c5a3

A：基本思路就是查看邻近的字符，相同就增加计数，不同就添加到压缩串里。（这里要注意边界条件，比如最后一组等）代码在此

1.6 将N×N的矩阵顺时针旋转90度，最好在原地进行。

A：这道题的主要思路就是找到旋转时，4个点的关系。旋转是一层一层来，从最外层到最里层。可以通过实例来推导关系，比如一个4×4的矩阵：

• (0, 0) –> (0, 3) –> (3, 3) –> (3, 0) –> (0, 0)
• (0, 1) –> (1, 3) –> (3, 2) –> (2, 0) –> (0, 1)
• (0, 2) –> (2, 3) –> (3, 1) –> (1, 0) –> (0, 2)
• (1, 1) –> (1, 2) –> (2, 2) –> (2, 1) –> (1, 1)

总结关系如下：

• i = （0, 1, …), j = (n – 1, n -2 , …), i < j。i最多只到一半的行，因为后半行已经旋转过了。j代表外面的层
• k = (i, i + 1, …, j – 1)。k是每一行的元素。
• l = n – k – 1。即l + k = n – 1。

通用关系如下(i, k) –> (k, j) –> (j, l) –> (l, i) –> (i, k)。有这个关系，代码就很简单了，在此

1.7 如果M×N矩阵中，有一个元素为0,那么就将该行该列都清0

A：书中的解法需要O（n）的空间，实际上解法可以优化到O（1）空间，即使用第0行和第0列来记录某一行某一列中是否有0.但是需要注意的是需要单独统计第0行或第0列中最开始时是否有0,这样需要清空第0行或第0列。如果不加以区别，会有额外的元素被清零。代码在此

1.8 给定两个字符串s1和s2,判断s2是否可以通过s1旋转而来（只使用一次isSubstring)。比如waterbottle是由erbottlewat旋转过来的。（重点推荐)

A: 这道题没想出只调用一次isSubstring的方法。。不过看了答案后，又学到一招。

常规方法是依次遍历s1，然后判断前后两部分是否都是s2的子串。但这需要调用太多次isSubstring了。

书上精妙的解法： 假设 s1 = xy, 如果s2由s1旋转而来，s2 = yx 那么两个s1拼接起来就是： s1s1 = xyxy，从这里可以看出s2是s1s1的子串。太妙了！！！代码在此

LevelDB的核心代码很短，1W行不到的样子。注释详细，可以用来学习C++在实际工程项目上的用法。

安装LevelDB

安装很简单，环境为Ubuntu 12.04

1
2
3
4
5
6

git clone https://code.google.com/p/leveldb/
cd leveldb
make
sudo cp -r include/leveldb /usr/local/include/
sudo cp -r libleveldb.so* /usr/local/lib/
sudo ldconfig

简单试用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include "leveldb/db.h"
#include <iostream>

using namespace std;

int main()
{
  leveldb::DB *db;
  leveldb::Options option;

  option.create_if_missing = true;
  leveldb::DB::Open(option, "/tmp/leveldb_t", &db);

  string key = "Name";
  string value = "Like";
  db->Put(leveldb::WriteOptions(), key, value);

  key = "Major";
  value = "Computer Science and Technology";
  db->Put(leveldb::WriteOptions(), key, value);


  string ret_s;
  db->Get(leveldb::ReadOptions(), "Name", &ret_s);
  cout << "key = Name" << endl
       << "value = " << ret_s << endl;

  db->Get(leveldb::ReadOptions(), "Major", &ret_s);
  cout << "key = Major" << endl
       << "value = " << ret_s << endl;
  
  delete db;
  return 0;
}

编译运行也很简单：

1
2

g++ test.cpp -lleveldb
./a.out

References：

[1] Google LevelDB 試玩心得

依赖包：numpy, matplotlib, statsmodels

• 可以使用sudo apt-get install python-numpy python-matplotlib安装前两个
• ubuntu 12.04里没新版的statsmodels，使用pip安装。它依赖于pandas和patsy，都可以通过pip安装

实现代码借鉴于参考文献[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#!/usr/bin/env python
# encoding: utf-8

import numpy as np
import statsmodels.api as sm
import matplotlib.pyplot as plt
import sys


def cdf_plot(data, name, number):
    """
    data: 一组数据
    name: 在legend上显示的名称
    number: 数据最大最小值之间划分多少段
    """
    ecdf = sm.distributions.ECDF(data)
    x = np.linspace(min(data), max(data), number)
    y = ecdf(x)

    #plt.step(x, y, label=name)
    plt.plot(x, y, label=name)


def main():
    for f in sys.argv[1:]:
        data = open(f).readlines()
        data = map(float, data)
        cdf_plot(data, f, 100)

    #plt.xscale('log')
    plt.legend(bbox_to_anchor=(0.65, 0.3), loc=2, borderaxespad=0.)
    plt.show() #显示CDF图

if __name__ == '__main__':
    main()

将代码保存为cdf.py，即可运行。后面跟几个文件，每个文件全是数据

1

./cdf.py data1 data2 data3

References

[1] How to plot empirical cdf in matplotlib in Python?