twitter 水たまりアルゴリズムの JavaScript 実装 example_javascript スキル

今日、非常に興味深いアルゴリズムの質問を見つけました。以下は、Twitter でのインタビューの質問から派生したアルゴリズムの説明です。

Twitter 水たまりアルゴリズムの説明

まず写真を見てください

上の図の数値は配列の内容に基づいて記述されており、最後に各数値のサイズに基づいて壁の高さがシミュレートされ、最終的に壁が生成されます。雨が降ったら、この壁に設置できます。水の量は1個単位です。

水を満たした後の壁は次のようになります

上の図を読んだ後、非常に興味深いと思います。アルゴリズムの実装を簡単に分析してみましょう。

実際、この原則は比較的単純です:

1. 左端と右端は水で満たされてはなりません
2. 水の充填の高さは、左側と右側の 2 つの最大値の最小値に依存します

以下では、js を使用して単純に実装します。

コードをコピーします コードは次のとおりです:

/**
* 配列アイテムを高さにした壁が保持できる水の量を計算します
* 配列の例 [2,5,1,2,3,4,7,7,6,9]
**/
function getWaterCounts(arg){
var i = 0,
j = 0,
カウント = 0;
// 最初と最後の項目の両方を除外する必要があります
for(i = 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] カウント = 分 - arg[i];
}
}
console.log(カウント);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]); // 11

概要

実装は非常に簡単です。実際、考える意欲さえあれば、js を使用して多くの楽しいことを実現できます。