挿入ソートのアルゴリズム 与えられた配列をソートする際、挿入ソートを用いるとする。 与えられた配列を、ソート済みの配列(長さは1)と未ソートの配列に分割する。未ソートの配列の中から一つ選び、ソート済みの配列に挿入する。挿入された値と、隣り合う要…

配列の積和演算のアルゴリズム 「特別な配列」が与えられるので積和演算を行って値を返す。「特別な配列」は数値あるいは「特別な配列」をもつ。「特別な配列」内の数値をすべて加算するが、ネストレベルに応じてその和を乗算する。 例えば、 [x, y] → x + y…

二分探索木(binary search tree)から近似値を求める 二分探索木のデータとtargetが与えられる。二分探索木のデータの中からtargetの近似値を求める。 例えば次のような二分探索木のデータとtarget 5が与えられるとき、答えは6である。 8 /\ 3 10 /\ \ 1 6 14…

2つの数の和 2つ以上のユニークな数字の集合Aの中から、ターゲット(target)の数字の和となる数字のペアを見つけ出す。数字のペアは最大1つある。答えは値が小さい順に並べるとする。 例えばAが1, 10, 5, -1、12、targetが15であれば、答えは10, 5のペアであ…

バイナリサーチ 問: ソートされた数値の配列と数値targetを受け取り、配列中のtargetのインデックスを求める。その際、バイナリサーチを用いること。 アルゴリズム実装 $O(\log n)$ 配列の要素数をnとしたとき、left=0、right=nの変数を作る。また、leftとri…

Palindrome Check (回文チェック) アルゴリズム 文字列stringを受け取って、回文かどうかをチェックする。すべての文字を比較しないといけないので、どうやっても計算量が$O(n)$以上になるはず。 アルゴリズム実装(1) $O(n)$ 両端から文字が等しいか比較して…

フィボナッチ数列のアルゴリズム 勉強がてらメモ フィボナッチ数列とは 「フィボナッチ数列」とは「前の２つの数を加えると次の数になる」という数列。1番目は0、2番目は1。n番目の数字は(n - 1)番目と(n - 2)番目の数字の和。 例えば、6番目の数は5 (0, 1, …