解答と解説: No Adjacent Neighbors

問題演習: No Adjacent Neighbors」の解答編です。

解答例

Javaでの解答例です。


解説

解答例では配列 bs を先頭から順に調べる際、前後と自身が false のときに自身に true を格納しています。true を格納した数だけ count をインクリメントし、配列をすべて調べた後に count の数が整数 n より大きければ、少なくとも n 個の true を置くことができると言えます。

ポイントとしては、配列を先頭から見ていく際に、前後と自身が false だと分かると躊躇なく自身に true を格納している点です。格納できると分かっても、今は格納しない方が後々になって有利になるかもしれないと思うかもしれません。このような疑問を持った際には図などを使って紙やホワイトボードに数パターン書いてみてください。今回の問題では先頭から順に詰めていくので十分です。

以上が今回の解説になります。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。

このエントリーをはてなブックマークに追加

コメント

このブログの人気の投稿

問題演習: Hamming Weight

解答と解説: Max Depth of Binary Tree

問題演習: Find Max Element per Level in Binary Tree