前几晚看《The Go Progromming Language》时，在匿名函数的最后一小节中，发现了一个比较有趣的小坑。
大概的场景为：首先创建一些目录，然后对于每一个目录，分别声明一个匿名函数删除目录，样例代码如下：

1
2
3
4
5
6
7

var rmdirs []func()
for _, dir := range tempDirs() {
    os.MkdirAll(dir, 0755)
    rmdirs = append(rmdirs, func() {
        os.RemoveAll(dir) 
    })
}

大家可以先自行考虑一下，有没有什么问题，效果会是怎样

背景

近来都在刷CCF的题，准备认证考试。最近几天开始刷其中的第四题，一般而言，CCF的第四题都是图论题。对于我这样之前没怎么刷题的人来说，图论题看上去就感觉很难，主要是感觉到很陌生，因为在实际的开发过程中比较少用到图这样的数据结构，都是线性的数据结构，连树都比较少用。

但是在刷得比较多的图论题后，发现其实图论题好像也就那么回事，也不是说简单，主要感觉来来去去都是考那几个东西，如果是没有接触过或者不会做的话，可能有点难，但是只要接触过相似的，直接套板子修改就行了（当然也有可能是我还接触的不够多 XD），另外，就是感觉没有什么题是 DFS/BFS 不能破，只是会不会超时，能拿多少的分的问题（对于 CCF 认证只想拿 300 分而言，有几十分就够了），其实很多算法的核心也就是 DFS 与 BFS。

所以在今晚刷完了 CCF 往年所有的第四题后，总结一下最近接触的图论问题及解法。

Problem

问题描述

给定一个公司的网络，由 n 台交换机和 m 台终端电脑组成，交换机与交换机、交换机与电脑之间使用网络连接。交换机按层级设置，编号为 1 的交换机为根交换机，层级为 1。其他的交换机都连接到一台比自己上一层的交换机上，其层级为对应交换机的层级加 1。所有的终端电脑都直接连接到交换机上。
　　当信息在电脑、交换机之间传递时，每一步只能通过自己传递到自己所连接的另一台电脑或交换机。请问，电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。

Problem

问题描述

给定一段文字，已知单词a1, a2, …, an出现的频率分别t1, t2, …, tn。可以用01串给这些单词编码，即将每个单词与一个01串对应，使得任何一个单词的编码（对应的01串）不是另一个单词编码的前缀，这种编码称为前缀码。
　　使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。一段文字经过前缀编码后的长度为：
　　L=a1 的编码长度 ×t1+a2 的编码长度 ×t2+…+ an 的编码长度×tn。
　　定义一个前缀编码为字典序编码，指对于1 ≤ i < n，ai的编码（对应的01串）的字典序在ai+1编码之前，即 a1, a2, …, an 的编码是按字典序升序排列的。
　　例如，文字E A E C D E B C C E C B D B E中， 5个单词A、B、C、D、E出现的频率分别为1, 3, 4, 2, 5，则一种可行的编码方案是A:000, B:001, C:01, D:10, E:11，对应的编码后的01串为1100011011011001010111010011000111，对应的长度 L 为 3×1+3×3+2×4+2×2+2×5=34。
　　在这个例子中，如果使用哈夫曼(Huffman)编码，对应的编码方案是A:000, B:01, C:10, D:001, E:11，虽然最终文字编码后的总长度只有33，但是这个编码不满足字典序编码的性质，比如C的编码的字典序不在D的编码之前。
　　在这个例子中，有些人可能会想的另一个字典序编码是A:000, B:001, C:010, D:011, E:1，编码后的文字长度为35。
　　请找出一个字典序编码，使得文字经过编码后的长度L最小。在输出时，你只需要输出最小的长度L，而不需要输出具体的方案。在上面的例子中，最小的长度L为34。

Problem

问题描述

某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。
该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：

1. buy p s 表示一个购买股票的买单，每手出价为p，购买股数为s。
2. sell p s 表示一个出售股票的卖单，每手出价为p，出售股数为s。
3. cancel i表示撤销第i行的记录。

如果开盘价为p0，则系统可以将所有出价至少为p0的买单和所有出价至多为p0的卖单进行匹配。因此，此时的开盘成交量为出价至少为p0的买单的总股数和所有出价至多为p0的卖单的总股数之间的较小值。
　　
你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。

Problem

• source: Wildcard Matching

• difficulty: hard

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?'and '*'.

1
2

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Problem

问题描述

俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。
　　游戏在一个15行10列的方格图上进行，方格图上的每一个格子可能已经放置了方块，或者没有放置方块。每一轮，都会有一个新的由4个小方块组成的板块从方格图的上方落下，玩家可以操作板块左右移动放到合适的位置，当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时，板块不再移动，如果此时方格图的某一行全放满了方块，则该行被消除并得分。
　　在这个问题中，你需要写一个程序来模拟板块下落，你不需要处理玩家的操作，也不需要处理消行和得分。
　　具体的，给定一个初始的方格图，以及一个板块的形状和它下落的初始位置，你要给出最终的方格图。

Problem

• Source: Merge K Sorted Lists
• difficulty: hard

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

引言

在准备做Windows程序设计的大作业时，需要用到 Mysql。打开了 Mysql WorkBench 连接本地数据库时，提示要输入 root 密码，试了几个常用密码无果后，发现自己再次忘记了 Mysql 的 root 密码。但是没有关系，本人已经习惯忘记各种不太常用的账号密码了，驾轻就熟地打开百度搜索相关方法，却发现来来去去都是那同一个方法，而且还因为版本问题与实际情况有些差异，最终还是花费了不少的时间，有点难受，遂写一文记录一下。

Problem

Given a string array words, find the maximum value of length(words[i]) * length(words[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

1
2
3

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 
Explanation: The two words can be "abcw", "xtfn".