スタックの実装です。 スタックのデータ構造はLIFO（後入れ先出し）です。 スタックは以下の操作ができます。 pop: スタックの一番上のデータを削除する push: スタックの一番上にデータを追加する peek: スタックの一番上の要素を返す isEmpty: スタックが…

問題 ある集合の全ての部分集合を返す 考え方 再帰的に考える。 N-1この要素の全ての部分集合がわかっているときに、次の部分集合はどうなるか？ N個目の要素を加えたsubsetsを元のsubsetsに加えれば良い。 f(n) = f(n-1) + {f(n-1), set[n]} コード例 def a…

問題 ソートされた配列からA[i] = iとなるindexを探す。配列が重複した値を持つ場合にどうするか。 考え方 2分探索的な方法で探す。 重複した値がある時は少しややこしくて、結局両側を探すしかない。ただし、探す範囲は mid > A[mid]ならば、左側はindexが0…

問題 Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. You can assume that the messages are decodable. For example, '001' is not allowed. 考え方 stringが与えられた時のデコード方…