一个算法题

现在对这些问题不感兴趣了,不像大学的我,主要因为他跟实际工作没啥关系,更多是个游戏,我也玩过编程竞赛,topcoder还曾经达到了(低)黄色的,这个结果其实也不算啥,但至少证明自己还是有些水平的。我曾经解了不少topcoder 500的题,但是竞赛中解决的不够快(srm只有75分钟的时间)。

最近写了一下jvm的东西,那些更有意思,也更重要,这次也写一个算法题吧。

我在一个面试被问了一个傻逼问题,就是给你为输入k个有序数组。要输出一个这些数组内容合并的并保持有序的数组。

这个问题好像有一次在美国一个面试也问道,但当时答的不是特别清楚。最终倒是想到了用最大排序堆了吧,但自己理解的也有点马虎,主要是没把细节写的讲的太好。

但在中国这个问题,我先用了O(nk)的做法写了代码。然后面试官让我想一个更好的。我立马想到了可以

input: vector > kSortedArrays
pair valueAndIndex;
vector res;

heap > minHeap;

int currentIndex[k];
memset(currentIndex, 0, sizeof(currentIndex);

for (int i = 0; i < k; i++) 
   minHeap.add(new pair(kSortedArrays[i][0], i));

while (minHeap.empty()) {
  int index = heap.pop().second
  res.push_back(heap.pop().first);
  if (++currentIndex[index] < kSortedArrays[index])
    minHeap.add(new pair(currentIndex[index], index))
}

return res;

这个我就懒得解释了,应该相当明显了。

还有几个傻逼问题我在中国美国都被问过,一个是给一个队列,让你按照层的顺序打出来。这个就是用宽度优先搜索算法(bfs)。

还有一个是给你个1和0的二维数组,让你数有多少个连续片段,这个用深度优先搜索算法(dfs)。

不多说了。。。我解决过好多真正难的ACM/TopCoder/USACO的算法题,但现在对那些页没兴趣了。

Advertisements