今日、私は非常に興味深いアルゴリズムの質問を見つけました。以下は、Twitterでのインタビューの質問からのアルゴリズムの説明です。
Twitter Puddlesアルゴリズムの説明
最初に写真を見てください
上の図の数字は、配列の内容に従って説明されています。最後に、各数のサイズに応じて壁の高さがシミュレートされ、壁が生成されます。雨が降ったら、カウントユニットとして1で、この壁にどれだけの水を満たすことができるかを尋ねてください。
これが水を満たした後の壁です
上記の写真を読んだ後、楽しいと思いますか？実際、以下のアルゴリズムの実装を簡単に分析しましょう。
実際、この原則は比較的単純です。いくつかの重要なポイントがあります。
1.左側と右側には間違いなく水がありません
2。水負荷の高さは、自分の左側と右側の2つの最大値の最小値に依存します
JSを使用して簡単に実装しましょう。
コードコピーは次のとおりです。
/**
*高さとして配列項で壁にどれだけの水を設置できるかを計算します
*配列の例[2,5,1,2,3,4,7,6,9]
**/
関数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 =左> =右？右：左;
//左側と右側の最大値が勝つものとする
//現在の値がこの値以上の場合は、何もしません
if（arg [i] <min）{
count += min -arg [i];
}
}
console.log（count）;
}
getWaterCounts（[2,5,1,2,3,4,7,7,6,9]）; // 11
要約します
Hehe、実装は非常に簡単ではありませんか？実際、あなたが喜んで考えている限り、JSを使用して多くの楽しいものを実装することができます。