條形圖

Question

最近遇到的面試問題在glassdoor樣的網站排在之間加水，我不能找到一個優化的解決方案來解決這個問題：

這跟捕水問題。請閱讀示例。

給定輸入數組，其每個元素表示塔的高度時，水的量將被傾倒和索引號指示每個塔的澆注水position.The寬度爲1.打印注水後的曲線圖。

注：

1. 使用*來指示塔，w來表示1升量的水。

2. 澆注位置永遠不會在高峯位置。無需考慮分水情況。

   （A獎金點，如果你給這種情況下的解決方案，則可以假定，如果在峯值位置澆注Ñ水，N/2水進入到左，N/2水前進到右側）

一個峯的定義：峯值位置的高度比它旁邊的兩個左和右指數大於）

假設有2周極端高壁位於接近直方圖。
因此，如果水量超過直方圖的容量，您應該指出容量數量並繼續。見例2.

假設水會向左走第一，見例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 
431 
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*** 
+++++++++++ 

起初我以爲這就像the trapping water problem，但我錯了。有沒有人有算法來解決這個問題？

歡迎對代碼進行解釋或評論。

注：

捕水問題問的能力，但這個問題引入了兩個變量：水量與灌注指數。此外，水有流動的偏好。所以它不像陷水問題。

Answer 1

我找到了這個問題的Python解決方案。但是，我對Python不熟悉，所以我在這裏引用了代碼。希望有人知道Python可以提供幫助。

代碼由@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 '' 

Answer 2

由於您必須生成並打印出數組，因此我可能會選擇使用遞歸方法來保持O(rows*columns)的複雜性。注意每個單元最多可以「訪問」兩次。

高級別：首先遞減，然後離開，然後向右，然後填充當前單元格。

然而，這種運行到一個小問題：（假設這是一個問題）

*w *    *  * 
**ww* * instead of **ww*w* 

這可以通過更新算法固定去左，右首創，填補細胞下面當前行，然後再向左右兩邊再次填充當前行。假設我們說state = v意味着我們來自上面，state = h1意味着它是第一個水平傳球，state = h2意味着它是第二個水平傳球。

您可能可以通過使用堆棧來避免重複訪問單元，但它更復雜。

僞代碼：

array[][] // populated with towers, as shown in the question 
visited[][] // starts with all false 
// call at the position you're inserting water (at the very top) 
define fill(x, y, state): 
    if x or y out of bounds 
      or array[x][y] == '*' 
      or waterCount == 0 
     return 

    visited = true 

    // we came from above 
    if state == v 
     fill(x, y+1, v) // down 
     fill(x-1, y, h1) // left , 1st pass 
     fill(x+1, y, h1) // right, 1st pass 
     fill(x-1, y, h2) // left , 2nd pass 
     fill(x+1, y, h2) // right, 2nd pass 

    // this is a 1st horizontal pass 
    if state == h1 
     fill(x, y+1, v) // down 
     fill(x-1, y, h1) // left , 1st pass 
     fill(x+1, y, h1) // right, 1st pass 
     visited = false // need to revisit cell later 
     return // skip filling the current cell 

    // this is a 2nd horizontal pass 
    if state == h2 
     fill(x-1, y, h2) // left , 2nd pass 
     fill(x+1, y, h2) // right, 2nd pass 

    // fill current cell 
    if waterCount > 0 
     array[x][y] = 'w' 
     waterCount-- 

Answer 3

你必須在每一列中的地形高度數組height，所以我創建這個數組的副本（我們稱之爲w爲水）表明每列中的水有多高。像這樣，當轉換成網格時，您還可以擺脫不知道要初始化多少行的問題，並且可以完全跳過該步驟。

在Java代碼中的算法將是這個樣子：

public int[] getWaterHeight(int index, int drops, int[] heights) { 
    int[] w = Arrays.copyOf(heights); 
    for (; drops > 0; drops--) { 
     int idx = index; 
     // go left first 
     while (idx > 0 && w[idx - 1] <= w[idx]) 
      idx--; 
     // go right 
     for (;;) { 
      int t = idx + 1; 
      while (t < w.length && w[t] == w[idx]) 
       t++; 
      if (t >= w.length || w[t] >= w[idx]) { 
       w[idx]++; 
       break; 
      } else { // we can go down to the right side here 
       idx = t; 
      } 
     } 
    } 
    return w; 
} 

即使有很多循環，其複雜度只有O（滴*列）。如果你期望大量的下降，那麼計算關於最高地形點O（列）的空白空間的數量可能是明智的，然後如果下降的數量超過空閒空間，則列高度的計算變得微不足道O（1），但是設置它們仍然需要O（列）。

Answer 4

可以在2D網格從底部循環到頂部，用於連接電池的每一個水平運行創建節點，然後串這些節點連接在一起成表示鏈表電池填充的順序。

一行後，你有一個橫向運行，以1:1的體積：

1(1) 

在兩排，你會發現三個運行，其中一個連接到節點1：

1(1)->2(1) 3(1) 4(1) 

在第三行中，您會發現三個運行，其中一個運行連接運行2和3;運行3最接近其中添加水列，所以它是第一位的：

3(1)->1(1)->2(1)->5(3) 6(1) 4(1)->7(1) 

在四排你發現兩分，其中一個連接運行6和7;運行6最接近其中添加水列，所以它是第一位的：

3(1)->1(1)->2(1)->5(3)->8(4) 6(1)->4(1)->7(1)->9(3) 

在五行你會發現它連接運行8,9運行;它們在其中加入的水的柱的相對側上，所以在左側的運行先行：

3(1)->1(1)->2(1)->5(3)->8(4)->6(1)->4(1)->7(1)->9(3)->A(8) 

運行A結合了所有的列，所以它成爲最後的節點，並給出無限量;任何多餘的水滴將被簡單地堆疊起來：

3(1)->1(1)->2(1)->5(3)->8(4)->6(1)->4(1)->7(1)->9(3)->A(infinite) 

然後我們按照它們列出的順序填充運行，直到我們用完水滴。

Answer 5

這就是我20分鐘的解決方案。 （複製粘貼到您的IDE）只有打印現在才能完成，但滴液滴滴正在他們的位置上。請看：

class Test2{ 
    private static int[] heights = {3,4,4,4,3,2,1,0,4,2,1}; 
    public static void main(String args[]){ 
    int wAmount = 10; 
    int position = 2; 
    for(int i=0; i<wAmount; i++){ 
    System.out.println(i+"#drop"); 
    aDropLeft(position); 
    } 
} 

private static void aDropLeft(int position){ 
    getHight(position); 
    int canFallTo = getFallPositionLeft(position); 
    if(canFallTo==-1){canFallTo = getFallPositionRight(position);} 
    if(canFallTo==-1){ 
    stayThere(position); 
    return; 
    } 
    aDropLeft(canFallTo); 
} 

private static void stayThere(int position) { 
    System.out.print("Staying at: ");log(position); 
    heights[position]++; 
} 

//the position or -1 if it cant fall 
private static int getFallPositionLeft(int position) { 
    int tempHeight = getHight(position); 
    int tempPosition = position; 
    //check left , if no, then check right 
    while(tempPosition>0){ 
    if(tempHeight>getHight(tempPosition-1)){ 
     return tempPosition-1; 
    }else tempPosition--; 
    } 
    return -1; 
} 

private static int getFallPositionRight(int position) { 
    int tempHeight = getHight(position); 
    int tempPosition = position; 
    while(tempPosition<heights.length-1){ 
    if(tempHeight>getHight(tempPosition+1)){ 
     return tempPosition+1; 
    }else if(tempHeight<getHight(tempPosition+1)){ 
     return -1; 
    }else tempPosition++; 
    } 
    return -1; 
} 
private static int getHight(int position) { 
return heights[position]; 
} 


private static void log(int position) { 
System.out.println("I am at position: " + position + " height: " + getHight(position)); 
} 
} 

當然可以把代碼優化，但是這就是我的簡單的解決方案

Answer 6

l=[0,1,0,2,1,0,1,3,2,1,2,1] 

def findwater(l): 
    w=0 
    for i in range(0,len(l)-1): 
     if i==0: 
      pass 
     else: 
      num = min(max(l[:i]),max(l[i:]))-l[i] 
      if num>0: 
       w+=num 
    return w 

Answer 7

col_names=[1,2,3,4,5,6,7,8,9,10,11,12,13] #for visualization 
bars=[4,0,2,0,1,0,4,0,5,0,3,0,1] 

pd.DataFrame(dict(zip(col_names,bars)),index=range(1)).plot(kind='bar') # Plotting bars 

def measure_water(l): 
    water=0 
    for i in range(len(l)-1): # iterate over bars (list) 
     if i==0:    # case to avoid max(:i) situation in case no item on left 
      pass 
     else: 
      vol_at_curr_bar=min(max(l[:i]),max(l[i:]))-l[i] #select min of max heighted bar on both side and minus current height 
      if vol_at_curr_bar>0: # case to aviod any negative sum 
       water+=vol_at_curr_bar 
    return water 

measure_water(bars)