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 的大作中提到】
: 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 的大作中提到】
: 最后一题有啥好方法没，只觉得与某个特殊的栈有关，记不得名字了
| m*****k
发帖数: 731 | 6 喜欢 this:
http://stackoverflow.com/questions/10670301/find-the-maximum-po
谁有比这更好的解法么？
【在 b***e 的大作中提到】
: 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
|
|
