Sheng Li (gmachine1729) wrote,
Sheng Li
gmachine1729

一个算法题

Originally published at 狗和留美者不得入内. You can comment here or there.

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

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

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

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

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

input: vector
[Error: Irreparable invalid markup ('<vector<int>') in entry. Owner must fix manually. Raw contents below.]

<p><small>Originally published at <a href="https://gmachine1729.com/2019/12/01/%e4%b8%80%e4%b8%aa%e7%ae%97%e6%b3%95%e9%a2%98/">狗和留美者不得入内</a>. You can comment here or <a href="https://gmachine1729.com/2019/12/01/%e4%b8%80%e4%b8%aa%e7%ae%97%e6%b3%95%e9%a2%98/#comments">there</a>.</small></p><p>现在对这些问题不感兴趣了,不像大学的我,主要因为他跟实际工作没啥关系,更多是个游戏,我也玩过编程竞赛,topcoder还曾经达到了(低)黄色的,这个结果其实也不算啥,但至少证明自己还是有些水平的。我曾经解了不少topcoder 500的题,但是竞赛中解决的不够快(srm只有75分钟的时间)。</p> <p>最近写了一下jvm的东西,那些更有意思,也更重要,这次也写一个算法题吧。</p> <p>我在一个面试被问了一个傻逼问题,就是给你为输入k个有序数组。要输出一个这些数组内容合并的并保持有序的数组。</p> <p>这个问题好像有一次在美国一个面试也问道,但当时答的不是特别清楚。最终倒是想到了用最大排序堆了吧,但自己理解的也有点马虎,主要是没把细节写的讲的太好。</p> <p>但在中国这个问题,我先用了<img src="//s0.wp.com/latex.php?latex=O%28nk%29&#038;bg=ffffff&#038;fg=1a1a1a&#038;s=0" alt="O(nk)" title="O(nk)" class="latex" />的做法写了代码。然后面试官让我想一个更好的。我立马想到了可以</p> <pre>input: vector<vector<int> > kSortedArrays pair<int, int> valueAndIndex; vector<int> res; heap<pair<int, int> > minHeap; int currentIndex[k]; memset(currentIndex, 0, sizeof(currentIndex); for (int i = 0; i < k; i++) minHeap.add(new pair<int, int>(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<int, int>(currentIndex[index], index)) } return res;</pre> <p>这个我就懒得解释了,应该相当明显了。</p> <p>还有几个傻逼问题我在中国美国都被问过,一个是给一个队列,让你按照层的顺序打出来。这个就是用<em>宽度优先搜索</em>算法(bfs)。</p> <p>还有一个是给你个1和0的二维数组,让你数有多少个连续片段,这个用深度优先搜索算法(dfs)。</p> <p>不多说了。。。我解决过好多真正难的ACM/TopCoder/USACO的算法题,但现在对那些页没兴趣了。</p>
Tags: uncategorized
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 0 comments