在条形图中添加水 [英] Add water between in a bar chart
问题描述
最近在类似玻璃门的网站上遇到了一个采访问题，我找不到解决此问题的优化解决方案：
Recently came across an interview question in glassdoor-like site and I can't find an optimized solution to solve this problem:
这完全不像是陷水问题。请通读示例。
This is nothing like trapping water problem. Please read through the examples.
给出一个输入数组，该数组的每个元素代表塔的高度，将倒水的数量，并且索引号指示倒水的位置。每塔的宽度为1.倒水后打印图表。
Given an input array whose each element represents the height of towers, the amount of water will be poured and the index number indicates the pouring water position.The width of every tower is 1. Print the graph after pouring water.
注意：
-
使用
*表示塔，w表示1量水。
Use
*to indicate the tower,wto represent 1 amount water.
浇筑位置永远不会在高峰位置。无需考虑分水情况。
The pouring position will never at the peak position.No need to consider the divide water case.
（如果给出解决方案，这是加分点）对于这种情况，您可以假设如果在峰值位置倒N水，则N / 2水流向左，N / 2水流向右。）
(A Bonus point if you gave a solution for this case, you may assume that if Pouring N water at peak position, N/2 water goes to left, N/2 water goes to right.)
峰的定义：峰位置的高度大于其旁边的左右两个索引。）
The definition for a peak: the height of peak position is greater than the both left and right index next to it.)
-
假定直方图附近有2个极高的墙。
因此，如果水量超过直方图的容量， >
，则应指明容量编号并继续操作。参见示例2。
Assume there are 2 extreme high walls sits close to the histogram.
So if the water amount is over the capacity of the histogram,
you should indicate the capacity number and keep going. See Example 2.
假设水先流走，请参见示例1
Assume the water would go left first, see Example 1
示例1：
int[] heights = {4,2,1,2,3,2,1,0,4,2,1}
It look like:
* *
* * **
** *** **
******* ***
+++++++++++ <- there'll always be a base layer
42123210431
Assume given this heights array, water amout 3, position 2:
打印：
* *
*ww * **
**w*** **
******* ***
+++++++++++
示例2：
int[] heights = {4,2,1,2,3,2,1,0,4,2,1}, water amout 32, position 2
打印：
capacity:21
wwwwwwwwwww
*wwwwwww*ww
*www*www**w
**w***ww**w
*******w***
+++++++++++
起初我虽然喜欢陷阱水问题，但我错了。有人有解决此问题的算法吗？
At first I though it's like the trapping water problem but I was wrong. Does anyone have an algorithm to solve this problem?
欢迎对代码进行解释或注释。
An explanation or comments in the code would be welcomed.
注意：
需要捕获水的容量，但是这个问题引入了两个变量：水量和倾倒指数。此外，水具有流动性。因此，这不像陷水问题。
The trapping water problem is asked for the capacity, but this question introduced two variables: water amount and the pouring index. Besides, the water has the flowing preference. So it not like trapping water problem.
推荐答案
我找到了解决此问题的Python解决方案。但是，我不熟悉Python，因此在这里引用了代码。希望有人知道Python可以提供帮助。
I found a Python solution to this question. However, I'm not familiar with Python so I quote the code here. Hopefully, someone knows Python could help.
通过 @ z026
def pour_water(terrains, location, water):
print 'location', location
print 'len terrains', len(terrains)
waters = [0] * len(terrains)
while water > 0:
left = location - 1
while left >= 0:
if terrains[left] + waters[left] > terrains[left + 1] + waters[left + 1]:
break
left -= 1
if terrains[left + 1] + waters[left + 1] < terrains[location] + waters[location]:
location_to_pour = left + 1
print 'set by left', location_to_pour
else:
right = location + 1
while right < len(terrains):
if terrains[right] + waters[right] > terrains[right - 1] + waters[right - 1]:
print 'break, right: {}, right - 1:{}'.format(right, right - 1)
break
right += 1
if terrains[right - 1] + waters[right - 1] < terrains[location] + waters[right - 1]:
location_to_pour = right - 1
print 'set by right', location_to_pour
else:
location_to_pour = location
print 'set to location', location_to_pour
waters[location_to_pour] += 1
print location_to_pour
water -= 1
max_height = max(terrains)
for height in xrange(max_height, -1, -1):
for i in xrange(len(terrains)):
if terrains + waters < height:
print ' ',
elif terrains < height <= terrains + waters:
print 'w',
else:
print '+',
print ''
这篇关于在条形图中添加水的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
