枚举算法

今天我们来讲一个万金油算法，这个算法可以解决所有的问题，它就是枚举法（穷举法）。

枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。

枚举算法简单粗暴，他暴力的枚举所有可能，尽可能地尝试所有的方法。虽然枚举算法非常暴力，而且速度可能很慢，但确实我们最应该优先考虑的！因为枚举法变成实现最简单，并且得到的结果总是正确的。

我们通过几个题目，来讲一讲什么是枚举法。

题目一：

给定一个序列，a1 ，a2 ，...，an 。定义这个序列的最大间隔为d=max{abs(a[i+1] - a[i] )}(1≤i<n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少？ n < 100;

输入例子：n = 5 a[] = 1 2 3 7 8

输出4

（蘑菇街面试真题）

思考一：

我们可以枚举哪一个数被删除了，然后形成一个新的序列，在用一边for循环去统计哪一个的间隔最大。

题目二：

给你一个字符串，求出字符串中最长的回文子串。

例如:abcdcbe

输出 bcdcb

思考二：

我们可以枚举哪一个是回文字符串的中心，然后再往左右进行扩展。这里有两种情况，回文字母串长度有奇数跟偶数，需要特殊考虑一下。

题目三：

输入正整数k，求出所有正整数x >= y，并且 1/k = 1/x + 1/y

样例输入:2

样例输出：

1/2 = 1/6 + 1/3

1/2 = 1/4 + 1/ 4

思考三：

我们可以枚举所有的x，y的大小，并且x >= y， 判断 1/ k 是否等于 1/x + 1/y。既然是枚举所有的x,y的大小，那么x,y最大多大呢？y的最大值为2k。因为x>=y,所以1/x <= 1/y。1/k - 1/y <= 1/y。所以y <= 2k.

好了，相信通过上面的3个例题，我们已经可以初步认识了枚举算法。我们来看一下枚举算法的局限性。

我们来尝试用枚举算法解决《阿里面试题》这个题目。我们需要枚举一个员工需要在那一段时间值班，这个的的复杂度是O(nxn)(开始结束时间)。我们注意到，如果有k个员工，那么，这个将是一个指数级的增长，枚举第一个员工后枚举第二个再枚举第三个。。。最后变成 ((N*N)^K)。当n，k达到10左右时，这就是一个天文数字了。

所以枚举算法的缺点就是速度太慢。所以才后来后面我们的其他算法。看到这里，不知道你是否已经懂了枚举算法呢？你需要下一期讲什么算法，也可以在下面评论留言。