解答と解説: Fibonacci Sequences

「問題演習: Fibonacci Sequences」の解答編です。Web 上でよく見かけるフィボナッチ数列のプログラムは再帰を使っています。今回は再帰を使うことができないという制約を付けて問題を出題しました。

問題演習: Fibonacci Sequences

今回は「Fibonacci Sequences」という問題です。日本語で「フィボナッチ数列」というとご存知の方も多く、実際にプログラムを作成したことがある方も多いと思います。実際に面接でフィボナッチ数列を書けという簡単な問題は出題されないと思いますが、問題を掘り下げると実はフィボナッチ数列を書けば解けるような問題があったりします。そのときのために一応解いておきましょう。また、よくあるプログラムは再帰を使う解法ですが、再帰が使えないように制約を加えました。難易度は「Easy」です。

解答と解説: Average of each Level in Binary Tree

「問題演習: Average of each Level in Binary Tree」の解答編です。問題出題時に述べたように、この問題は本サイトに掲載してきた 2 分木に関する問題「Max Depth of Binary Tree」や「Find Max Element per Level in Binary Tree」と似ており、解答も非常に似ています。そのため、解答例の細かい解説はそちらの記事を見ていただきたいと思います。今回の解説では問題出題時の最後に記載した "もし数値の 1 つが int 型の最大値だった場合" について解法を紹介したいと思います。

問題演習: Average of each Level in Binary Tree

今回は「Average of each Level in Binary Tree」という問題です。この問題はこれまでに本サイトに掲載してきた 2 分木に関する問題「Max Depth of Binary Tree」や「Find Max Element per Level in Binary Tree」と似ているので掲載するか迷ったのですが、1 点だけ注意してほしいことがあったので掲載することにしました。その注意して欲しい点は下記の「解答を見る前に」に記載したので考えてみてください。難易度は「Easy」です。

解答と解説: Symmetric Binary Tree

「問題演習: Symmetric Binary Tree」の解答編です。今回は再帰を用いた解答例と深さ優先探索を用いた解答例の 2 つを用意しました。

問題演習: Symmetric Binary Tree

今回は「Symmetric Binary Tree」という問題です。Symmetric とは左右対称のことです。難易度は「Easy」です。

解答と解説: Longest Palindrome

「問題演習: Longest Palindrome」の解答編です。今回は直感的で分かりやすい解法と少し最適化を施した解法の 2 種類の解答を用意しました。

問題演習: Longest Palindrome

今回は「Longest Palindrome」という問題です。難易度は「Easy」です。Palindrome とは回文のことです。前後のどちらから読んでも同じように読める文です。

解答と解説: Hamming Weight

「問題演習: Hamming Weight」の解答編です。模範解答に加え、Java が提供している便利なメソッドを使った解答を用意しました。

問題演習: Hamming Weight

今回は「Hamming Weight」という問題です。日本語ではハミング重みです。以前出題し Hamming Distance と類似の問題ですが、ビット演算のおさらいも兼ねて挑戦しましょう。難易度は「Easy」です。

解答と解説: Add Binary Strings

「問題演習: Add Binary Strings」の解答編です。この問題のポイントとしては、文字列で表記された 2 進数を最下位のビットから計算する際に桁上げ処理を忘れずに行うことです。それでは解答例を見ていきましょう。

問題演習: Add Binary Strings

今回は「Add Binary Strings」という問題です。難易度は「Easy」です。 2 つの 2 進数が文字列で与えられる。これらの和を 2 進数の文字列で返せ。

解答と解説: Reverse Digits of Integer

「問題演習: Reverse Digits of Integer」の解答編です。今回の解答では 2 つのポイントがありますので、それらを中心に解説します。

問題演習: Reverse Digits of Integer

今回は「Reverse Digits of Integer」という問題です。難易度は「Easy」です。与えられた整数の桁を反転せよ。ただし、反転後の整数が int 型に入らない場合は 0 を返せ。

解答と解説: Identical Binary Trees

「問題演習: Identical Binary Trees」の解答編です。再帰と深さ優先探索を用いた解答例を示します。

問題演習: Identical Binary Trees

今回は「Identical Binary Tree」という問題です。難易度は「Easy」です。 2 つの二分木が同一か判定せよ。木が同一であるとき、木の形が同じであり、各ノードが保持する値も同じである。

解答と解説: Reverse a String

「問題演習: Reverse a String」の解答編です。解答例を複数載せました。面接で思いついて欲しいのは解答例3ですが、解答例1から順に見ていきましょう。

問題演習: Reverse a String

今回は「Reverse a String」という問題です。難易度は「Easy」です。非常に単純な問題なので、多くの方が解けると思います。その分、ミスが命取りになるので注意しましょう。

解答と解説: Reverse a Singly Linked List

「問題演習: Reverse a Singly Linked List」の解答編です。この問題は単方向リストを逆順に並び替えるという一見すると単純に見える問題ですが、空間計算量を O(1) で処理しなくてはならない点が難易度を上げています。

問題演習: Reverse a Singly Linked List

今回は「Reverse a Singly Linked List」という問題です。シンプルな問題ですが思考過程で混乱しやすい問題です。難易度は「Medium」です。

解答と解説: No Adjacent Neighbors

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

問題演習: No Adjacent Neighbors

今回は「No Adjacent Neighbors」という問題です。難易度は「Easy」です。-- 1 つの boolean 型の配列 a と 1 つの整数 n が与えられる。配列にはいくつかの true と false が既に格納されており、あと n 個の true を格納できるか調べたい。ただし true の隣には false しか置けない。もし、あと n 個の true を格納できるとき true を返し、格納できないときは false を返せ。

解答と解説: Isomorphic Strings

「問題演習: Isomorphic Strings」の解答編です。今回の解答例には、比較的すぐに思いつきそうなものと、簡単な制約がある場合に思いつきたい解答を載せました。

問題演習: Isomorphic Strings

今回は「Isomorphic Strings」という問題です。この問題も非常に有名な問題です。皆に知られすぎている問題なので、面接には出てこないかもしれません。難易度は「Easy」です。

解答と解説: Lowest Common Ancestor in Binary Search Tree

「問題演習: Lowest Common Ancestor in Binary Search Tree」の解答編です。この問題は単なる二分木ではなく、二分探索木であることに注目する必要があります。それらの違いについては解説で述べたいと思います。