这次的“精选”内容是“很简单”的算法题，乃看看自己能做出几个。
问题 1：
有一个未排序的整型数组 A，每个数字范围是 1 – 30 000，最多有 50 000 个元素。
现在要把数组里的数字两两合并。每次选出两个数字从数组里删去，并将这两个数相加后放到原数组里去。每执行一步，你要消耗的体力值为两数之和。
重复以上步骤，直到数组里只剩下一个元素。求消耗的最少体力值之和（时限 1 秒）。
例如数组为 [1, 3, 2, 4]，第一次合并 1 和 2，数组变为 [3, 3, 4]，消耗体力 3；第二次合并 3 和 3，数组变为 [6, 4]，消耗体力 6；第三次合并 6 和 4，数组变为 [10]，消耗体力 10。一共消耗体力 3+6+10=19，即为所求。
问题 2：
有一个已经排序好的数组 A，里面的数字取值只有 0 – 9 这 10 种。求哪一个数字出现最多。
问题 3：
输入一个只含有左右括号 ‘(‘ 和 ‘)’ 的字符串，找出字符串中最长的符合规则的子串。
例如输入：)(()(())))()(()，红色部分为最长合法子串。
======================================================
分析 1：
随便尝试一下，发现只要每次都合并最小的两个数字，就是最优解。
只要乃上学的时候上课没有睡觉，会发现这特么就是一个哈夫曼编码。所以现在问题的关键就是每次找到最小的两个数字。
如果乃用暴力搜索，每次遍历数组来找到最小的两个数字，那么你就可以和二面说“白白”了。
很明显“堆”（优先队列）适合干这种事情，每次取到最小值后，重新调整堆的复杂度为 O(logn)，所以合并所有数字的复杂度是 O(nlogn)。
但是数字范围只有 1 – 30 000 这个条件有什么用呢？明显是让你用计数排序，用 O(n) 的复杂度把这 n 个数字排序好。乃可能会说，虽然最小的数字是前两个，但是相加之后的结果要放在数组的某个地方，这个复杂度至少就是 O(logn) 了，显然复杂度还是 O(nlogn) 啊？
既然都想到这里了，为什么还是有思维定势呢？我们为啥要把相加后的结果放回原来的数组里，我们可以把每次相加的结果放在另外一个数组 B 里。因为我们每次都是合并的最小的两个数字，因此每次相加后的结果必然是单调递增（即不会比上一个少），放到 B 数组里的数字也必然是递增的。
那么就很简单的，每次取数必然只能在 A 和 B 的头部取，要么两个数字都是 A 的，要么都是 B 的，要么 A 和 B 各一个，这样每次取数的复杂度就变成 O(1) 了，最终时间复杂度就会是 O(n) 了。
备注：这道题是某年高中信息竞赛的题，原题标题为“合并果子”。
分析 2：
任何遍历数组的解答肯定会死得很难看，因为你忘了数组是排好序的。
所以很容易想到的是用二分法来计数。搞一个长度为 10 的数组来计数，当递归到某一个子区间时，如果发现有一段上下界相等，那么就可以直接向计数器里累加，然后这一段就可以不管了。如果上下界不相等，就取中间元素二分。这个方法代码很容易写。
不过还可以加快运行速度吗？实际上是可以的，我们只要查找最多的数字，而不是为每个数字进行计数。我们发现数字只有 0 – 9 一共 10 种，此时脑袋上灯泡一亮，感觉有好办法了。
假如一共有 N 个数字，那么出现最多的数字一定不会比 N/10 少。我们把数组平均分成 10 段，看每一段的上下界，如果上下界相等，这一段的数字就会是“候选者”。这样，我们就可以在一个只有 10 次的循环里找到这些“候选者”，看它们谁所在的“区间”数量多。
能够进行下一轮 PK 的数字所占的区间数必然不能相差 2 个区间以上，否则就可以放心地“淘汰”了。接着对“幸存者”所在的区间进一步判断，找出幸存者在上下界不相等的区间里的边界，以便确定数量。
采用这种方法，看上去会比用二分法统计快不少，因为范围一下子就降低了很多。不过代码好像相当难写，等老夫哪天心情好来实现一下。
分析 3：
很明显一个动态规划问题，找到转移方程后，实现就相当容易了。
令 dp(i) 表示以位置 i 【结尾】的最长合法子串，那么：
- 如果 A[i] = ‘(‘，则 dp(i) = 0，很明显以 ‘(‘ 结尾的不可能是合法子串。
- 如果 A[i] = ‘)’，并且 a(i – 1) = ‘(‘，则最后两位肯定合法，所以 dp(i) = dp(i – 2) + 2。
- 如果 A[i] = ‘)’，并且 a(i – 1) = ‘)’，则字符串以 “……)) ”结尾。此时判断 a(i – dp(i – 1) – 1)，即上一个位置的 ‘)’ 匹配的左括号的前一位，如果是 ‘(‘，则和这个右括号匹配上了，长度加 2，即 dp(i)=dp(i−1)+dp(i−dp(i−1)−2)+2。否则就不匹配了，只能置为 0。
因此时间复杂度是 O(n)，空间复杂度是 O(n)。
当然说到括号匹配，很容易想到用栈来判断，这个实现起来就比 dp 容易了，而且复杂度和上述方法相当。
不过有一个方法可以把空间复杂度优化到 O(1)，那就是用首末两个指针。提示到这里，相信乃自己就可以想到解法了。