刷OJ的技巧

在三星广研待了四年，兼任了两年半内训讲师，其实整理过很多培训资料，却因为安保绝大多数无法带走。里面无关保密部分，一直想重新整理出来，留一个记录。

可仅凭手头遗留的一些纸质资料和记忆，时隔越久越难恢复了。只能怪我在三星期间没有坚持回家写技术博客。

先从容易的开始吧。
我写过一篇汇总，主要是在OJ系统上刷题提交 以及 应对三星内部软件考试的技巧，部分是针对考试的小聪明，但也有很多其实是通用的coding技巧。因为是针对当时的学员常见错误写的，内容很乱没什么章法。以下是整理恢复的正文：

1 测试数据的输入输出重定向

很多人在调试的过程中，都是一个字符一个字符地手动输入测试数据，然后对着小黑窗一个一个地核对答案的正确性。

这样做缺点很明显：

  • 效率低，容易出错（包括输入输错，和输出核对出错）
  • 没有办法测一些压力比较大的数据，譬如问题范围达到千级别，手输基本没法测
  • 一些数据修改之后又重新测，反复手敲浪费时间
  • 代码修改前后的输出结果很难比较

解决方法就是，将输入输出重定向到文件上。

这样做，输入数据生成一次可以反复测，需要大的测试数据，可以写一个for循环加随机数生成放文件里。

输出的结果，可以每次换一个文件名存着，方便前后对比代码修改的效果。

上代码：

1
2
3
4
#include <stdio.h> // freopen() 就包含在这个库里
freopen("in1.txt", "r", stdin);
freopen("out1-1.txt","w", stdout);

2 输出缓冲区置空

这个官方的代码模板里一般都自带，但是很多人不知道它放在那里干什么：

1
setbuf(stdout, NULL);

其实这段代码的作用就是把输出缓冲区置为空，这样任何输出都会马上输出到终端或者文件。

如果程序能保证执行完，那么这个缓冲区的大小是不会影响最终结果的，只是缓冲区大的话会减少输出的频率，提高一点点IO的效率。

但反过来，如果程序可能有潜在的bug，不一定能执行完，那么把缓冲区置空就能尽可能地输出已经完成的结果，尽可能地多拿一部分的分（由于新的考试形式只有一题，而且要求全对，这个技巧可能没有用武之地了）。

3 调试宏

有些题目比较复杂，需要额外增加一些log来调试。但往往调试完大家会忘了把log给 注释掉/删掉，以至于有多余输出引起答案错误。而即使你记得，从复杂的代码中一点一点地把log找出来也是吃力不讨好，还容易漏。

这时候，把调试代码加上条件编译，并用宏控制开关，就是比较省力的做法了：

1
2
3
4
5
6
7
8
9
#define DEBUG (1) // before you submit, change it to 0
...
#if DEBUG
// do something for debuging
#endif // DEBUG

一般的题目，我个人喜欢用 DEBUG_IO 和 DEBUG_LOG 两个宏，分别控制IO重定向（见技巧1），和log的输出。

这种技巧在生产代码中也是随处可见的，所以大家应该不难理解，只是有时候想不起来把它用起来。

4 “函数” 宏

对于一些反复出现的算式，手敲累且容易错，写函数又显得没必要，可以写成宏的形式。

如两者取较大值：

1
#define MAX(a, b)   ((a) > (b) ? (a) : (b))

不过，请注意：

  1. 这终究不是函数，只是宏展开（相当于预编译器做了一次查找替换），实际行为跟函数差异很大，如果复杂的式子，请还是写成函数；如果使用C++，可以写成 inline 的形式。
  2. 为了避免展开后优先级的问题，请务必在变量外加一层括号。这不仅在这里推荐，所有宏都推荐这样做，来保证在最终展开的地方能够有正确的优先级。

试考虑这样的宏：

1
2
3
#define MULTIPY(a, b)   (a * b)
int res = MULTIPY(1 + 2, 3 + 4)

res 的结果是多少？ 3 * 7 = 21 吗？
实际上展开之后的表达式是int res = (1 + 2 * 3 + 4) , 因为乘法优先，结果是11。

如果写成以下的样子就不会有问题了：

1
#define MULTIPY(a, b)   ((a) * (b))

5 规避比较语句中误用等号

*该技巧出自《C专家编程》

试看这样一段代码：

1
2
3
4
5
6
7
8
9
// count the number of 7 in array
int count = 0;
for(i = 0; i < len; i++)
{
    if(array[i] = 7)
    {
        count++;
    }
}

很普通的一段统计次数的代码。

一切看起来都很正常。

大家先不要急着往下看。

看完这段代码，大家能第一时间发现问题吗？

……

if(array[i] = 7)

这个判断永远是真的（这个语句取左值，也就是array[i]的值。而array[i]被赋值成7，在C里面，非零的量都当做真），
所以结果是，数组的所有元素都成了7，也统计了数组大小这么多个7……

如果养成习惯，在比较时将 常量 / 字面量 放在前面，像这样：

1
2
3
4
5
6
7
8
9
// count the number of 7 in array
int count = 0;
for(i = 0; i < len; i++)
{
    if(7 = array[i]) // !!compile error here
    {
        count++;
    }
}

因为常量 / 字面量 不能被赋值，所以是会直接编译失败的，而且编译器还直接指出了错误的行数。

6 预先计算 + 查表 大幅减少程序运行时间

*该技巧出自《Code complete》

在算法里，预先计算（Precomputation）是指在实际运行程序之前，使用初始化运算，生成一个查询表（lookup table）供算法引用，以避免每次运行程序时重复计算这些数据。
——翻译自英文维基Precomputation词条

假设内存用之不尽，又有足够的时间提前准备，那么速度最快的算法应该就是 “预先计算 + 查表” 无疑。

试想我们已经有了所有情况的答案，你一问，我马上就能回答。

“无限内存 + 无限准备时间” 这个前提当然是不可能成立的，所以我们也没办法拿这种做法当万金油。

但是对于某些特定问题，可能的情况如此之少，以至于我们可以把 中间结果 甚至 最终结果 先存起来，运行时直接查表。

筛选素数 是 比较经典的例子。

假设我们的任务要 判断 1’000 个 1’000’000（不用数0了，一百万） 以内 的自然数是否素数：

  1. 如果逐个判断（对每个数，判断 每一个 比它小的数能否整除），显然太慢了。
    （时间复杂度为O(n*k)，空间复杂度为O(1)，其中k = 1’000, n = 1’000’000，下同）
  2. 如果预先计算并保存每一个数 是否 素数，时间上变成了可以随机访问马上得到结果，但显然太浪费空间了。
    （一百万大小的数组，只有其中1’000个元素有用。时间复杂度成了O(k)，空间复杂度又成了 O(n)）
  3. 其实素数的分布相当稀疏，在 一百万以内，一共只有78’498个 素数 （7.85%）。如果我们按顺序存储这些素数，然后拿到一个数之后再数组里折半查找，就可以知道这个数是否素数了。
    (时间复杂度为 O(k * log m)，空间复杂度为O(m)，其中m = 78’498, log m 约为 16)
  4. 可是如果给的内存限制，连78’498个数都存不下呢？其实存168个就够了。
    1’000以内的素数一共168个。对于任意一个数x, 2 到 根号x 之间的所有素数，构成了对 x 的素数筛。换言之1’000以内的素数，就构成了1’000’000这个范围的素数筛。
    所以这168个素数，足以筛选一百万以内的任意一个整数。
    （时间复杂度为 O(k * l)， 空间复杂度为 O(l)，其中 l = 168）

如果你追求 极致的时间要求，内存随便，当然可以选择方案2。
还是 追求时间尽可能短，但内存不够 方案2的要求，可以选择方案3。
但多数情况下，方案4是 在 时间 和 空间 都比较平衡 的一个方案。

这个例子同时也说明了，很多时候不存在完美方案，即使算法，也是各种资源的折衷。需要根据面临的主要矛盾，来选择合适的解决方案。

顺便附上一个输出素数的小脚本。（预先计算因为没有语言限制，建议使用Python, js 等易于编写功能强大的 动态脚本语言。考虑到大家可能没有Python坏境，这里给了一个js的版本。）
原理很简单，初始化一个 素数筛，里面一开始只有2（换言之，只能判断不大于4的数是否素数）。
然后从3开始，对每个奇数（除2以外的偶数都不是素数）用素数筛筛一遍，如果是素数，就加入素数筛。
代码足够短小简单（很容易背下来），效率也还过得去，正好可以在需要 素数表 的题目里，用来做预先计算。

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
// js script
// for given range, return all prime numbers that not greater than range
function getPrimeNumList(range) {
    var list = new Array();
    list.push(2);
    var n = 3; // the num start to be tested
    while (n <= range) {
        var i = 0; // list index
        var r = Math.sqrt(n); // square root of n
    
        while (list[i] < r) {
            if (n % list[i] == 0) // if n can be divided, break
                break;
            else
                i++;
        }
    
        if (list[i] > r) // if list[i] > r, it means that never break
            list.push(n); // n is a PRIME number
        n = n + 2;
    }
    return list;
}

7 表驱动法 实现状态转移

*该技巧出自《Code complete》

查表法 除了可以用来引用 预先计算 的数据，还能用来实现状态的判断转移。

大多数场合，连续的 if-else 或 switch-case，都是不断复制黏贴的类似代码片段。
这样的代码，一旦需要修改，要在多个地方做类似修改，可维护性非常差。
实际上这是没有好好 运用 合适的 数据结构 的结果。

而将状态之间的映射关系 预先 存放在 表里面，并实现维护一段查表的算法，正是对“数据结构 + 算法 = 程序” 的一种实践。

以 POJ1002 作为例子：

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
const int mapping[] =
{
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, // digit 0~9, ASCII 48~57
    NA, NA, NA, NA, NA, NA, NA, // ASCII 58~64
    2, 2, 2, // A~Y, Q = NA
    3, 3, 3,
    4, 4, 4,
    5, 5, 5,
    6, 6, 6,
    7, NA, 7, 7,
    8, 8, 8,
    9, 9, 9
};
main(){
    // ...
    scanf("%s", buf);
    int j = 0, k = 0, num = 0;
    while(k < 7)
    {
        int c = buf[j++] - '0';
        int x;
        if(0 <= c && MAPSIZE > c && NA != (x = mapping[c]))
        {
            num = num * 10 + x;
            k++;
        }
    }
    cnt[num]++;
    // ...
}

可以看到，在构建好 数据表 之后，核心的查询代码 只有一行（这个例子里，x 是我们需要的值）：

1
2
3
4
if(0 <= c && MAPSIZE > c && NA != (x = mapping[c]))
{
    // use x to do something
}

8 备忘录方法

提到了 预先计算 和 查表，就不得不顺便介绍一下 备忘录方法

大多数时候 备忘录方法 都是用来跟 动态规划 作对比。
这两种方法都是应用于这样的情况：

  1. 问题可以分解成多个子问题
  2. 有重复子问题

所以为了避免重复计算的浪费，两种方法都会开辟一个数组用来存放子问题的解。
区别在于

  • 动态规划 是自底向上的计算，先计算最小的子问题的解，然后逐渐组合出更复杂的子问题的的解，最后得出原问题的解。因为是从最小的字问题开始计算，可能部分子问题的解是没有派上用场的，因为在计算的时候还不知道哪些会被引用。
  • 备忘录方法 是自顶向下的，多数情况下是一个递归结构：先计算原问题，里面引用到子问题时，递归计算子问题……直到全部子问题都有解，再在返回里面组合成原问题的解。这里面， 备忘录方法的优化在于，一旦一个子问题被解决过，就把解缓存起来，以后再引用就直接读取不再计算。

拿 POJ1243 举例

动态规划：

1
2
3
4
5
6
7
8
9
10
11
//...
for(i = 0; i <= G; i++) {
    DP[i][0] = i;
    DP[0][i] = 0;
}
for(i = 1; i<= G; i++) {
    for(j = 1; j<= L; j++) {
        DP[i][j] = DP[i-1][j-1] + 1 + DP[i-1][j];
    }
}

在计算过一次(G, L)之后，所有比G, L 小的(g, l) 对的解都可以在DP数组中找到。不过多个case里面G, L的值的大小并不确定。所以遇到新的G, L又要再算一遍是一种浪费。

备忘录方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getRange(int g, int l) {
    if(0 == Memo[g][l]) {
        // compute it only when it has no result
        Memo[g][l] = getRange(guess - 1, life)
            + 1
            + getRange(guess - 1, life - 1);
    }
    return Memo[g][l];
}
for(i = 0; i <= MAX; i++) {
    Memo[i][0] = i;
    Memo[1][i] = 1;
}
getRange(g, l);

你会发现这道题在case很多而且g, l大小没有顺序时，备忘录方法的效果会更好。（其实这道题也可以预先计算，才30*30的规模）

当然，这道题属于比较特殊的情况，两种方法都能用。
一部分问题 由于引用哪个子问题的解，取决于子问题的解之间的比较，只能先算最小的子问题，只能自底向上，只能动态规划。

而有些题目，实际引用的子问题数占全部子问题数的很少一部分，这时，动态规划把全部子问题算一遍是一种很大的浪费，备忘录是一种更好的选择。

说了这么多好像很复杂，其实 备忘录方法 的核心思想只有一句话： 子问题太多，只在第一次引用时算一次，也只算这一次。

预先计算是：情况这么少，编译前就全算好了。（提前计算）
动态规划是：从最小的子问题开始向上组合，用小的子问题组合出大的子问题，直到原问题。全部子问题都算且只算一次。（从小到大，全部都算）
而备忘录方法：从原问题开始，向下分解，不用不算，只算一次。（推迟计算）

9 邻接矩阵 VS 邻接表 VS 其他图存储法

不同的 图 问题怎么解先按下不表，但是图的存储总是绕不开的问题。

那么最常用的两种表示方法，究竟用 邻接矩阵 还是 邻接表 呢？ 还有什么表示方法呢？ 分别有什么优缺点，要注意什么呢？

（ 为了方便讨论，下面统一用 V 代表顶点数， v 代表一个顶点， E 代表边数， e 代表一条边。*图默认都是无向图，所以是双向操作；如果有向图，请省略反向操作。 另外，为了简便，代码是精简过的伪代码。）

边集数组

在讲那两种主要的存储方式之前，先提一下边集数组。

所谓边集数组，就是用数组记录每条边的两个顶点。部分题目由于input的方式就是给出每条边的两个顶点，所以sample代码里的存储方式默认就是给了边集数组。

1
2
3
4
5
6
7
8
9
10
11
12
// edge array
int A[MAX_E];
int B[MAX_E];
int Weight[MAX_E]; // skip if unweighted graph
// int Edge[MAX_E][3]; // you can make into 1 array too, [0]-from, [1]-to, [2]-weight
for(e: 1 ~ E){
    // input va， vb, weight
    A[e] = va;
    B[e] = vb;
    Weight[e] = weight;
}

优点：

  • 固定使用MAX_E的空间，对于 E << V ^ 2 的图（边数远小于顶点的平方，即，稀疏图），空间上很节省。
  • 方便对边遍历。

缺点：

  • 不能随机访问，对顶点遍历效率很低。

邻接矩阵

因为直观、实现方便，加上正式考试对内存的限制比较宽松，这应该是大家最常用的表示方式。

示例代码给出了两种输入处理： 1是处理以邻接矩阵给出的数据，2是处理以边表的方式给出数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// adjacent matrix
int AdjMat[MAX_V][MAX_V]; // you can use bool for connected or not, and int for weight.
// input method 1 (input from matrix)
for(va: 1 ~ V){
    for(vb: 1 ~ V){
        // input weight
        AdjMat[va][vb] = weight;
    }
}
// input method 2 (input from edge array)
// init
for(va: 1 ~ V){
    for(vb: 1 ~ V){
        AdjMat[va][vb] = DEFAULT; // Define your default value, maybe 0 or -1.
    }
}
for(e: 1 ~ E){
    // intput va, vb, weight
    AdjMat[va][vb] = weight;
    AdjMat[vb][va] = weight; // set this only when it's undirected graph
}

优点：

  • 实现简单（二维数组），容易理解
  • 可以随机访问。亦即，知道任意from, to的值，都可以马上判断是否连通。

缺点：

  • 固定使用MAX_V ^ 2的空间，对于稀疏图，空间上是很大的浪费。（不过由于考试多数够空间，很多时候这个缺点可以忽略）
  • 遍历效率低。跟随机访问相反，如果要遍历from能到的所有to点，就不得不将from所在行遍历一次，在稀疏图中，会导致遍历的效率很低。而恰恰很多算法都需要做遍历。

邻接表

邻接表比邻接矩阵稍复杂一些，一般要用到变长数组vector。

1
2
3
4
5
6
7
8
9
10
11
// adjacent list - based on vector
vector<int> AdjList[MAX_V];
// input
for(e: 1 ~ E){
    // input va, vb
    AdjList[va].push_back(vb);
    AdjList[vb].push_back(va);
    // AdjList[va].push_back(weight); // If it's weighted graph, you can push weight right after vb.
    // AdjList[vb].push_back(weight);
}

你可能会问，库不是不给用了吗？其实基于边集数组可以改写成邻接表， 本质上就是用Next数组将边集数组串联起来。

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
// adjacent list - based on edge array
int Head[MAX_V];
int Tail[MAX_V];
int Next[MAX_E];
int To[MAX_E * 2]; // size * 2 for reverse edge
int Weight[MAX_E]; // skip if unweighted graph
E_counter = 0;
for(e: 1 ~ E){
    // input va， vb, weight
    // process va -> vb
    To[E_counter] = vb;
    Weight[E_counter] = weight;
    if(Head[va] == DEFAULT){
        Head[va] = E_counter;
    } else {
        Next[Tail[va]] = E_counter;
    }
    Tail[va] = E_counter;
    E_counter++;
    // process vb -> va
    To[E_counter] = va;
    Weight[E_counter] = weight;
    if(Head[vb] == DEFAULT){
        Head[vb] = E_counter;
    } else {
        Next[Tail[vb]] = E_counter;
    }
    Tail[vb] = E_counter;
    E_counter++;
}

而如果不为了省内存，只是为了加快遍历速度，直接上二维数组也可以实现邻接表。

1
2
3
4
5
6
7
8
// adjacent list - based on 2-dimens array
int AdjList[MAX_V][MAX_V];
for(e: 1 ~ E){
    // intput va, vb, weight
    AdjList[va][++AdjList[va][0]] = weight; // store edge from AdjList[v][1], use AdjList[v][0] to store the edge number that adjacent to v.
    AdjList[vb][++AdjList[vb][0]] = weight; // set this only when it's undirected graph
}

优点：

  • 方便对顶点遍历邻接顶点（或者说对顶点，遍历它连接的边），对稀疏图的遍历比邻接矩阵节省时间。 一般空间足够的情况下，推荐最后一种实现方式。

缺点：

  • 不能对边遍历
  • 不能随机访问

表面上来看，邻接表缺点比较多。但实际使用中，几乎所有图算法都需要对顶点遍历边（Dijkstra，Floyd，Prim…），所以反而是最常用的表示存储方式。

其他存储方式

牵涉到复杂的指针操作，仅供参考了解。

  • 十字链表
  • 多重邻接表

原本这里写着 …… To be continued……，表示我会不定期更新。但因为我的离职，起码三星内网的那篇文章，我再也不会更新了。

知识共享 “署名-非商业性使用-相同方式共享” 4.0 (CC BY-NC-SA 4.0)”许可协议
本文为本人原创，采用知识共享 “署名-非商业性使用-相同方式共享” 4.0 (CC BY-NC-SA 4.0)”许可协议进行许可。
本作品可自由复制、传播及基于本作品进行演绎创作。如有以上需要，请留言告知，在文章开头明显位置加上署名（Jayce Chant）、原链接及许可协议信息，并明确指出修改（如有），不得用于商业用途。谢谢合作。
详情请点击查看协议具体内容。