一些简单的面试题精选(2)

这次的“精选”内容是“很简单”的算法题,乃看看自己能做出几个。

 

问题 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 【结尾】的最长合法子串,那么:

  1. 如果 A[i] = ‘(‘,则 dp(i) = 0,很明显以 ‘(‘ 结尾的不可能是合法子串。
  2. 如果 A[i] = ‘)’,并且 a(i – 1) = ‘(‘,则最后两位肯定合法,所以 dp(i) = dp(i – 2) + 2。
  3. 如果 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),那就是用首末两个指针。提示到这里,相信乃自己就可以想到解法了。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s