DIV CSS 佈局教程網

積水演算法實作:用 JavaScript 解 Twitter puddles 面試題
編輯:關於JavaScript     

這個題目來自 Twitter 的面試題,看起來只是幾何圖形,實際考驗的是對「邊界約束」的抽象能力,蠻有意思。

題目描述

先看下面這張圖:

圖中的數字來自一個陣列,每個數字對應一道牆的高度,組合起來就形成一面高低起伏的牆。問題是:下雨時,這面牆最多能承接多少單位的水?

換成注水之後的樣子如下:

解題關鍵

原理其實不難,掌握兩點即可:

1. 最左側與最右側的格子一定存不了水,因為沒有邊界可擋。
2. 某個位置能蓄到的高度,取決於它左右兩側各自最大值中的「較小者」——木桶效應,短板決定水位。

JavaScript 實作

/**
 *  計算以陣列項為高度的牆能裝多少水
 *  陣列例子 [2,5,1,2,3,4,7,7,6,9]
 **/
function getWaterCounts(arg){
  var i = 0,
      j = 0,
      count = 0;
  // 第一項和最後一項都得排除
  for(i = 1; i < arg.length - 1; i++){
    var left = Math.max.apply(null, arg.slice(0, i + 1));
    var right = Math.max.apply(null, arg.slice(i, arg.length));
    var min = left >= right ? right : left;
    // 以左右兩邊最大值內小的為準
    // 假如當前值大於或者等於這個值什麼都不做
    if(arg[i] < min){
      count += min - arg[i];
    }
  }
  console.log(count);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

這裡的 min - arg[i] 就是該格能承接的水量,若本身高度已達或超過水位則略過。這個版本勝在直白好懂,缺點是每個位置都要 slice 兩次求最大值,時間複雜度為 O(n²)。若資料量龐大,可以改用「預先由左向右、由右向左各掃一次,記下每格的左右最大值」的做法,把複雜度壓到 O(n)。

小結

演算法的樂趣就在這裡:題目聽起來抽象,一旦把「短板決定水位」這個直覺寫成程式,答案便自然浮現。只要願意動腦,JavaScript 能玩出很多有趣的東西。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved