[leetcode][42]Trapping Rain Water問題を解決!
5159 ワード
ああ...特別な銭湯を建てたいのですが...でもどれだけの水が必要かはわかりませんが...彼を助けてくれませんか.
トピックコードのホームページと問題の説明を参照してください.問題に答える
🔑 問題を解く
代表的なのはこれらの問題の大部分が2 pointer問題です!!
まず水位を考えてみましょう[2,0,0,3]を入力して、左柱の高さ2、右柱の高さ3を入力します.
そのため、水を充てると左が右より低いので、高さ2までしか充てることができません.
この原理を用いて,左から右へ参照ポインタを生成し,逆に右から左へ参照ポインタを生成する.
左から1つ見ると、現在の柱が右参照の柱の高さ以下またはそれに等しい場合は、水を1つ充填し、逆に右の柱がより低い場合は、右側の水を充填する形で行います.満たされた量は現在の水の高さ-現在の柱の高さです低いところからゆっくりと水がいっぱい入っているようにしましょう.
左から右に行くにしても、どちらから基準を決めるにしても、私は左から基準を決めます.
だから私はどうやって解いたの?
水を加えるときの高さが一番重要です.
水の高さは左柱と右柱の高さを比較し、低い値とこれまでの水の高さでより大きな値を選択します.
わかりやすいように、次のようにマークされます.
Math.max(fixH, Math.min(height[left], height[right]));
// fixH가 물의 높이다.
そして左の右のどこを埋めるかを選択すればいい!!🥽 ソースコードとソースコード分析
var trap = function (height) {
let answer = 0;
let left = 0;
let right = height.length - 1;
let fixH = 0;
while (left < right) {
fixH = Math.max(fixH, Math.min(height[left], height[right]));
if (height[left] <= fixH) {
answer += fixH - height[left];
left++;
} else {
answer += fixH - height[right];
right--;
}
}
return answer;
};
🔨 問題ポストおもしろい.
最初はかなり長いコードを書きました.私はもともと設計がうまくいかなかったので,解がうまくいかず,途中で値段を変えて,直して問題を通過した.
他の人が入れているとてもきれいなソースを見て、少し恥ずかしい感じと少し悟りました.
コードが簡潔であればあるほど、エラーは少なくなります.
今後はコードを簡潔に書く必要があるかもしれません.
Reference
この問題について([leetcode][42]Trapping Rain Water問題を解決!), 我々は、より多くの情報をここで見つけました https://velog.io/@qnfmtm666/leetcode42-Trapping-Rain-Water-문제풀기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol