DIV CSS 佈局教程網

用 JavaScript 實作 Twitter 水坑(Puddles)演算法的完整教程
編輯:關於JavaScript     

今天無意間發現了一道挺好玩的演算法題,它源自 Twitter 的一道面試題——「twitter puddles」,就來看看如何用 JavaScript 實現它。

演算法描述

先看一幅圖:

圖中的數字是根據一個陣列的內容而來,每個數字模擬一道牆的高度,最後生成一面牆。問題是:當下雨時,這面牆能裝多少水?以 1 為計數單位。

下面是裝完水之後的樣子:

原理分析

看完圖會發現它其實很好玩。原理也不複雜,主要有兩個要點:

  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

程式邏輯是:對每個位置(排除首尾),分別找出它左側與右側的最大值,取兩者中較小者作為水位上限;若該位置本身高度低於這個上限,就能裝「上限減自身高度」這麼多的水,累加起來即為總水量。

總結

實現起來是不是挺簡單的?其實只要願意動腦,用 JavaScript 能實現很多好玩的東西。這道題也提醒我們:先把問題拆解成清晰的子規則,程式碼自然水到渠成。

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