JavaScript實現(xiàn)twitter puddles算法實例

更新時間：2014年12月06日 11:18:16 投稿：junjie

這篇文章主要介紹了JavaScript實現(xiàn)twitter puddles算法實例,本文源自twitter的一道面試題,本文使用js解開了這首題,需要的朋友可以參考下

今天發(fā)現(xiàn)了一個挺好玩的算法題,下面是它的算法描述,源自twitter的一道面試題。

twitter puddles 算法描述

先看一副圖

上圖里的數(shù)字是根據(jù)一個數(shù)組內(nèi)容來描述的,最后會根據(jù)每個數(shù)字的大小來模擬一道墻的高度,最后生成一面墻,問你,當(dāng)下雨的時候,這面墻可以裝多少水,以1為計數(shù)單位。

下面是裝完水之后的一面墻的樣子

看完上面上幅圖,感覺是不是很好玩,確實,下面來簡單的分析下它的算法實現(xiàn)

其實這個原理比較簡單,總共有下面幾個要點:

1.最左邊和最右邊肯定不能裝水
2.裝水的高度依賴自身左右兩側(cè)內(nèi)兩個最大值其中的最小值

下面我們用js來簡單的實現(xiàn)它：

復(fù)制代碼代碼如下:

/**

*  計算以數(shù)組項為高度的墻能裝多少水

*  數(shù)組例子 [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;

        // 以左右兩邊最大值內(nèi)小的為準(zhǔn)

        // 假如當(dāng)前值大于或者等于這個值什么都不做

        if(arg[i] < min){

            count += min - arg[i];

        }

    }

    console.log(count);

}

getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

總結(jié)

嘿嘿,實現(xiàn)是不是挺簡單的,其實只要你愿意思考,用js可以實現(xiàn)很多好玩的東西.

您可能感興趣的文章:

相關(guān)文章

淺談JSON.stringify()和JOSN.parse()方法的不同
parse 用于從一個字符串中解析出json 對象而stringify用于從一個對象解析出字符串，這篇文章主要介紹了JSON.stringify()和JOSN.parse()方法的不同,需要的朋友可以參考下
2016-08-08
關(guān)于微信小程序登錄的那些事
這篇文章主要給大家介紹了關(guān)于微信小程序登錄的那些事，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2019-01-01
輸入npm?run?xxx后執(zhí)行原理深入解析
這篇文章主要為大家介紹了輸入npm?run?xxx后執(zhí)行原理深入解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2022-07-07
Javascript中valueOf與toString區(qū)別淺析
Javascript中valueOf與toString區(qū)別淺析，需要的朋友可以參考一下
2013-03-03
高性能web開發(fā) 如何加載JS，JS應(yīng)該放在什么位置？
所有瀏覽器在下載JS的時候，會阻止一切其他活動，比如其他資源的下載，內(nèi)容的呈現(xiàn)等等。至到JS下載、解析、執(zhí)行完畢后才開始繼續(xù)并行下載其他資源并呈現(xiàn)內(nèi)容。
2010-05-05
JS實現(xiàn)橫向跑馬燈效果代碼
這篇文章主要介紹了JS實現(xiàn)橫向跑馬燈效果代碼,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
2020-04-04
js中的this關(guān)鍵字詳解
this是Javascript語言的一個關(guān)鍵字它代表函數(shù)運行時，自動生成的一個內(nèi)部對象，只能在函數(shù)內(nèi)部使用,下面分四種情況，詳細討論this的用法，感興趣的朋友可以了解下
2013-09-09
JavaScript實現(xiàn)打地鼠游戲
這篇文章主要為大家詳細介紹了JavaScript實現(xiàn)打地鼠游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-10-10
Javascript設(shè)計模式之觀察者模式(推薦)
觀察者模式有時也稱為發(fā)布--訂閱模式，在觀察者模式中，有一個觀察者可以管理所有的目標(biāo)，等到有狀態(tài)發(fā)生改變的時候發(fā)出通知
2016-03-03
手把手教你在微信小程序中使用three.js(保姆級教程)
Three.js是一款運行在瀏覽器中的3D引擎,你可以用它創(chuàng)建各種三維場景,包括了攝影機、光影、材質(zhì)等各種對象,下面這篇文章主要給大家介紹了關(guān)于如何在微信小程序中使用three.js的保姆級教程,需要的朋友可以參考下
2023-03-03