• 连连看与一种巧妙的广度优先搜索

    连连看是一种益智游戏,其核心算法是要在一个M * N的矩阵上找出两个点的“最短路径”,满足:1. 转弯数最少 2. 经过的点最少。谈到图的两点间最短路径,我们会想到用于无权图的广度优先搜索(BFS)和带权图的Dijkstra算法。那么对于连连看的M * N矩阵来说,究竟可以抽象成有权图呢还是无权图?如果有,权重又是什么呢? 继续阅读 »

  • Slash Maze

    这道题不简单!首先要把迷宫表示成可遍历的图,其次要找出图中所有的环及其长度。

    第一个问题就很棘手:只用斜线矩阵(构成的邻接矩阵)来表示图可以吗?这种方式看似简单可行——可以遍历出环——但是难以计算环的长度(如环内部的情况比较复杂时),而且难以枚举出所有环(环和环之间可能有共享边),必须考虑其他方式。

    继续阅读 »

  • Playing With Wheels

    每个数字代表一个状态,其任意一位左/右转动得出的数字代表一个新的状态:如果把这些状态看作一张图的顶点,在一个状态和它可以(一步)到达的状态之间连一条线,那么在初始状态和目标状态之间的最短路径长度就等于最少的转换步数,可以用广度优先搜索得到;对于禁止的状态,可以在遍历图之前就把它们标记为“已访问”状态,这样就不会搜素经过这些禁止状态的路径了。代码如下:

    继续阅读 »

  • Chopsticks

    如果考虑一般情况:把n个元素划分成p组(p = k + 8)、每组3个元素,分别计算每种划分的“难用度”然后找出最小值,这种穷举算法时间复杂度巨大、不可用。

    题目中说筷子数组l是按长度排好序的,这是一点很重要的提示:如果我们拿l[i]做A筷,则B筷一定是l[i + 1]才能保证(A - B) ^ 2最小,至于C筷,只要它的序号大于i + 1即可。

    这样,如果设f(i, j)为从l[i]到l[n - 1]里选出j组筷子(每组3支)的最小“难用度”,则f(0, p)即求解目标,并有以下递推式:

    继续阅读 »

  • Ferry Loading

    此题最简单、直观的办法是递归求解:

    继续阅读 »

  • Weights and Measures

    此题贪心可解:定义第i层的最大负载为p(i),则:

    继续阅读 »

  • 最长上升子序列长度的O(N*logN)算法推导

    关于最长上升子序列的O(N*logN)算法已经有不少文章表述,可惜大都不够“好”(甚至语焉不详):我认为“好”的算法描述不但应该清晰地说明计算步骤,更应该讲清思路——即,这个算法是怎样思考得出的。这种思考的过程和方式才是精华之处。我试图用我的理解对这个算法给出一个尽量“好”的推导和表述,使你我一样的普通人都可以理解它的思路。 继续阅读 »

  • Ruby Rack及其应用(下)

    Ruby Rack及其应用(上)对Rack的定义、基本原理和构建方法做了介绍,并且提到Rails、Sinatra等web框架都是在Rack之上构建的。现在让我们来看几个Rack作为中间件的典型例子,包括Auth、Session以及Log。 继续阅读 »

  • 电子书与跑步机

    我有不少电子书,其中一些还购买了纸质书——不(仅仅)是为了收藏,而是为了更好地阅读——把经常阅读的书放在手边、随手可以翻到感兴趣的地方是很重要的。另外,这对记忆也大有帮助——哪一天、在什么情况下你翻到了书的什么位置、看到了什么、想到了什么,这些信息都藏在你大脑深处,帮助你回忆。

    继续阅读 »

  • 作为缓存的Redis实例的备份和恢复

    听上去很简单,然而并不是——今天我要说的是为仅配置为缓存、没有persistence的Redis实例进行备份和恢复。为什么要对缓存进行备份和恢复?每个人的需求都不一样,其中一种是为了debug:你必须复原一个与production一模一样的环境——不仅是db,还有缓存,否则一些问题就没法重现。 继续阅读 »