t**********d 发帖数: 14 | 1 1)Given n non-negative integers a1, a2, ..., an, where each represents a
point at coordinate (i, ai). n vertical lines are drawn such that the two
endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together
with x-axis forms a container, such that the container contains the most
water.
2) Given a non-negative integer array representing an elevation map where
the width of each bar is 1, compute how much water it can trap after raining
. For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6.
http://www.leetcode.com/groups/google-interview/forum/topic/rai
3) Given n non-negative integers representing the histogram's bar height
where the width of each bar is 1, find the area of largest rectangle in the
histogram.
4) Given a set of buildings, defined by (x1,x2,height) discuss an algorithm
to determine the silhouette of the buildings (line, the skyline). Buildings
can overlap each other.
http://www.careercup.com/question?id=3514054
5) You are given N blocks of height 1..N. In how many ways can you arrange
these blocks in a row such that when viewed from left you see only L blocks
(rest are hidden by taller blocks) and when seen from right you see only R
blocks?
Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while
for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
似乎难度都不小,而且理解起来很恶心。需要用堆栈或者heap反复比较。大家有什么比
较好的通用解题思路? | b***e 发帖数: 1419 | 2 The first one is interesting. I believe there’s a linear algorithm:
First compute the ascending sequence from the left.
Then compute the ascending sequence from the right.
Finally, do a merge sort...
together
raining
【在 t**********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1)Given n non-negative integers a1, a2, ..., an, where each represents a : point at coordinate (i, ai). n vertical lines are drawn such that the two : endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together : with x-axis forms a container, such that the container contains the most : water. : 2) Given a non-negative integer array representing an elevation map where : the width of each bar is 1, compute how much water it can trap after raining : . For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6. : http://www.leetcode.com/groups/google-interview/forum/topic/rai : 3) Given n non-negative integers representing the histogram's bar height
| m******d 发帖数: 25 | 3 第一题可以这么做:先计算一下最左L和最右R两条线包围出的面积。假定L比R短,那么
从左边开始,找到第一条比L高的线段L'。计算L'和R包围的面积,看看是不是更大。L
和L'包围出的面积不可能比L和R包围的面积大,所以不用考虑。下一步,L'变成新的L
,重新开始。O(n)。 | z****e 发帖数: 9 | 4 最后一题有啥好方法没,只觉得与某个特殊的栈有关,记不得名字了 | c*****e 发帖数: 3226 | 5 最难的应该是题4。
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 最后一题有啥好方法没,只觉得与某个特殊的栈有关,记不得名字了
| m*****k 发帖数: 731 | 6 喜欢 this:
http://stackoverflow.com/questions/10670301/find-the-maximum-po
谁有比这更好的解法么?
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : The first one is interesting. I believe there’s a linear algorithm: : First compute the ascending sequence from the left. : Then compute the ascending sequence from the right. : Finally, do a merge sort... : : together : raining
|
|