コーディング面接で
アルゴリズムのチートシートに、
日本の企業のコーディングテストの形と対策に、
標準入力から
この頁の目次25 項目
難度と出題の頻度の見方
出題の頻度は、海外でよく使われる定番の問題リスト 4 本 (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150) に何本入っているかで、よく出る・ときどき出る・少なめ の 3 段階に分けています。少なめは、
難度の目安
- 型を
1 つ 知っていれば 解ける 基本の 問い。 LeetCode の Easy ほど - 型を
選び、 端の 場合まで 詰めて 解く 問い。 LeetCode の Medium ほど - 型を
組み合わせるか、 計算量を 一段縮める 工夫が 要る 問い。 Medium の 難しい 物と Hard - いく
つもの 操作を 持つ仕組みを、 データの 持ち方から 設計して作る問い
準備の
最優先の 8 問先にここから
文字列
配列とハッシュ
Two Sum を
ハッシュマップで解く 整数の
並びから、 足すと 目標の 数に なる 2 つを 探し、 その 位置を 返す。 見た数を 辞書に 覚えて おくと、 並びを 1 回なめるだけで 見つかります。 
アナグラムか
どうかを ハッシュで 判定する 2 つの
文字列が、 文字を 並べ替えるだけで 同じに できるかを 調べる。 並べ替えて 比べる 書き方と、 文字の 数を 数える 書き方を 比べる 練習です。 
ハッシュで
最初の 重複しない 文字を探す 文字列の
中で 1 回しか 出ない 文字の うち、 いちばん前に ある物の 位置を 返す。 先に 全部を 数え、 もう 1 回読んで 探す、 2 回なめる 考え方の 練習です。 集合で
同じ値が 2 回出てくるかを 確かめる 整数の
並びの 中に、 同じ 値が 2 回以上 出てくるかを 判定します。 見た値を 集合に 覚え、 出てきた 値が もう 集合に あるかを 一定の 手間で 調べる 練習です。 辞書で
同じ 文字で できた 語を 組に 分ける 文字を
並べ替えると 同じに なる 語どうしを、 1 つの 組に まとめます。 語ごとに 文字の 数を 数えた物を 辞書の 鍵に して、 同じ鍵の 語を 集める 練習です。 左右からの
積で 自分以外の 積を 並べる 整数の
並びの 各位置に ついて、 その 位置を 除いた 全部の 数の 積を 並べて 返します。 割り算を 使わず、 左からの 積と 右からの 積を 2 回なめて 掛け合わせる 練習です。 集合で
数独の 盤に 同じ 数字の 重なりが 無いか 確かめる 途中まで
数字の 入った 9 × 9 の 数独の 盤で、 行、 列、 3 × 3 の 箱の どれにも 同じ 数字が 2 回入っていないかを 確かめます。 見た 数字を 「どの 行、 どの 列、 どの 箱か」と 組に して 集合に 覚える、 ハッシュの 練習です。 前からの
合計と 辞書で 和が ちょうど k に なる 区間を 数える 日ごとの
増減の 並びから、 続いた 日の 合計が ちょうど k に なる 区間の 数を 数えます。 前からの 合計を 辞書に 数えて おき、 「いまの 合計から k を 引いた 値」が 何回出たかを 足していく、 ハッシュの 練習です。 集合で
並べ替えずに 1 ずつ続く 数の 最長を 求める ばらばらに
並んだ 整数から、 1 ずつ続いて 並べられる 数の、 いちばん長い 続きの 長さを 求めます。 値を 集合に 入れ、 続きの 先頭の 数からだけ 数えて O(n) に する、 ハッシュの 練習です。
- Two Sum を
ハッシュマップで解く整数の並びから、足すと目標の数になる 2 つを探し、その位置を返す。見た数を辞書に覚えておくと、並びを 1 回なめるだけで見つかります。 - アナグラムか
どうかを ハッシュで判定する2 つの文字列が、文字を並べ替えるだけで同じにできるかを調べる。並べ替えて比べる書き方と、文字の数を数える書き方を比べる練習です。 - ハッシュで
最初の 重複しない 文字を探す文字列の中で 1 回しか出ない文字のうち、いちばん前にある物の位置を返す。先に全部を数え、もう 1 回読んで探す、2 回なめる考え方の練習です。 - 集合で
同じ 値が 2 回出てくるかを確かめる整数の並びの中に、同じ値が 2 回以上出てくるかを判定します。見た値を集合に覚え、出てきた値がもう集合にあるかを一定の手間で調べる練習です。 - 辞書で
同じ 文字で できた語を 組に分ける文字を並べ替えると同じになる語どうしを、1 つの組にまとめます。語ごとに文字の数を数えた物を辞書の鍵にして、同じ鍵の語を集める練習です。 - 左右からの
積で 自分以外の 積を並べる整数の並びの各位置について、その位置を除いた全部の数の積を並べて返します。割り算を使わず、左からの積と右からの積を 2 回なめて掛け合わせる練習です。 - 集合で
数独の 盤に 同じ 数字の 重なりが 無いか確かめる途中まで数字の入った 9 × 9 の数独の盤で、行、列、3 × 3 の箱のどれにも同じ数字が 2 回入っていないかを確かめます。見た数字を「どの行、どの列、どの箱か」と組にして集合に覚える、ハッシュの練習です。 - 前からの
合計と 辞書で 和が ちょうど k に なる 区間を数える日ごとの増減の並びから、続いた日の合計がちょうど k になる区間の数を数えます。前からの合計を辞書に数えておき、「いまの合計から k を引いた値」が何回出たかを足していく、ハッシュの練習です。 - 集合で
並べ替えずに 1 ずつ続く 数の 最長を求めるばらばらに並んだ整数から、1 ずつ続いて並べられる数の、いちばん長い続きの長さを求めます。値を集合に入れ、続きの先頭の数からだけ数えて O(n) にする、ハッシュの練習です。
数学と行列
見た数を
集合に 覚え、 桁の 2 乗の 和を 繰り返して 1 に 着くかを 確かめる 正の
整数を 「各桁の 2 乗の 和」に 置き換える 操作を 繰り返し、 いつか 1 に 着くかを 判定します。 同じ数に もう 一度 来たら 輪に 入ったと 分かるので、 見た数を 集合に 覚えて 止める 練習です。 
下の
桁から 繰り 上がりを 運び、 桁の 並びに 1 を足す 10 進の
数を 上の 桁から 並べた 桁の 並びに 1 を 足し、 結果も 桁の 並びで 返します。 数に 直さず、 いちばん下の 桁から 繰り 上がりを 運び、 全部 9 の ときだけ頭に 1 を 足す練習です。 
転置してから
各行を 逆にし、 正方形の 行列を 時計回りに 90 度回す n×n の
行列を、 新しい 行列を 作らずに その 場で 時計回りに 90 度回します。 行と 列を 入れ替える 転置と、 各行の 左右の 反転の 2 つに 分ければ、 どちらも 入れ替えだけで 書ける 練習です。 4 つの
境目を 狭めながら、 行列を 渦巻きの 順に読む m×n の
行列を、 左上から 時計回りに 外側の 枠から 内側へ 渦巻きの 順に 読んだ 並びを 返します。 上、 下、 左、 右の 4 つの 境目を 持ち、 1 辺を 読むたびに 1 つ 狭める 練習です。 先頭の
行と 列を 印の 置き場にし、 0 の ある 行と 列を 全部 0 にする 行列の
中に 0 が あれば、 その 行と 列を 全部 0 にします。 どの 行と 列を 消すかの 印を、 行列の 先頭の 行と 先頭の 列に 書き込めば、 追加の 記憶を O(1) に 抑えられる 練習です。 繰り返し 2 乗で
掛ける 回数を 減らし、 x の n 乗を 求める 小数 x と、
負も ありうる 整数 n から、 x の n 乗を 求めます。 n を 2 進で 見て、 x を 2 乗し続けながら 1 の ビットの 所だけ掛ければ、 掛け算の 回数が n の 桁の 数ほどで 済む練習です。 筆算の
位ごとの 置き場に 積を 足し、 数字の 文字列どうしを 掛ける 10 進の
数字だけで できた 2 つの 文字列の 積を、 文字列で 返します。 大きい 整数の 型に 直さず、 桁どうしの 積を 筆算の 位ごとの 置き場に 足し、 最後に 繰り上げを まとめる 練習です。 点の
数を 辞書に 数え、 向かいの 角から 軸に そろった 正方形を 数える 平面に
点を 足していき、 ある 点を 1 つの 角と する 軸に そろった 正方形が 何通り 作れるかを 数える 仕組みを 作ります。 点ごとの 個数を 辞書に 持ち、 向かいの 角を 決めれば 残りの 2 つの 角が 決まる、と 気づく 練習です。
- 見た
数を 集合に 覚え、 桁の 2 乗の 和を 繰り返して 1 に 着くかを確かめる正の整数を「各桁の 2 乗の和」に置き換える操作を繰り返し、いつか 1 に着くかを判定します。同じ数にもう一度来たら輪に入ったと分かるので、見た数を集合に覚えて止める練習です。 - 下の
桁から 繰り 上がりを 運び、 桁の 並びに 1 を足す10 進の数を上の桁から並べた桁の並びに 1 を足し、結果も桁の並びで返します。数に直さず、いちばん下の桁から繰り上がりを運び、全部 9 のときだけ頭に 1 を足す練習です。 - 転置してから
各行を 逆にし、 正方形の 行列を 時計回りに 90 度回すn×n の行列を、新しい行列を作らずにその場で時計回りに 90 度回します。行と列を入れ替える転置と、各行の左右の反転の 2 つに分ければ、どちらも入れ替えだけで書ける練習です。 - 4 つの
境目を 狭めながら、 行列を 渦巻きの順に読むm×n の行列を、左上から時計回りに外側の枠から内側へ渦巻きの順に読んだ並びを返します。上、下、左、右の 4 つの境目を持ち、1 辺を読むたびに 1 つ狭める練習です。 - 先頭の
行と 列を 印の 置き場にし、 0 の ある 行と 列を 全部 0 にする行列の中に 0 があれば、その行と列を全部 0 にします。どの行と列を消すかの印を、行列の先頭の行と先頭の列に書き込めば、追加の記憶を O(1) に抑えられる練習です。 - 繰り返し 2 乗で
掛ける 回数を 減らし、 x の n 乗を求める小数 x と、負もありうる整数 n から、x の n 乗を求めます。n を 2 進で見て、x を 2 乗し続けながら 1 のビットの所だけ掛ければ、掛け算の回数が n の桁の数ほどで済む練習です。 - 筆算の
位ごとの 置き場に 積を 足し、 数字の 文字列どうしを掛ける10 進の数字だけでできた 2 つの文字列の積を、文字列で返します。大きい整数の型に直さず、桁どうしの積を筆算の位ごとの置き場に足し、最後に繰り上げをまとめる練習です。 - 点の
数を 辞書に 数え、 向かいの 角から 軸に そろった 正方形を数える平面に点を足していき、ある点を 1 つの角とする軸にそろった正方形が何通り作れるかを数える仕組みを作ります。点ごとの個数を辞書に持ち、向かいの角を決めれば残りの 2 つの角が決まる、と気づく練習です。
ビット操作
全部を
XOR で まとめ、 1 回だけ出てくる 値を 見つける 1 つを
除いてどの 値も ちょうど 2 回ずつ 出てくる 並びから、 1 回だけ出てくる 値を 返します。 同じ 値どうしの XOR は 0 に なるので、 全部を XOR で まとめれば対の 値が 消えて 1 つだけ 残る 練習です。 
いちばん下の
1 を 消していき、 2 進の 1 の 数を 数える 0 以上の
整数を 2 進で 書いた ときの 1 の 数を 返します。 n & (n - 1) で いちばん下の 1 の ビットを 1 つずつ消せば、 1 の 数の 回数だけ回して 数えられる 練習です。 
半分の
数の 答えを 使い回し、 0 から n までの 1 の ビットの 数を 並べる 0 から
n までの 各数に ついて、 2 進で 書いた ときの 1 の 数を 並べて 返します。 i を 1 ビット 右へずらした 数の 答えは もう 出ているので、 それに いちばん下の ビットを 足すだけで 次々に 埋まる 練習です。 下の
ビットから 取り出して 上へ 積み、 32 ビットを 逆順にする 0 以上の
整数を 32 ビットの 並びと して 見て、 ビットの 並びを 左右逆に した 数を 返します。 下の ビットを 1 つずつ 取り出し、 答えを 左へずらしながら 積んでいく 練習です。 番号と
値を 全部 XOR で まとめ、 0 から n の 中で 抜けた 数を 見つける 0 から
n までの n + 1 個の 数の うち、 1 つだけが 抜けた 長さ n の 並びから、 抜けた 数を 返します。 0 から n の 番号と 並びの 値を 全部 XOR で まとめれば、 そろった 数は 打ち消し合って 抜けた 数だけが 残る 練習です。 XOR と
AND の 繰り 上がりで、 + を 使わずに 2 つの 整数を足す + と
- を 使わずに、 2 つの 整数の 和を 求めます。 繰り 上がりを 無視した 和は XOR、 繰り 上がりは AND を 1 ビット 左へずらした 値なので、 繰り 上がりが 0 に なるまで 2 つを 足し直す練習です。 足す前に
あふれを 確かめながら、 32 ビットの 整数の 桁を 逆順にする 32 ビットの
符号つき整数の 10 進の 桁を 逆順に した 数を 返し、 範囲を 出るなら 0 を 返します。 64 ビットの 型に 頼らず、 桁を 1 つ 積む前に 「積んだら あふれるか」を 確かめる 練習です。
- 全部を
XOR で まとめ、 1 回だけ 出てくる 値を見つける1 つを除いてどの値もちょうど 2 回ずつ出てくる並びから、1 回だけ出てくる値を返します。同じ値どうしの XOR は 0 になるので、全部を XOR でまとめれば対の値が消えて 1 つだけ残る練習です。 - いちばん下の
1 を 消していき、 2 進の 1 の 数を数える0 以上の整数を 2 進で書いたときの 1 の数を返します。n & (n - 1) でいちばん下の 1 のビットを 1 つずつ消せば、1 の数の回数だけ回して数えられる練習です。 - 半分の
数の 答えを 使い回し、 0 から n までの 1 の ビットの 数を並べる0 から n までの各数について、2 進で書いたときの 1 の数を並べて返します。i を 1 ビット右へずらした数の答えはもう出ているので、それにいちばん下のビットを足すだけで次々に埋まる練習です。 - 下の
ビットから 取り出して 上へ 積み、 32 ビットを 逆順にする0 以上の整数を 32 ビットの並びとして見て、ビットの並びを左右逆にした数を返します。下のビットを 1 つずつ取り出し、答えを左へずらしながら積んでいく練習です。 - 番号と
値を 全部 XOR で まとめ、 0 から n の 中で 抜けた 数を見つける0 から n までの n + 1 個の数のうち、1 つだけが抜けた長さ n の並びから、抜けた数を返します。0 から n の番号と並びの値を全部 XOR でまとめれば、そろった数は打ち消し合って抜けた数だけが残る練習です。 - XOR と
AND の 繰り 上がりで、 + を 使わずに 2 つの 整数を足す+ と - を使わずに、2 つの整数の和を求めます。繰り上がりを無視した和は XOR、繰り上がりは AND を 1 ビット左へずらした値なので、繰り上がりが 0 になるまで 2 つを足し直す練習です。 - 足す前に
あふれを 確かめながら、 32 ビットの 整数の 桁を 逆順にする32 ビットの符号つき整数の 10 進の桁を逆順にした数を返し、範囲を出るなら 0 を返します。64 ビットの型に頼らず、桁を 1 つ積む前に「積んだらあふれるか」を確かめる練習です。
ツーポインタ
ツーポインタで
回文を 判定する 英字と
数字だけを 見て、 大文字と 小文字を 区別せずに 回文か どうかを 調べる。 両端に 置いた 2 つの 指を、 まん中へ 寄せていく 考え方 (ツーポインタ) の 練習です。 
ツーポインタで
0 を 配列の 末尾へ移す 整数の
並びの 0 を 全部 後ろへ 寄せ、 0 でない 数の 順は 保ちます。 書き込む 位置の 指と 読む指の 2 つを 使い、 新しい 並びを 作らずに 入れ替える 練習です。 
ソート
済み配列の Two Sum を ツーポインタで解く 小さい
順に 並んだ 整数の 並びから、 足すと 目標に なる 2 つの 位置を 返します。 両端に 指を 置いて 内側へ 寄せ、 余分な 記憶を 使わずに 探す練習です。 ツーポインタで
水を 最も 多く ためる 2 本の 板を選ぶ 高さの
違う 板の 並びから 2 本を 選び、 間に ためられる 水の 量の いちばん 大きい 値を 返します。 両端に 指を 置き、 低い側の 指だけを 内側へ 寄せる 理由まで 言える 練習です。 ソートと
ツーポインタで 目標に いちばん近い 3 つの 和を 求める 整数の
並びから 3 つを 選んで 足し、 目標に いちばん近い 和を 返します。 並べ替えてから 1 つを 決め、 残りの 2 つを 両端の 指で 寄せて 探す練習です。 3 本の
指で 0 と 1 と 2 の 並びを 1 回で 並べ替える 0 と
1 と 2 だけが 入った 並びを、 その 場で 小さい 順に 並べ替えて 返します。 3 本の 指で 並びを 4 つの 区画に 分け、 1 回なめるだけで 仕分ける 練習です。 まん中から
広げて 最も 長い回文の 部分 文字列を探す 文字列の
中で、 前から 読んでも 後ろから 読んでも 同じに なる、 いちばん長い ひと 続きの 部分を 返します。 まん中に 2 本の 指を 置き、 両側へ 広げて 確かめる 練習です。 まん中から
広げて 回文に なっている 部分文字列を 全部 数える 文字列の
続いた 一部の うち、 前から 読んでも 後ろから 読んでも 同じに なる 物が いくつあるかを 数えます。 回文の まん中を 1 つずつ 決め、 左右の 2 本の 指を 外へ 広げて 数える 練習です。 並べ替えと
ツーポインタで 和が 0 に なる 3 つ組を 全部出す 整数の
並びから、 足すと 0 に なる 3 つの 数の 組を、 同じ組を 2 回出さずに 全部 返します。 並べ替えて 1 つ目を 固定し、 残り 2 つを ツーポインタで 探し、 重なりを 飛ばす理由まで 言える 練習です。 ソートと
ツーポインタで 和が 目標に なる 4 つの 組を 全部 集める 整数の
並びから、 足すと 目標に なる 4 つの 数の 組を、 重ならないように 全部 返します。 並べ替えてから 外側の 数を 順に 決め、 最後の 2 つを 両端の 指で 探す形に 組み立てる 練習です。 ツーポインタで
並んだ壁の あいだに たまる 雨水の 量を 求める 幅 1 の
壁の 高さの 並びから、 雨が 降った あと 壁の あいだに たまる 水の 量を 求めます。 両端から 2 本の 指を 寄せ、 低い 側の 水の 高さは もう 決まっていると 見抜く、 ツーポインタの 練習です。
- ツーポインタで
回文を判定する英字と数字だけを見て、大文字と小文字を区別せずに回文かどうかを調べる。両端に置いた 2 つの指を、まん中へ寄せていく考え方 (ツーポインタ) の練習です。 - ツーポインタで
0 を 配列の 末尾へ移す整数の並びの 0 を全部後ろへ寄せ、0 でない数の順は保ちます。書き込む位置の指と読む指の 2 つを使い、新しい並びを作らずに入れ替える練習です。 - ソート済み配列の
Two Sum を ツーポインタで解く小さい順に並んだ整数の並びから、足すと目標になる 2 つの位置を返します。両端に指を置いて内側へ寄せ、余分な記憶を使わずに探す練習です。 - ツーポインタで
水を 最も 多く ためる 2 本の板を選ぶ高さの違う板の並びから 2 本を選び、間にためられる水の量のいちばん大きい値を返します。両端に指を置き、低い側の指だけを内側へ寄せる理由まで言える練習です。 - ソートと
ツーポインタで 目標に いちばん近い 3 つの 和を求める整数の並びから 3 つを選んで足し、目標にいちばん近い和を返します。並べ替えてから 1 つを決め、残りの 2 つを両端の指で寄せて探す練習です。 - 3 本の
指で 0 と 1 と 2 の 並びを 1 回で 並べ替える0 と 1 と 2 だけが入った並びを、その場で小さい順に並べ替えて返します。3 本の指で並びを 4 つの区画に分け、1 回なめるだけで仕分ける練習です。 - まん中から
広げて 最も 長い 回文の 部分文字列を探す文字列の中で、前から読んでも後ろから読んでも同じになる、いちばん長いひと続きの部分を返します。まん中に 2 本の指を置き、両側へ広げて確かめる練習です。 - まん中から
広げて 回文に なっている 部分文字列を 全部数える文字列の続いた一部のうち、前から読んでも後ろから読んでも同じになる物がいくつあるかを数えます。回文のまん中を 1 つずつ決め、左右の 2 本の指を外へ広げて数える練習です。 - 並べ替えと
ツーポインタで 和が 0 に なる 3 つ組を全部出す整数の並びから、足すと 0 になる 3 つの数の組を、同じ組を 2 回出さずに全部返します。並べ替えて 1 つ目を固定し、残り 2 つをツーポインタで探し、重なりを飛ばす理由まで言える練習です。 - ソートと
ツーポインタで 和が 目標に なる 4 つの 組を 全部集める整数の並びから、足すと目標になる 4 つの数の組を、重ならないように全部返します。並べ替えてから外側の数を順に決め、最後の 2 つを両端の指で探す形に組み立てる練習です。 - ツーポインタで
並んだ壁の あいだに たまる 雨水の 量を求める幅 1 の壁の高さの並びから、雨が降ったあと壁のあいだにたまる水の量を求めます。両端から 2 本の指を寄せ、低い側の水の高さはもう決まっていると見抜く、ツーポインタの練習です。
スライディングウィンドウ
窓の
左端に 最安値を 置いて 1 回の 売り 買いの 利益を 最大にする 日ごとの
値段の 並びから、 1 回だけ 買って、 それより 後の 日に 1 回だけ売る ときの、 いちばん 大きい 利益を 返します。 窓の 左端を それまでの 最安の 日に 置き、 右端を 1 日ずつ 進める 練習です。 
スライディングウィンドウで
続いた 1 の 最長を 数える 0 と
1 だけの 並びから、 1 が いちばん長く 続いた 所の 長さを 返します。 並びを 1 回なめながら、 いま続いている 長さと 最長を 覚えて おく 練習です。 
スライディングウィンドウで
幅 k の 平均が 最大の 所を探す 整数の
並びで、 続いた k 個の 平均が いちばん 大きくなる 所を 探し、 その k 個の 合計を 返します。 窓を 1 つずらすたびに、 入る 数を 足して 出る 数を 引く 練習です。 スライディングウィンドウで
同じ 文字の 無い 最長の 部分を探す 文字列の
中で、 同じ 文字が 2 回出て こない 続いた 部分の うち、 いちばん長い物の 長さを 返します。 左右の 端を 持つ窓を 伸ばし、 重なりが 出たら 左の 端を 飛ばして 縮める 練習です。 スライディングウィンドウで
k 枚まで 塗り 替えて 同じ色の 最長の 並びを作る 色を
英大文字で 表した タイルの 並びで、 k 枚まで 塗り 替えて よいとき、 同じ 色が 続く 並びを 最も 長くします。 窓の 長さから 最も 多い 色の 数を 引いた 数が k 以下、を 保つ スライディングウィンドウの 練習です。 長さを
決めた 窓で 並べ替えた 言葉が 文の 中に 続けて 入っているか 調べる 言葉 p の
文字を 並べ替えた 物が、 文 s の 中に 途切れずに 入っているかを 調べます。 p と 同じ 長さの 窓を 1 文字ずつずらし、 窓の 中の 文字の 数を 足し 引きして 比べる、 長さを 決めた スライディングウィンドウの 練習です。 スライディングウィンドウで
必要な 文字を 全部 含む 最短の 部分を探す 文字列 s の
中で、 t の 文字を 数まで 全部 含む、 いちばん短い 続いた 部分を 探します。 足りない 文字の 数を 1 つの 数で 持ち、 右へ 伸ばして 全部 そろったら 左を 縮める、 スライディングウィンドウの 練習です。 両端
キューで 幅 k の 窓ごとの 最大値を 並べる 毎分の
数の 並びで、 直近 k 分ごとの 最大値を 全部 並べます。 値が 下がっていく 順に 添字を 両端 キューに 持ち、 窓の 外と 負けた 値を 捨てていく、 スライディングウィンドウと 単調 キューの 練習です。
- 窓の
左端に 最安値を 置いて 1 回の 売り 買いの 利益を 最大にする日ごとの値段の並びから、1 回だけ買って、それより後の日に 1 回だけ売るときの、いちばん大きい利益を返します。窓の左端をそれまでの最安の日に置き、右端を 1 日ずつ進める練習です。 - スライディングウィンドウで
続いた 1 の 最長を数える0 と 1 だけの並びから、1 がいちばん長く続いた所の長さを返します。並びを 1 回なめながら、いま続いている長さと最長を覚えておく練習です。 - スライディングウィンドウで
幅 k の 平均が 最大の所を探す整数の並びで、続いた k 個の平均がいちばん大きくなる所を探し、その k 個の合計を返します。窓を 1 つずらすたびに、入る数を足して出る数を引く練習です。 - スライディングウィンドウで
同じ 文字の 無い 最長の 部分を探す文字列の中で、同じ文字が 2 回出てこない続いた部分のうち、いちばん長い物の長さを返します。左右の端を持つ窓を伸ばし、重なりが出たら左の端を飛ばして縮める練習です。 - スライディングウィンドウで
k 枚まで 塗り 替えて 同じ色の 最長の 並びを作る色を英大文字で表したタイルの並びで、k 枚まで塗り替えてよいとき、同じ色が続く並びを最も長くします。窓の長さから最も多い色の数を引いた数が k 以下、を保つスライディングウィンドウの練習です。 - 長さを
決めた窓で 並べ替えた 言葉が 文の 中に 続けて 入っているか調べる言葉 p の文字を並べ替えた物が、文 s の中に途切れずに入っているかを調べます。p と同じ長さの窓を 1 文字ずつずらし、窓の中の文字の数を足し引きして比べる、長さを決めたスライディングウィンドウの練習です。 - スライディングウィンドウで
必要な 文字を 全部含む 最短の 部分を探す文字列 s の中で、t の文字を数まで全部含む、いちばん短い続いた部分を探します。足りない文字の数を 1 つの数で持ち、右へ伸ばして全部そろったら左を縮める、スライディングウィンドウの練習です。 - 両端キューで
幅 k の 窓ごとの 最大値を並べる毎分の数の並びで、直近 k 分ごとの最大値を全部並べます。値が下がっていく順に添字を両端キューに持ち、窓の外と負けた値を捨てていく、スライディングウィンドウと単調キューの練習です。
スタック
スタックで
括弧の 対応を 判定する 3 種類のかっこだけで
できた 文字列を 見て、 開きと 閉じの 対応が 正しいかを 返します。 開いたかっこを 積んで おき、 閉じる たびに 一番上と 照らす、 スタックの 練習です。 
スタックで
逆ポーランド 記法の 式を 計算する 演算子を
2 つの 数の 後ろに 書く 記法の 式を、 文字列の 並びで 受け取って 計算します。 数を 積んで おき、 演算子が 来たら 上の 2 つを 取り出して 計算する、 スタックの 練習です。 
スタックで
今日より 暖かい 日まで 何日 待つかを 並べる 毎日の
気温の 並びから、 日ごとに 「今日より 暖かい 日が 来るまで 何日 待つか」を 並べます。 まだ 答えの 決まらない 日を スタックに 積み、 暖かい 日が 来たら まとめて 答えを 決める、 単調 スタックの 練習です。 着く
時刻を 前から 比べて 一本道で ゴールに 着く 自転車の 群れを 数える 追い
越しの できない 一本道を 走る 自転車が、 ゴールに いくつの 群れで 着くかを 数えます。 ゴールに 近い順に 並べ、 前の 群れより 遅く 着く 自転車だけが 新しい 群れに なる、と 見抜く 練習です。 スタックで
棒グラフの 中に 入る いちばん 大きい 長方形を 求める 幅 1 の
棒を 並べた 棒グラフの 中に 描ける、 いちばん 大きい 長方形の 面積を 求めます。 高さが 上がっていく 棒を スタックに 積み、 低い棒が 来たら、 取り出した 棒の 高さで 左右に 広げた 長方形を 測る、 単調 スタックの 練習です。
- スタックで
括弧の 対応を判定する3 種類のかっこだけでできた文字列を見て、開きと閉じの対応が正しいかを返します。開いたかっこを積んでおき、閉じるたびに一番上と照らす、スタックの練習です。 - スタックで
逆ポーランド記法の 式を計算する演算子を 2 つの数の後ろに書く記法の式を、文字列の並びで受け取って計算します。数を積んでおき、演算子が来たら上の 2 つを取り出して計算する、スタックの練習です。 - スタックで
今日より 暖かい 日まで 何日待つかを並べる毎日の気温の並びから、日ごとに「今日より暖かい日が来るまで何日待つか」を並べます。まだ答えの決まらない日をスタックに積み、暖かい日が来たらまとめて答えを決める、単調スタックの練習です。 - 着く
時刻を 前から 比べて 一本道で ゴールに 着く 自転車の 群れを数える追い越しのできない一本道を走る自転車が、ゴールにいくつの群れで着くかを数えます。ゴールに近い順に並べ、前の群れより遅く着く自転車だけが新しい群れになる、と見抜く練習です。 - スタックで
棒グラフの 中に 入る いちばん 大きい長方形を求める幅 1 の棒を並べた棒グラフの中に描ける、いちばん大きい長方形の面積を求めます。高さが上がっていく棒をスタックに積み、低い棒が来たら、取り出した棒の高さで左右に広げた長方形を測る、単調スタックの練習です。
連結リスト
連結
リストの つなぎ先を 付け替えて 逆順にする 連結
リストの 先頭を 受け取り、 節の 並びを 逆に したリストの 先頭を 返します。 前、 いま、 次の 3 つを 指で 持ち、 つなぎ先を 1 つずつ後ろ 向きに 付け替える 練習です。 
ダミーの
節で 2 本の 並んだ 連結 リストを 1 本に まとめる 小さい
順に 並んだ 2 本の 連結 リストを、 小さい 順の まま 1 本に つなぎ直して 返します。 ダミーの 節を 先頭に 置き、 2 本の 先頭を 比べて 小さい 方を つなぐ 練習です。 
速い指と
遅い指で 連結 リストの 輪を 見つける 連結
リストを たどると 同じ節へ 戻ってくる 輪が あるかを 返します。 1 つずつ 進む指と 2 つずつ 進む指を 走らせ、 追いつくか どうかで 見分ける 練習です。 半分に
分けて 後ろを 逆にし、 連結 リストを 前と 後ろから 互い 違いに 並べ直す 連結
リストを、 先頭、 最後、 2 番目、 後ろから 2 番目、と前と 後ろから 交互に 取る 順に つなぎ直します。 まん中を 探す、 後ろ半分を 逆に する、 2 本を 交互に つなぐ、の 3 つを 組み合わせる 練習です。 間を
あけた 2 本の 指で 連結 リストの 後ろから n 番目の 節を外す 連結
リストの 後ろから 数えて n 番目の 節を 外し、 先頭を 返します。 n 歩先に 出した 指と 一緒に 進め、 1 回なめるだけで 外す節の 1 つ前を 見つける 練習です。 繰り
上がりを 持ちながら、 1 の 位から 並んだ 2 本の 連結 リストの 数を足す 数の
桁を 1 の 位から 順に 1 つずつ 持つ 2 本の 連結 リストを 受け取り、 2 つの 数の 和を 同じ形の 連結 リストで 返します。 繰り 上がりを 持ちながら、 長さの 違う 2 本を 同時に なめる 練習です。 速い指と
遅い指で 並びの 中の 重なった 数を探す 1 から
n までの 数が n + 1 個入った 並びから、 2 回以上 出てくる 数を、 並びを 書き換えず O(1) の 記憶で 返します。 値を 次の 行き先と 見て 連結 リストの 輪を 探す練習です。 元の
節と 写しの 対応表で random つきの 連結 リストを 丸ごと写す 次の
節の ほかに、 同じリストの どこかの 節を 指す random を 持つ連結 リストを、 全部 新しい 節で 写して 返します。 元の 節から 写しの 節を 引ける 対応表を 先に 作り、 つなぎ先を 2 回目で そろえる 練習です。 つなぎ先の
付け替えで 連結 リストを k 個ずつ 逆順にする 連結
リストを 先頭から k 個ずつの 組に 分け、 それぞれの 組の 中を 逆順に つなぎ直します。 k 個に 足りない 最後の 残りは そのままです。 組の 前後の つなぎ目を 見失わずに 付け替える 練習です。 2 本ずつまとめて
k 本の 並んだ 連結 リストを 1 本にする 小さい
順に 並んだ k 本の 連結 リストを、 小さい 順の まま 1 本に つなぎ直して 返します。 2 本を まとめる 手順を、 組み合わせを 半分ずつに 減らしながら 繰り返し、 O(N log k) に 収める 練習です。
- 連結リストの
つなぎ先を 付け替えて 逆順にする連結リストの先頭を受け取り、節の並びを逆にしたリストの先頭を返します。前、いま、次の 3 つを指で持ち、つなぎ先を 1 つずつ後ろ向きに付け替える練習です。 - ダミーの
節で 2 本の 並んだ 連結リストを 1 本にまとめる小さい順に並んだ 2 本の連結リストを、小さい順のまま 1 本につなぎ直して返します。ダミーの節を先頭に置き、2 本の先頭を比べて小さい方をつなぐ練習です。 - 速い指と
遅い指で 連結リストの 輪を見つける連結リストをたどると同じ節へ戻ってくる輪があるかを返します。1 つずつ進む指と 2 つずつ進む指を走らせ、追いつくかどうかで見分ける練習です。 - 半分に
分けて 後ろを 逆にし、 連結リストを 前と 後ろから 互い 違いに並べ直す連結リストを、先頭、最後、2 番目、後ろから 2 番目、と前と後ろから交互に取る順につなぎ直します。まん中を探す、後ろ半分を逆にする、2 本を交互につなぐ、の 3 つを組み合わせる練習です。 - 間を
あけた 2 本の 指で 連結リストの 後ろから n 番目の節を外す連結リストの後ろから数えて n 番目の節を外し、先頭を返します。n 歩先に出した指と一緒に進め、1 回なめるだけで外す節の 1 つ前を見つける練習です。 - 繰り
上がりを 持ちながら、 1 の 位から 並んだ 2 本の 連結リストの数を足す数の桁を 1 の位から順に 1 つずつ持つ 2 本の連結リストを受け取り、2 つの数の和を同じ形の連結リストで返します。繰り上がりを持ちながら、長さの違う 2 本を同時になめる練習です。 - 速い指と
遅い指で 並びの 中の 重なった数を探す1 から n までの数が n + 1 個入った並びから、2 回以上出てくる数を、並びを書き換えず O(1) の記憶で返します。値を次の行き先と見て連結リストの輪を探す練習です。 - 元の
節と 写しの 対応表で random つきの 連結リストを 丸ごと写す次の節のほかに、同じリストのどこかの節を指す random を持つ連結リストを、全部新しい節で写して返します。元の節から写しの節を引ける対応表を先に作り、つなぎ先を 2 回目でそろえる練習です。 - つなぎ先の
付け替えで 連結リストを k 個ずつ逆順にする連結リストを先頭から k 個ずつの組に分け、それぞれの組の中を逆順につなぎ直します。k 個に足りない最後の残りはそのままです。組の前後のつなぎ目を見失わずに付け替える練習です。 - 2 本ずつまとめて
k 本の 並んだ 連結リストを 1 本にする小さい順に並んだ k 本の連結リストを、小さい順のまま 1 本につなぎ直して返します。2 本をまとめる手順を、組み合わせを半分ずつに減らしながら繰り返し、O(N log k) に収める練習です。
再帰
二分探索
二分探索で
ソート 済み配列から 値を探す 小さい
順に 並んだ 整数から 目当ての 数の 位置を 探し、 無ければ -1 を 返す。 探す範囲を 毎回 半分に 狭める 二分探索の 練習です。 
二分探索で
挿入位置を 求める 小さい
順の 並びで、 目当ての 数が あれば その 位置を、 無ければ 順を 崩さずに 入れる 位置を 返す。 二分探索が 止まった ときの 左の 端が 何を 指すかを 考える 練習です。 
答えの
値で 二分探索して 締め切りに 間に 合う 最小の 速さを探す 何冊かの
本を 決まった 時間で 読み切るのに 要る、 1 時間 あたりの 最小の ページ 数を 返します。 並びではなく 答えの 値の 範囲を 半分ずつ 絞る、 二分探索の 使い方の 練習です。 二分探索で
同じ値が 続く 範囲の 両端を探す 小さい
順に 並んだ 整数の 並びから、 目標の 値が 続いている 範囲の 最初と 最後の 位置を 返します。 「この 値以上が 始まる 位置」を 探す 二分探索を 2 回使い、 端の 場合まで 詰める 練習です。 二分探索で
上って 下る 並びの 頂上を探す 上ってから
下る 整数の 並びから、 いちばん高い 所 (頂上) の 位置を 返します。 並び全体が 小さい 順でなくても、 隣と 比べた 向きで 範囲を 半分に 絞れる ことに 気づく 練習です。 二分探索で
行ごとに 並んだ 表から 値を探す 各行が
小さい 順に 並び、 行の 頭が 前の 行の 最後より 大きい 表から、 目標の 値が あるかを 返します。 表を 1 本の 長い 並びと 見なして 二分探索する 練習です。 二分探索で
回された 並びの いちばん 小さい 値を探す 小さい
順の 並びを 途中で 切って 前後を 入れ替えた 並びから、 いちばん 小さい 値を O(log n) で 返します。 まん中と 右端を 比べて、 切れ目の ある 側へ 絞る 二分探索の 練習です。 二分探索で
回された 並びから 値を探す 小さい
順の 並びを 途中で 切って 前後を 入れ替えた 並びから、 目当ての 値の 位置を O(log n) で 探します。 半分に 割る たびに、 どちらの 半分が 順に 並んでいるかを 見分ける 練習です。 二分探索で
2 つの ソート 済み配列の 中央値を 求める 小さい
順の 2 つの 並びを 1 つに まとめずに、 まとめた ときの 中央値を O(log(min(m, n))) で 求めます。 短い方の 並びの 「切る 位置」を 二分探索で 探す練習です。
- 二分探索で
ソート済み配列から値を探す小さい順に並んだ整数から目当ての数の位置を探し、無ければ -1 を返す。探す範囲を毎回半分に狭める二分探索の練習です。 - 二分探索で
挿入位置を求める小さい順の並びで、目当ての数があればその位置を、無ければ順を崩さずに入れる位置を返す。二分探索が止まったときの左の端が何を指すかを考える練習です。 - 答えの
値で 二分 探索して 締め切りに 間に 合う 最小の 速さを探す何冊かの本を決まった時間で読み切るのに要る、1 時間あたりの最小のページ数を返します。並びではなく答えの値の範囲を半分ずつ絞る、二分探索の使い方の練習です。 - 二分探索で
同じ 値が 続く 範囲の 両端を探す小さい順に並んだ整数の並びから、目標の値が続いている範囲の最初と最後の位置を返します。「この値以上が始まる位置」を探す二分探索を 2 回使い、端の場合まで詰める練習です。 - 二分探索で
上って 下る 並びの 頂上を探す上ってから下る整数の並びから、いちばん高い所 (頂上) の位置を返します。並び全体が小さい順でなくても、隣と比べた向きで範囲を半分に絞れることに気づく練習です。 - 二分探索で
行ごとに 並んだ 表から値を探す各行が小さい順に並び、行の頭が前の行の最後より大きい表から、目標の値があるかを返します。表を 1 本の長い並びと見なして二分探索する練習です。 - 二分探索で
回された 並びの いちばん 小さい値を探す小さい順の並びを途中で切って前後を入れ替えた並びから、いちばん小さい値を O(log n) で返します。まん中と右端を比べて、切れ目のある側へ絞る二分探索の練習です。 - 二分探索で
回された 並びから値を探す小さい順の並びを途中で切って前後を入れ替えた並びから、目当ての値の位置を O(log n) で探します。半分に割るたびに、どちらの半分が順に並んでいるかを見分ける練習です。 - 二分探索で
2 つの ソート済み配列の 中央値を求める小さい順の 2 つの並びを 1 つにまとめずに、まとめたときの中央値を O(log(min(m, n))) で求めます。短い方の並びの「切る位置」を二分探索で探す練習です。
木 (DFS と BFS)
深さ優先探索 (DFS) で
二分木の 深さを 求める 二分木の
根から 一番 遠い 葉までの 段の 数を 返す。 左右の 子の 深さを 先に 求めて 1 を 足す、 深さ優先の 再帰の 練習です。 
再帰で
2 本の 二分木が 同じか 確かめる 2 本の
二分木を 受け取り、 形も 値も まったく 同じかを 返します。 根を 比べ、 左どうし、 右どうしを 同じ 関数に 任せる、 木の 再帰の いちばん基本の 練習です。 
再帰で
二分木を 左右反転する 二分木の
すべての 節で 左の 子と 右の 子を 入れ替え、 鏡に 映した 木を 返します。 下の 木を 先に 反転してから 付け替える、 木の 再帰の 基本の 練習です。 深さ優先探索で
二分木の 根から 葉までの 合計を 調べる 二分木の
根から 葉までの 道で、 値の 合計が 目標の 数に なる物が あるかを 調べる。 残りの 数を 子へ 渡しながら 潜る、 深さ優先の 再帰の 練習です。 再帰で
二分木の いちばん長い道の 長さを 求める 二分木の
中で、 いちばん離れた 2 つの 節を 結ぶ 道の 長さを、 辺の 数で 返します。 下から 高さを 返しながら、 ついでに 最長の 道を 数える、 木の 再帰の 練習です。 再帰で
二分木の 高さが 釣り合っているか 確かめる 二分木の
どの 節でも、 左と 右の 高さの 差が 1 以下かを 返します。 下から 高さを 返し、 崩れを 見つけたら 印を 返して 止める、 木の 再帰の 練習です。 再帰で
二分木の 中に 別の 木と 同じ 部分木が あるか 確かめる 大きい
二分木の どこかの 節から 下が、 小さい 二分木と そっくり 同じかを 返します。 どの 節を 根に するかを 探す再帰と、 2 本の 木が 同じかを 比べる 再帰を 組み合わせる 練習です。 幅優先探索 (BFS) と
キューで 二分木を 段ごとに読む 二分木の
値を、 上の 段から 順に、 段ごとの 並びに まとめて 返す。 待ち行列で 近い 節から 順に 見ていく、 幅優先の 読み方の 練習です。 再帰で
二分探索木の 決まりを 確かめる 二分木が
二分探索木の 決まりを 守っているかを 返します。 親と 子だけを 比べる 落とし穴を 避け、 各節に 入って よい値の 範囲を 上から 渡していく 練習です。 再帰で
二分木の 2 つの 節に いちばん近い 共通の 祖先を探す 二分木の
中の 2 つの 値に ついて、 両方を 下に 持つ節の うち、 いちばん深い節の 値を 返します。 左右の 部分木から 見つけた 物を 上へ 返し、 両側から 返った 所で 答えを 決める 再帰の 練習です。 幅優先探索 (BFS) で
二分木を 右から 見た ときに 見える 節を 並べる 二分木を
右側から 眺めた ときに 見える 節の 値を、 上の 段から 順に 返します。 段ごとに 読む幅優先探索で、 各段の いちばん右の 節を 拾う 練習です。 深さ優先探索で
根からの 道で いちばん 大きい値を 持ち回り、 二分木の よい節を 数える 根から
その 節までの 道に、 その 節より 大きい 値が 1 つも 無い節を 「よい節」と 呼び、 その 数を 返します。 上から 下へ、 ここまでの 最大値を 引数で 渡していく 深さ優先探索の 練習です。 辞書と
再帰で 前順と 中順の 並びから 二分木を 組み直す 二分木を
前順と 中順で たどった 2 つの 並びから、 元の 木を 組み直して 返します。 前順で 根を 決め、 中順で 左右を 分ける 再帰に、 位置を 引く 辞書を 組み合わせて O(n) に する 練習です。 再帰で
二分木の 道の 値の 合計が いちばん 大きくなる 所を探す 二分木の
中で、 節を つないだ道の 値の 合計の うち、 いちばん 大きい 値を 返します。 負の 値の 枝を 切り 捨てながら、 下へ 伸ばせる 片道の 和を 返し、 ついでに 曲がる 道を 比べる 再帰の 練習です。 前順の
走査で 二分木を 文字列に して、 文字列から 同じ木に 組み直す 二分木を
1 本の 文字列に 直す serialize と、 その 文字列から 同じ木を 組み直す deserialize を 書きます。 空の 子にも 印を 付けて 前順で 並べ、 読む ときも 同じ順で 消費する 再帰の 練習です。
- 深さ優先探索 (DFS) で
二分木の 深さを求める二分木の根から一番遠い葉までの段の数を返す。左右の子の深さを先に求めて 1 を足す、深さ優先の再帰の練習です。 - 再帰で
2 本の 二分木が 同じか確かめる2 本の二分木を受け取り、形も値もまったく同じかを返します。根を比べ、左どうし、右どうしを同じ関数に任せる、木の再帰のいちばん基本の練習です。 - 再帰で
二分木を 左右反転する二分木のすべての節で左の子と右の子を入れ替え、鏡に映した木を返します。下の木を先に反転してから付け替える、木の再帰の基本の練習です。 - 深さ優先探索で
二分木の 根から 葉までの 合計を調べる二分木の根から葉までの道で、値の合計が目標の数になる物があるかを調べる。残りの数を子へ渡しながら潜る、深さ優先の再帰の練習です。 - 再帰で
二分木の いちばん長い 道の 長さを求める二分木の中で、いちばん離れた 2 つの節を結ぶ道の長さを、辺の数で返します。下から高さを返しながら、ついでに最長の道を数える、木の再帰の練習です。 - 再帰で
二分木の 高さが 釣り合っているか確かめる二分木のどの節でも、左と右の高さの差が 1 以下かを返します。下から高さを返し、崩れを見つけたら印を返して止める、木の再帰の練習です。 - 再帰で
二分木の 中に 別の 木と 同じ 部分木が あるか確かめる大きい二分木のどこかの節から下が、小さい二分木とそっくり同じかを返します。どの節を根にするかを探す再帰と、2 本の木が同じかを比べる再帰を組み合わせる練習です。 - 幅優先探索 (BFS) と
キューで 二分木を 段ごとに読む二分木の値を、上の段から順に、段ごとの並びにまとめて返す。待ち行列で近い節から順に見ていく、幅優先の読み方の練習です。 - 再帰で
二分探索木の 決まりを確かめる二分木が二分探索木の決まりを守っているかを返します。親と子だけを比べる落とし穴を避け、各節に入ってよい値の範囲を上から渡していく練習です。 - 再帰で
二分木の 2 つの 節に いちばん近い 共通の 祖先を探す二分木の中の 2 つの値について、両方を下に持つ節のうち、いちばん深い節の値を返します。左右の部分木から見つけた物を上へ返し、両側から返った所で答えを決める再帰の練習です。 - 幅優先探索 (BFS) で
二分木を 右から 見た ときに 見える 節を並べる二分木を右側から眺めたときに見える節の値を、上の段から順に返します。段ごとに読む幅優先探索で、各段のいちばん右の節を拾う練習です。 - 深さ優先探索で
根からの 道で いちばん 大きい値を 持ち回り、 二分木の よい 節を数える根からその節までの道に、その節より大きい値が 1 つも無い節を「よい節」と呼び、その数を返します。上から下へ、ここまでの最大値を引数で渡していく深さ優先探索の練習です。 - 辞書と
再帰で 前順と 中順の 並びから 二分木を組み直す二分木を前順と中順でたどった 2 つの並びから、元の木を組み直して返します。前順で根を決め、中順で左右を分ける再帰に、位置を引く辞書を組み合わせて O(n) にする練習です。 - 再帰で
二分木の 道の 値の 合計が いちばん 大きくなる所を探す二分木の中で、節をつないだ道の値の合計のうち、いちばん大きい値を返します。負の値の枝を切り捨てながら、下へ伸ばせる片道の和を返し、ついでに曲がる道を比べる再帰の練習です。 - 前順の
走査で 二分木を 文字列に して、 文字列から 同じ木に組み直す二分木を 1 本の文字列に直す serialize と、その文字列から同じ木を組み直す deserialize を書きます。空の子にも印を付けて前順で並べ、読むときも同じ順で消費する再帰の練習です。
二分探索木
再帰で
並びから 高さの そろった 二分 探索木を作る 小さい
順に 並んだ 数から、 左右の 高さが そろった 二分探索木を 作って 返します。 まん中を 根に して 左右を 同じ形で 作る、 分けて 解く 再帰の 基本の 練習です。 
スタックの
中順の 走査で 二分探索木の k 番目に 小さい 値を探す 二分探索木から、
小さい 方から 数えて k 番目の 値を 返します。 左、 自分、 右の 順に 読むと 小さい 順に なる ことを 使い、 その 読み方を 再帰ではなく スタックの 繰り返しで 書く 練習です。 
二分探索木の
大小で 2 つの 節の 共通の 祖先を探す 二分探索木の
2 つの 値に ついて、 両方を 子孫に 持ついちばん深い 節 (共通の 祖先) の 値を 返します。 2 つの 値と 節の 大小だけで、 根から 1 本道で 下りられる ことに 気づく 練習です。 繰り返しで
二分探索木に 新しい 値を 葉と して足す 二分探索木に
新しい 値を 足し、 足した あとの 木を 返します。 大小で 左右へ 進んで 空いた 所を 探し、 そこへ 葉と して つなぐ 練習です。 再帰で
二分探索木から 値を 消して 木を つなぎ直す 二分探索木から
指定の 値の 節を 消し、 決まりを 崩さないように つなぎ直した 木を 返します。 子の 数で 場合を 分け、 子が 2 つの ときは 右の 部分木の いちばん 小さい 節で 置き換える 練習です。
- 再帰で
並びから 高さの そろった 二分探索木を作る小さい順に並んだ数から、左右の高さがそろった二分探索木を作って返します。まん中を根にして左右を同じ形で作る、分けて解く再帰の基本の練習です。 - スタックの
中順の 走査で 二分探索木の k 番目に 小さい値を探す二分探索木から、小さい方から数えて k 番目の値を返します。左、自分、右の順に読むと小さい順になることを使い、その読み方を再帰ではなくスタックの繰り返しで書く練習です。 - 二分探索木の
大小で 2 つの 節の 共通の 祖先を探す二分探索木の 2 つの値について、両方を子孫に持ついちばん深い節 (共通の祖先) の値を返します。2 つの値と節の大小だけで、根から 1 本道で下りられることに気づく練習です。 - 繰り返しで
二分探索木に 新しい 値を 葉として足す二分探索木に新しい値を足し、足したあとの木を返します。大小で左右へ進んで空いた所を探し、そこへ葉としてつなぐ練習です。 - 再帰で
二分探索木から 値を 消して 木を つなぎ直す二分探索木から指定の値の節を消し、決まりを崩さないようにつなぎ直した木を返します。子の数で場合を分け、子が 2 つのときは右の部分木のいちばん小さい節で置き換える練習です。
ヒープ
ヒープで
いちばん重い 2 つを 打ち合わせて 最後に 残る 重さを 求める 金属の
玉を、 いちばん重い 2 つずつ 打ち合わせて 減らしていき、 最後に 残る 重さを 返します。 毎回 「いちばん 大きい値を 2 つ取り出す」を、 大きい順の ヒープで 速くこなす練習です。 
ヒープで
k 番目に 大きい値を 求める 整数の
並びから、 大きい 方から 数えて k 番目の 値を 返します。 全部を 並べ替えず、 大きい方の k 個だけを 小さい 順の ヒープに 持ち続ける 練習です。 
ハッシュと
ヒープで 出てくる 回数の 多い 値を k 個選ぶ 整数の
並びから、 出てくる 回数の 多い 値を k 個、 決めた 順で 返します。 辞書で 回数を 数え、 「いちばん弱い 候補」が 根に 来る ヒープに k 個だけ 持つ練習です。 ヒープで
原点に いちばん近い k 個の 点を選ぶ 平面の
点の 並びから、 原点 (0, 0) に 近い方の k 個を 選んで 返します。 全部を 並べ替えず、 近い k 個だけを 「いちばん遠い物が 根に 来る ヒープ」に 持ち続ける 練習です。 ヒープで
同じ 作業の 間を 空けて 全部を 終える 最短の 時間を 求める 同じ
種類の 作業の あいだに 決まった 数の 休みを 挟む 決まりで、 全部の 作業を 終えるのに 要る いちばん短い 時間を 数えます。 残りの 多い 作業から 先に 入れる 欲張りを、 大きい順の ヒープで 回す練習です。
- ヒープで
いちばん重い 2 つを 打ち合わせて 最後に 残る 重さを求める金属の玉を、いちばん重い 2 つずつ打ち合わせて減らしていき、最後に残る重さを返します。毎回「いちばん大きい値を 2 つ取り出す」を、大きい順のヒープで速くこなす練習です。 - ヒープで
k 番目に 大きい値を求める整数の並びから、大きい方から数えて k 番目の値を返します。全部を並べ替えず、大きい方の k 個だけを小さい順のヒープに持ち続ける練習です。 - ハッシュと
ヒープで 出てくる 回数の 多い 値を k 個選ぶ整数の並びから、出てくる回数の多い値を k 個、決めた順で返します。辞書で回数を数え、「いちばん弱い候補」が根に来るヒープに k 個だけ持つ練習です。 - ヒープで
原点に いちばん近い k 個の点を選ぶ平面の点の並びから、原点 (0, 0) に近い方の k 個を選んで返します。全部を並べ替えず、近い k 個だけを「いちばん遠い物が根に来るヒープ」に持ち続ける練習です。 - ヒープで
同じ 作業の 間を 空けて 全部を 終える 最短の 時間を求める同じ種類の作業のあいだに決まった数の休みを挟む決まりで、全部の作業を終えるのに要るいちばん短い時間を数えます。残りの多い作業から先に入れる欲張りを、大きい順のヒープで回す練習です。
トライ木
トライ
木 (Trie) で 言葉の 頭を 調べる 仕組みを作る 言葉を
足す、 言葉が まる ごと あるか 調べる、 ある 頭で 始まる 言葉が あるか 調べる、の 3 つの 操作を 持つ 仕組みを 作る。 1 文字ずつ 枝分かれする 木に 言葉を しまう 練習です。 
トライ
木で 伏せ字の 入った 言葉を 探す 仕組みを作る 言葉を
足す操作と、 どの 1 文字にも 当たる 伏せ字 . を 含む 言葉を 探す操作を 持つ 仕組みを 作る。 トライ 木の 上で、 当ては まる 節の 集まりを 1 文字ずつ 進めていきます。 
トライ
木と 深さ優先探索で 文字の 盤面から 言葉を 全部探す 文字の
盤面の 上下左右を たどって 作れる 言葉を、 候補の 一覧から 全部 探して、 辞書の 順に 返します。 候補を トライ 木に まとめ、 盤面を 1 回た どる あいだに 全部の 候補を 同時に 調べる 練習です。
- トライ木 (Trie) で
言葉の 頭を 調べる 仕組みを作る言葉を足す、言葉がまるごとあるか調べる、ある頭で始まる言葉があるか調べる、の 3 つの操作を持つ仕組みを作る。1 文字ずつ枝分かれする木に言葉をしまう練習です。 - トライ木で
伏せ字の 入った 言葉を 探す仕組みを作る言葉を足す操作と、どの 1 文字にも当たる伏せ字 . を含む言葉を探す操作を持つ仕組みを作る。トライ木の上で、当てはまる節の集まりを 1 文字ずつ進めていきます。 - トライ木と
深さ優先探索で 文字の 盤面から 言葉を全部探す文字の盤面の上下左右をたどって作れる言葉を、候補の一覧から全部探して、辞書の順に返します。候補をトライ木にまとめ、盤面を 1 回たどるあいだに全部の候補を同時に調べる練習です。
グラフ
幅優先探索 (BFS) で
グリッドの 島を 数える 陸と
海の 地図から、 上下左右で つながった 陸のかたまりが いくつあるかを 数える。 まだ 見ていない 陸を 見つける たびに、 そこから 広がる 陸を 待ち行列で 全部 塗りつぶします。 
幅優先探索 (BFS) で
東と 西の 両方の 海へ 流れる 場所を探す 島の
高さの 地図から、 雨水が 東の 海にも 西の 海にも 流れていける 場所を 全部返す。 海の 側から 逆に、 高い ほうへ 登れる 所を 幅優先で 広げ、 両方から 届いた 場所を 集めます。 
深さ優先探索 (DFS) で
グリッドの いちばん 大きい島の 広さを 求める 陸と
海の マスが 並んだ 地図から、 上下左右に つながった 陸の まとまり (島) の うち、 いちばん 広い島の マスの 数を 返します。 島を 見つけたら 塗りつぶしながら 数える 練習です。 盤の
端から たどって 囲まれた 空き地だけを 埋める 土と
水の マスが 並んだ盤で、 盤の 端に つながっていない 水の まとまりを 土で 埋めた 盤を 返します。 囲まれた 所を 探すのではなく、 端から 届く 水に 印を 付けて、 残りを 埋める 練習です。 幅優先探索 (BFS) と
辞書で つながりの グラフを 写し取る 1 つの
節から 届く グラフを、 節を 1 回ずつだけ写して、 つながりごと 写し取ります。 元の 節と 写した 節の 対応を 辞書に 持ち、 初めて 見た 節だけを 写して 列に 並べる 練習です。 幅優先探索 (BFS) の
色塗りで、 つながった 2 人を 別の 組に 分けられるか 調べる 人と
人の つながりを、 どの つながりも 2 つの 組を またぐように 2 組へ 分けられるか (二部 グラフか ) を 調べます。 隣を 反対の 色で 塗りながらた どり、 同じ 色どうしが つながっていたら 分けられない、と 判断する 練習です。 プリム法で
全部の 倉庫を 道で つなぐ いちばん安い 費用を 求める 平面に
散らばった 倉庫を、 碁盤の 目の 道で つないで、 どの 2 つも 行き来できるように する いちばん安い 費用を 求めます。 つないだまとまりから 最も 近い 倉庫を 1 つずつ 足していく、 最小全域木の プリム法の 練習です。 一筆
書き (ヒアホルツァー法) で 全部の 切符を 使う 旅程を 組み立てる 片道の
切符の 束から、 全部の 切符を ちょうど 1 回ずつ 使う 旅程を、 行き先の 名前が 辞書の 順で 早い方を 優先して 組み立てます。 行き止まりに 着いた 空港から 後ろに 並べていく 一筆 書きの 練習です。
- 幅優先探索 (BFS) で
グリッドの 島を数える陸と海の地図から、上下左右でつながった陸のかたまりがいくつあるかを数える。まだ見ていない陸を見つけるたびに、そこから広がる陸を待ち行列で全部塗りつぶします。 - 幅優先探索 (BFS) で
東と 西の 両方の 海へ 流れる 場所を探す島の高さの地図から、雨水が東の海にも西の海にも流れていける場所を全部返す。海の側から逆に、高いほうへ登れる所を幅優先で広げ、両方から届いた場所を集めます。 - 深さ優先探索 (DFS) で
グリッドの いちばん 大きい島の 広さを求める陸と海のマスが並んだ地図から、上下左右につながった陸のまとまり (島) のうち、いちばん広い島のマスの数を返します。島を見つけたら塗りつぶしながら数える練習です。 - 盤の
端から たどって 囲まれた 空き地だけを埋める土と水のマスが並んだ盤で、盤の端につながっていない水のまとまりを土で埋めた盤を返します。囲まれた所を探すのではなく、端から届く水に印を付けて、残りを埋める練習です。 - 幅優先探索 (BFS) と
辞書で つながりの グラフを写し取る1 つの節から届くグラフを、節を 1 回ずつだけ写して、つながりごと写し取ります。元の節と写した節の対応を辞書に持ち、初めて見た節だけを写して列に並べる練習です。 - 幅優先探索 (BFS) の
色塗りで、 つながった 2 人を 別の 組に 分けられるか調べる人と人のつながりを、どのつながりも 2 つの組をまたぐように 2 組へ分けられるか (二部グラフか) を調べます。隣を反対の色で塗りながらたどり、同じ色どうしがつながっていたら分けられない、と判断する練習です。 - プリム法で
全部の 倉庫を 道で つなぐいちばん安い 費用を求める平面に散らばった倉庫を、碁盤の目の道でつないで、どの 2 つも行き来できるようにするいちばん安い費用を求めます。つないだまとまりから最も近い倉庫を 1 つずつ足していく、最小全域木のプリム法の練習です。 - 一筆書き (ヒアホルツァー法) で
全部の 切符を 使う 旅程を 組み立てる片道の切符の束から、全部の切符をちょうど 1 回ずつ使う旅程を、行き先の名前が辞書の順で早い方を優先して組み立てます。行き止まりに着いた空港から後ろに並べていく一筆書きの練習です。
最短経路 (BFS)
幅優先探索 (BFS) で
グリッドの 最短の 道を 数える 通れる
マスと ふさがった マスの 地図で、 左上から 右下まで 8 方向に 進むときの 最短の 道の マスの 数を 返す。 近い マスから 順に 広げる 幅優先で、 最初に 着いた 時の 歩数が 答えに なります。 
幅優先探索 (BFS) で
知らせが 全員に 届くまでの 分を 数える 座席の
表で、 知らせを 持つ 人から 上下左右の 人へ 1 分ずつ知らせが 広がる とき、 全員に 届くまでの 分を 数えます。 始めに 知らせを 持つ人を 全員、 同時に 列へ 入れて 段ごとに 広げる 練習です。 
幅優先探索 (BFS) で
全部の 部屋から いちばん 近い 出口までの 歩数を 求める 部屋と
出口が 並んだ 間取りで、 どの 部屋に ついても、 いちばん 近い 出口までの 歩数を 書き込んだ 表を 返します。 全部の 出口から 同時に 広げる 幅優先探索で、 1 回で 全部の 歩数を 決める 練習です。 ダイクストラ法で
合図が 全部の 中継所に 届くまでの 時間を 求める 一方
通行の 回線で つながった 中継所に、 1 か 所から 合図を 流した とき、 全部の 中継所に 届くまでの 時間を 求めます。 重みの ある 最短経路を、 ヒープで 近い 所から 確定していく ダイクストラ法で 解く 練習です。 ベルマン・
フォード法で 乗り継ぎ k 回までの いちばん安い 運賃を 求める 都市を
結ぶ 便の 運賃の 並びから、 乗り 継ぎを k 回までに 抑えて 出発地から 目的地へ 行く、 いちばん安い 運賃を 求めます。 使う 便の 数を 1 本ず つ増やしながら 運賃を 緩めていく、 回数に 上限の ある 最短経路の 練習です。 幅優先探索 (BFS) で
言葉の 梯子の いちばん短い 長さを 求める 1 文字ずつ
置き換えて、 始めの 言葉から 終わりの 言葉まで、 言葉の 一覧に ある 言葉だけを 通って 渡る。 1 文字を 伏せた形で 言葉を 箱に 分けて おき、 幅優先で 近い 言葉から 広げます。 ヒープで
水位の 上がる池を 対角まで 渡れる いちばん早い 時刻を 求める 高さの
違う 石が 並んだ池で、 水位が 1 ずつ 上がる とき、 左上から 右下まで 水の 上を 渡れる いちばん早い 時刻を 求めます。 道の 「いちばん高い石」を 小さく する 最短経路を、 ヒープで 低い 所から 広げて 解く 練習です。
- 幅優先探索 (BFS) で
グリッドの 最短の 道を数える通れるマスとふさがったマスの地図で、左上から右下まで 8 方向に進むときの最短の道のマスの数を返す。近いマスから順に広げる幅優先で、最初に着いた時の歩数が答えになります。 - 幅優先探索 (BFS) で
知らせが 全員に 届くまでの 分を数える座席の表で、知らせを持つ人から上下左右の人へ 1 分ずつ知らせが広がるとき、全員に届くまでの分を数えます。始めに知らせを持つ人を全員、同時に列へ入れて段ごとに広げる練習です。 - 幅優先探索 (BFS) で
全部の 部屋から いちばん近い 出口までの 歩数を求める部屋と出口が並んだ間取りで、どの部屋についても、いちばん近い出口までの歩数を書き込んだ表を返します。全部の出口から同時に広げる幅優先探索で、1 回で全部の歩数を決める練習です。 - ダイクストラ法で
合図が 全部の 中継所に 届くまでの 時間を求める一方通行の回線でつながった中継所に、1 か所から合図を流したとき、全部の中継所に届くまでの時間を求めます。重みのある最短経路を、ヒープで近い所から確定していくダイクストラ法で解く練習です。 - ベルマン・フォード法で
乗り継ぎ k 回までの いちばん安い 運賃を求める都市を結ぶ便の運賃の並びから、乗り継ぎを k 回までに抑えて出発地から目的地へ行く、いちばん安い運賃を求めます。使う便の数を 1 本ずつ増やしながら運賃を緩めていく、回数に上限のある最短経路の練習です。 - 幅優先探索 (BFS) で
言葉の 梯子の いちばん短い 長さを求める1 文字ずつ置き換えて、始めの言葉から終わりの言葉まで、言葉の一覧にある言葉だけを通って渡る。1 文字を伏せた形で言葉を箱に分けておき、幅優先で近い言葉から広げます。 - ヒープで
水位の 上がる 池を 対角まで 渡れる いちばん早い 時刻を求める高さの違う石が並んだ池で、水位が 1 ずつ上がるとき、左上から右下まで水の上を渡れるいちばん早い時刻を求めます。道の「いちばん高い石」を小さくする最短経路を、ヒープで低い所から広げて解く練習です。
素集合 (Union-Find)
トポロジカルソート
トポロジカルソートで
全部の 講座を 受けられるか 調べる 「この
講座の 前に あの 講座を 終える」と いう 決まりの 並びから、 全部の 講座を 受け終えられるかを 答える。 前提の 残り数が 0 の 講座から 順に 待ち行列で 取り出す、 トポロジカルソートの 練習です。 
トポロジカルソートと
ヒープで 講座を 受ける 順を 決める 「この
講座の 前に あの 講座を 終える」と いう 決まりの 並びから、 全部の 講座を 受ける 順を 1 つ返す。 いま受けられる 講座の うち、 番号の いちばん 小さい 物を ヒープで 取り出していきます。 
トポロジカルソートで
手持ちの 材料から 作れる 料理を 全部 見つける 料理ごとに
要る 材料と、 手持ちの 材料から、 作れる 料理を 全部 見つけます。 ほかの 料理を 材料に 使う 料理も あるので、 「要る 物が 全部 そろった 料理から 作る」を、 残りの 数を 数えながら列で 回すトポロジカルソートの 練習です。
- トポロジカルソートで
全部の 講座を 受けられるか調べる「この講座の前にあの講座を終える」という決まりの並びから、全部の講座を受け終えられるかを答える。前提の残り数が 0 の講座から順に待ち行列で取り出す、トポロジカルソートの練習です。 - トポロジカルソートと
ヒープで 講座を 受ける 順を決める「この講座の前にあの講座を終える」という決まりの並びから、全部の講座を受ける順を 1 つ返す。いま受けられる講座のうち、番号のいちばん小さい物をヒープで取り出していきます。 - トポロジカルソートで
手持ちの 材料から 作れる 料理を 全部見つける料理ごとに要る材料と、手持ちの材料から、作れる料理を全部見つけます。ほかの料理を材料に使う料理もあるので、「要る物が全部そろった料理から作る」を、残りの数を数えながら列で回すトポロジカルソートの練習です。
区間
並べ替えで
重なる 区間を 1 つに まとめる 会議室の
予約の 時間帯の 並びから、 重なったり接したりする 時間帯を まとめて、 使われている 時間帯の 一覧を 作る。 始まりの 順に 並べ替えれば、 前から 1 回なめるだけで まとめられます。 
3 つの
組に 分けて 新しい 区間を 差し込む 始まりの
順に 並んだ重ならない 予約の 並びに、 新しい 予約を 1 本差し込み、 重なる 物を まとめた 並びを 返す。 手前、 重なる 所、 後ろの 3 つに 分ければ、 並べ替えずに 前から 1 回なめるだけで 済みます。 
終わりの
順の 貪欲で 重なりを消す 1 台の
機械に 入った 作業の 時間帯の 並びから、 残りが 重ならないように 外す本数の 最少を 求める。 終わりの 早い順に 並べ、 残せる 物を 前から 選んでいくと、 外す本数が 最も 少なくなります。 2 本の
指で 2 人とも 空いている 日を 求める 2 人それぞれの、
日の 順に 並んだ 休みの 範囲の 一覧から、 2 人とも 休みの 範囲を 並べて返す。 両方の 並びに 指を 1 本ずつ 置き、 先に 終わる 方の 指を 進めれば、 1 回なめるだけで 全部の 重なりが 拾えます。 始まりと
終わりを 分けて 要る 部屋の 数を 数える 研修の
日程の 並びから、 同じ 部屋で 日が 重ならないように 割り当てる ときに 要る 部屋の 最少の 数を 求める。 始まりの 日と 最終日を 別々に 並べて 前から 数えれば、 同時に 開いている 研修の 最大の 数が 分かります。 最小
ヒープで 点を 含む 最も 短い 区間を 答える 電波の
届く 範囲の 並びと、 問い合わせの 地点の 並びから、 地点ごとに そこへ 届く 範囲の うち最も 短い物の 長さを 返す。 範囲と 地点を どちらも 左から 並べ、 届き始めた 範囲を 長さの 短い順の ヒープに 入れていけば、 地点ごとに ヒープの 根を 見るだけで 答えが 出ます。
- 並べ替えで
重なる 区間を 1 つにまとめる会議室の予約の時間帯の並びから、重なったり接したりする時間帯をまとめて、使われている時間帯の一覧を作る。始まりの順に並べ替えれば、前から 1 回なめるだけでまとめられます。 - 3 つの
組に 分けて 新しい 区間を差し込む始まりの順に並んだ重ならない予約の並びに、新しい予約を 1 本差し込み、重なる物をまとめた並びを返す。手前、重なる所、後ろの 3 つに分ければ、並べ替えずに前から 1 回なめるだけで済みます。 - 終わりの
順の 貪欲で 重なりを消す1 台の機械に入った作業の時間帯の並びから、残りが重ならないように外す本数の最少を求める。終わりの早い順に並べ、残せる物を前から選んでいくと、外す本数が最も少なくなります。 - 2 本の
指で 2 人とも 空いている 日を求める2 人それぞれの、日の順に並んだ休みの範囲の一覧から、2 人とも休みの範囲を並べて返す。両方の並びに指を 1 本ずつ置き、先に終わる方の指を進めれば、1 回なめるだけで全部の重なりが拾えます。 - 始まりと
終わりを 分けて 要る 部屋の 数を数える研修の日程の並びから、同じ部屋で日が重ならないように割り当てるときに要る部屋の最少の数を求める。始まりの日と最終日を別々に並べて前から数えれば、同時に開いている研修の最大の数が分かります。 - 最小ヒープで
点を 含む 最も 短い 区間を答える電波の届く範囲の並びと、問い合わせの地点の並びから、地点ごとにそこへ届く範囲のうち最も短い物の長さを返す。範囲と地点をどちらも左から並べ、届き始めた範囲を長さの短い順のヒープに入れていけば、地点ごとにヒープの根を見るだけで答えが出ます。
貪欲法
貪欲で
最後の マスに 着けるかを 判定する すごろくの
マスごとに 進める 歩数の 上限が 決まっている とき、 最初の マスから 最後の マスに 着けるかを 返す。 「いままでに 届く 最も 遠い マス」を 1 つ 持ち 歩き、 前から 1 回なめるだけで 判定できます。 
貪欲で
最後の マスまでの 最少の 跳ぶ回数を 求める すごろくの
マスごとに 進める 歩数の 上限が 決まっている とき、 最後の マスに 着くまでの 跳ぶ回数の 最少を 返す。 「あと 1 回 跳べば 届く 範囲」を 段ごとに 広げていけば、 前から 1 回なめるだけで 数えられます。 
貪欲で
輪を 1 周できる 出発点を 求める 輪に
なった 配送の 道で、 電気 自動車が 1 周できる 出発の 充電所の 番号を 返す。 電池が 足りなくなったら、 その 次の 充電所から 出発し直すと 決めるだけで、 前から 1 回なめて 答えが 出ます。 貪欲で
札を 連続する 数の 組に 分ける 数の
書かれた 札の 束を、 決まった 枚数の 連続する 数の 組に 全部 分けられるかを 返す。 残っている 最も 小さい 札は 必ず組の 先頭に なるので、 小さい 順に 組を 作っていくだけで 判定できます。 貪欲で
3 つ組の 最大から 目標を作る 3 つの
数の 組の 並びから いく つかを 選び、 位置ごとの 最大を 取って 目標の 組を 作れるかを 返す。 目標を 1 か所でも 越える 組は 使えないので 捨て、 残りの 組で 目標の 3 つの 値が そろうかだけを 見れば 判定できます。 最後の
位置を 使って 文字列を できるだけ 多く切る 文字列を、どの
文字も 1 つの 切れに しか 出ないように、 できるだけ 多くの 切れに 分けた ときの 切れの 長さを 返す。 文字ごとに 最後に 出る 位置を 先に 調べておけば、 前から 1 回なめて 切れ目を 決められます。 数の
幅を 持ち歩いて 星入りの 括弧を 判定する 開きかっこ、
閉じかっこ、 どちらにも 空にもなれる 星の 3 つの 文字だけの 文字列が、 正しいかっこの 並びに できるかを 返す。 開いたままのかっこの 数が とりうる 最小と 最大の 2 つだけを 持てば、 前から 1 回なめて 判定できます。
- 貪欲で
最後の マスに 着けるかを判定するすごろくのマスごとに進める歩数の上限が決まっているとき、最初のマスから最後のマスに着けるかを返す。「いままでに届く最も遠いマス」を 1 つ持ち歩き、前から 1 回なめるだけで判定できます。 - 貪欲で
最後の マスまでの 最少の 跳ぶ回数を求めるすごろくのマスごとに進める歩数の上限が決まっているとき、最後のマスに着くまでの跳ぶ回数の最少を返す。「あと 1 回跳べば届く範囲」を段ごとに広げていけば、前から 1 回なめるだけで数えられます。 - 貪欲で
輪を 1 周できる 出発点を求める輪になった配送の道で、電気自動車が 1 周できる出発の充電所の番号を返す。電池が足りなくなったら、その次の充電所から出発し直すと決めるだけで、前から 1 回なめて答えが出ます。 - 貪欲で
札を 連続する 数の 組に分ける数の書かれた札の束を、決まった枚数の連続する数の組に全部分けられるかを返す。残っている最も小さい札は必ず組の先頭になるので、小さい順に組を作っていくだけで判定できます。 - 貪欲で
3 つ組の 最大から 目標を作る3 つの数の組の並びからいくつかを選び、位置ごとの最大を取って目標の組を作れるかを返す。目標を 1 か所でも越える組は使えないので捨て、残りの組で目標の 3 つの値がそろうかだけを見れば判定できます。 - 最後の
位置を 使って 文字列を できるだけ多く切る文字列を、どの文字も 1 つの切れにしか出ないように、できるだけ多くの切れに分けたときの切れの長さを返す。文字ごとに最後に出る位置を先に調べておけば、前から 1 回なめて切れ目を決められます。 - 数の
幅を 持ち歩いて 星入りの 括弧を判定する開きかっこ、閉じかっこ、どちらにも空にもなれる星の 3 つの文字だけの文字列が、正しいかっこの並びにできるかを返す。開いたままのかっこの数がとりうる最小と最大の 2 つだけを持てば、前から 1 回なめて判定できます。
バックトラック
バックトラックで
並べ方を 全部作る 違う
数ばかりの 並びから、 全部の 数を 1 回ずつ 使った 並べ方を 残らず 作る。 1 つ 選んでは 先へ 進み、 戻る ときに 選んだ印を 外す、 バックトラックの 基本の 形です。 
バックトラックで
足すと 目標に なる 組み合わせを 全部 集める 何度でも
使える 数の 並びから、 足すと 目標に なる 組み合わせを、 重ならないように 全部 返します。 選ぶ、 先へ 進む、 取り消す、 をくり返すバックトラックで、 選び始める 位置を 決めて 重なりを 防ぐ 練習です。 
バックトラックで
正しく 閉じた 括弧の 並びを 全部作る n 組の
丸括弧で 作れる、 正しく 閉じた 並びを 全部、 辞書の 順で 作ります。 開き括弧は あと 何個置けるか、 閉じ括弧は 開いた 数を 越えないか、の 2 つの 決まりで 枝を 切りながら 1 文字ずつ伸ばす、 バックトラックの 練習です。 バックトラックで
電話の ボタンの 数字から 作れる 文字の 並びを 全部 集める 昔の
携帯電話の ボタンには、 数字ごとに 英字が いくつか 割り当てられています。 押した 数字の 並びから 作れる 英字の 並びを、 決まった 順で 全部 集める 練習です。 バックトラックで
同じ値を 含む 並びから 重ならない 部分集合を 全部 集める 同じ
値が 何度か 出てくる 整数の 並びから、 選び方の 違う 部分集合を、 同じ物を 2 回入れずに 全部 集めます。 並べ替えてから 「同じ段で 同じ値を 2 回選ばない」と 決めて 重なりを 防ぐ 練習です。 バックトラックで
1 つずつしか 使えない 数から 足すと 目標に なる 組を 全部 集める 同じ
値が 何度か 出てくる 数の 並びから、 それぞれの 数を 1 回までしか 使わずに、 足すと 目標に なる 組を 重なりなく 全部 集めます。 並べ替えて、 同じ段で 同じ値を 2 回選ばない 練習です。 バックトラックで
文字列を 回文だけに 区切る 方法を 全部 集める 文字列を、どの
部分も 前から 読んでも 後ろから 読んでも 同じ (回文) に なるように 区切る 方法を、 全部 集めます。 頭から 1 つ目の 部分の 長さを 決めては 残りを 同じように 区切る、を 繰り返す練習です。 バックトラックで
文字の 盤の 上を たどって 言葉が 作れるか 調べる 英字が
升目に 並んだ盤の 上で、 隣り合う マスを たどって 言葉を 作れるかを 調べます。 通った マスに 印を 付けて 進み、 行き止まりなら印を 外して 戻る 練習です。 バックトラックで
互いに 取り合わない n 個の クイーンの 置き方を 全部 集める n 行 n 列の
盤に、 縦・ 横・ 斜めの どれでも 取り合わないように n 個の クイーンを 置く 方法を 全部 集めます。 1 行に 1 個ずつ 置き、 使った 列と 2 本の 斜めを 集合で 覚えて、 置けない 所を O(1) で 飛ばす練習です。
- バックトラックで
並べ方を全部作る違う数ばかりの並びから、全部の数を 1 回ずつ使った並べ方を残らず作る。1 つ選んでは先へ進み、戻るときに選んだ印を外す、バックトラックの基本の形です。 - バックトラックで
足すと 目標に なる 組み合わせを 全部集める何度でも使える数の並びから、足すと目標になる組み合わせを、重ならないように全部返します。選ぶ、先へ進む、取り消す、をくり返すバックトラックで、選び始める位置を決めて重なりを防ぐ練習です。 - バックトラックで
正しく 閉じた 括弧の 並びを全部作るn 組の丸括弧で作れる、正しく閉じた並びを全部、辞書の順で作ります。開き括弧はあと何個置けるか、閉じ括弧は開いた数を越えないか、の 2 つの決まりで枝を切りながら 1 文字ずつ伸ばす、バックトラックの練習です。 - バックトラックで
電話の ボタンの 数字から 作れる 文字の 並びを 全部集める昔の携帯電話のボタンには、数字ごとに英字がいくつか割り当てられています。押した数字の並びから作れる英字の並びを、決まった順で全部集める練習です。 - バックトラックで
同じ値を 含む 並びから 重ならない 部分集合を 全部集める同じ値が何度か出てくる整数の並びから、選び方の違う部分集合を、同じ物を 2 回入れずに全部集めます。並べ替えてから「同じ段で同じ値を 2 回選ばない」と決めて重なりを防ぐ練習です。 - バックトラックで
1 つずつしか 使えない 数から 足すと 目標に なる組を 全部集める同じ値が何度か出てくる数の並びから、それぞれの数を 1 回までしか使わずに、足すと目標になる組を重なりなく全部集めます。並べ替えて、同じ段で同じ値を 2 回選ばない練習です。 - バックトラックで
文字列を 回文だけに 区切る 方法を 全部集める文字列を、どの部分も前から読んでも後ろから読んでも同じ (回文) になるように区切る方法を、全部集めます。頭から 1 つ目の部分の長さを決めては残りを同じように区切る、を繰り返す練習です。 - バックトラックで
文字の 盤の 上を たどって 言葉が 作れるか調べる英字が升目に並んだ盤の上で、隣り合うマスをたどって言葉を作れるかを調べます。通ったマスに印を付けて進み、行き止まりなら印を外して戻る練習です。 - バックトラックで
互いに 取り合わない n 個の クイーンの 置き方を 全部集めるn 行 n 列の盤に、縦・横・斜めのどれでも取り合わないように n 個のクイーンを置く方法を全部集めます。1 行に 1 個ずつ置き、使った列と 2 本の斜めを集合で覚えて、置けない所を O(1) で飛ばす練習です。
動的計画法 (DP)
動的計画法
(DP) で 階段の 上り方を 数える 1 段か
2 段ずつ 上る とき、 n 段の 階段の 上り方が 何通り あるかを 数える。 小さな 段の 答えを 覚えて 使い回す、 動的計画の 最初の 練習です。 
動的計画法で
通行料つきの 階段を いちばん 安く上る 段ごとに
決まった 通行料を 払うと、 そこから 1 段か 2 段上れる 階段で、 いちばん上へ 抜けるまでの 合計を 最も 安くします。 前の 2 段の 答えだけを 持ち歩く、 階段の 数え方の 続きの 練習です。 
動的計画法で
碁盤の 目の 左上から 右下への 道順を 数える 碁盤の
目の 町を、 右か下へ 1 マスずつだけ 進んで 左上から 右下へ 行く 道順が 何通り あるかを 数えます。 上と 左の マスの 答えを 足して 表を 埋める、 2 次元の 動的計画の 入口の 練習です。 動的計画法で
最大部分配列和を 求める 整数の
並びから、 続いた 区間の 合計の うち最大の 値を 求める。 「ここで 終わる 区間の 最大」を 1 つ 持ち 歩き、 並びを 1 回なめるだけで 解く 考え方の 練習です。 動的計画法で
隣り合わない 要素の 合計を 最大にする 日ごとの
稼ぎの 並びから、 続けて 2 日は 選ばない 決まりで 合計の 最大を 求める。 各日で 「選ぶ」 「選ばない」の 2 通りを 比べて 表を 埋める、 動的計画の 練習です。 動的計画法
(DP) で おつりの 硬貨の 枚数を 最も 少なくする 何種類かの
硬貨を 何枚でも 使える とき、 ちょうど ある 金額を 作るのに 要る 最も 少ない 枚数を 求める。 大きい 硬貨から 取る 欲張りは 外れる ことが あり、 小さい 金額の 答えを 順に 積み上げる DP で 解きます。 動的計画法で
輪に なった 並びから 隣り合わない合計を 最大にする 日ごとの
稼ぎの 予定が 輪のように 繰り返し、 最後の 日と 最初の 日も 隣どうしに なる とき、 続けて 2 日は 選ばない 決まりで 合計の 最大を 求めます。 輪を 2 本の まっすぐな 並びに 分け、 同じ表の 埋め方を 2 回使う 練習です。 動的計画法で
2 つの 文字列に 共通する 最長の 部分列を 求める 2 つの
文字列から、 順番を 変えずに 文字を 拾って 作れる 共通の 並びの うち、 いちばん長い物の 長さを 求めます。 2 つの 文字列の 前から 何文字かずつを 表の 縦と 横に 取り、 欄を 順に 埋める 動的計画の 練習です。 部分和の
数え上げで 符号の 付け方を 数える 数の
並びの それぞれに + か - を 付けて 足した とき、 ちょうど 目標に なる 付け方が 何通り あるかを 数えます。 符号の 付け方の 問題を 「和が ある 数に なる 選び方の 数」に 言い換え、 1 次元の 表で 数える 練習です。 動的計画法で
硬貨の 組み合わせが 何通り あるかを 数える 何種類かの
硬貨を 何枚でも 使える とき、 ちょうど ある 金額に なる 組み合わせが 何通り あるかを 数えます。 並べる 順の 違いを 数えないために、 硬貨の 繰り返しを 外側に 置く 理由まで つかむ 練習です。 動的計画法で
文字列を 辞書の 単語に 区切れるか 調べる 空白の
抜けた 文字列を、 辞書に ある 単語だけで 区切れるかを 調べます。 「前から 何文字目までなら 区切れるか」を 表に 書き、 欲張りで 外れる 場合も 取り こぼさない 動的計画の 練習です。 動的計画法で
数字だけの 暗号を 文字に 戻す読み方を 数える A を
1、 B を 2、…、 Z を 26 と 置き換えて 区切りを 消した 数字の 列が、 何通りの 文字の 並びに 読めるかを 数えます。 最後の 1 桁か 2 桁で 場合を 分け、 前の 2 つの 答えを 足していく 練習です。 動的計画法で
最大と 最小の 積を 持ち 歩き、 積が 最大の 続いた 区間を 求める 負の
数と 0 を 含む 整数の 並びから、 続いた 区間の 積の うち最も 大きい値を 求めます。 負の 数を 掛けると 大小が 入れ替わるので、 そこで 終わる 区間の 最大と 最小を 2 つ 並べて 持ち歩く 練習です。 動的計画法で
売った 次の 日は 買えない 決まりの 売り 買いの 利益を 最大にする 毎日の
値段の 並びで、 何回でも 売り 買いできるが 売った 次の 日は 休む 決まりの とき、 利益の 最大を 求めます。 持っている、 今日 売った、 休んでいるの 3 つの 状態を 日ごとに 持ち歩く 練習です。 動的計画法
(DP) と 二分探索で 最長の 増える 部分列を 求める 整数の
並びから、 順を 保ったまま 飛び飛びに 選んで、 どんどん 大きくなる 数の 列を 作る とき、 その 最も 長い 長さを 求める。 O(n²) の DP から 入り、 長さごとの 「最も 小さい 末尾」を 二分探索で 直す O(n log n) に 縮めます。 動的計画法で
2 つの 単語の 編集距離を 求める 1 文字の
挿入、 削除、 置き換えを 何回すれば、 ある 単語を 別の 単語に 変えられるかの 最小を 求めます。 2 次元の 表で 考え、 記憶を 表の 1 行分まで 縮める ところまで 詰める 練習です。 0-1 ナップサックで
荷物を 同じ 重さの 2 組に 分ける 荷物の
重さの 並びを、 重さの 合計が 同じ 2 組に 分けられるかを 調べます。 「半分の 重さちょうどの 選び方が あるか」に 言い換え、 1 次元の 表を 後ろから 埋める 0-1 ナップサックの 練習です。 動的計画法で
2 つの 文字列を 順を 保って 混ぜると 3 つ目に なるか 調べる 2 つの
文字列の 文字を、 それぞれの 順を 変えずに 交互に 混ぜて 3 つ目の 文字列が 作れるかを 確かめます。 2 つの 文字列から 使った 文字数を 表の 縦と 横に 取り、 作れる 所を 埋めていく 練習です。 動的計画法で
低い マスから 順に 埋め、 グリッドの 上り続ける 最長の 道を 求める 高さの
書かれた グリッドを、 上下左右の 隣へ 高さが 上がり続けるように 進むとき、 通れる マスの 数の 最大を 求めます。 低い マスから 順に 「そこで 終わる 道の 長さ」を 決めていく 練習です。 動的計画法で
文字列から 別の 文字列を 拾い出す方法を 数える 文字列 s から、
順番を 変えずに 文字を 拾って 文字列 t を 作る 拾い方が 何通り あるかを 数えます。 t の 前から 何文字までを 作ったかごとの 数を、 s の 文字を 1 つずつ 読みながら 更新する 練習です。 区間の
動的計画法で 最後に 割る 風船を 決め、 得点の 合計を 最大にする 並んだ
風船を 1 つずつ 割り、 割った 風船と 左右の 隣の 数の 積を 得点に する とき、 合計の 最大を 求めます。 区間の 中で 「最後に 割る 風船」を 決めて、 左右を 別々の 小さな 区間に 分ける 練習です。 動的計画法で
ドットと アスタリスクの 入った 型が 文字列全体に 合うか 調べる 「どの
1 文字でも よい」の ドットと 「直前の 1 文字を 0 回以上くり返す」の アスタリスクを 使った 型が、 文字列の 全体に 合うかを 確かめます。 文字列と 型の 前から 何文字ずつが 合うかを 表に して 埋める 練習です。
- 動的計画法 (DP) で
階段の 上り方を数える1 段か 2 段ずつ上るとき、n 段の階段の上り方が何通りあるかを数える。小さな段の答えを覚えて使い回す、動的計画の最初の練習です。 - 動的計画法で
通行料つきの 階段を いちばん安く上る段ごとに決まった通行料を払うと、そこから 1 段か 2 段上れる階段で、いちばん上へ抜けるまでの合計を最も安くします。前の 2 段の答えだけを持ち歩く、階段の数え方の続きの練習です。 - 動的計画法で
碁盤の 目の 左上から 右下への 道順を数える碁盤の目の町を、右か下へ 1 マスずつだけ進んで左上から右下へ行く道順が何通りあるかを数えます。上と左のマスの答えを足して表を埋める、2 次元の動的計画の入口の練習です。 - 動的計画法で
最大部 分配列和を求める整数の並びから、続いた区間の合計のうち最大の値を求める。「ここで終わる区間の最大」を 1 つ持ち歩き、並びを 1 回なめるだけで解く考え方の練習です。 - 動的計画法で
隣り合わない 要素の 合計を 最大にする日ごとの稼ぎの並びから、続けて 2 日は選ばない決まりで合計の最大を求める。各日で「選ぶ」「選ばない」の 2 通りを比べて表を埋める、動的計画の練習です。 - 動的計画法 (DP) で
おつりの 硬貨の 枚数を 最も 少なくする何種類かの硬貨を何枚でも使えるとき、ちょうどある金額を作るのに要る最も少ない枚数を求める。大きい硬貨から取る欲張りは外れることがあり、小さい金額の答えを順に積み上げる DP で解きます。 - 動的計画法で
輪に なった 並びから 隣り合わない 合計を 最大にする日ごとの稼ぎの予定が輪のように繰り返し、最後の日と最初の日も隣どうしになるとき、続けて 2 日は選ばない決まりで合計の最大を求めます。輪を 2 本のまっすぐな並びに分け、同じ表の埋め方を 2 回使う練習です。 - 動的計画法で
2 つの 文字列に 共通する 最長の 部分列を求める2 つの文字列から、順番を変えずに文字を拾って作れる共通の並びのうち、いちばん長い物の長さを求めます。2 つの文字列の前から何文字かずつを表の縦と横に取り、欄を順に埋める動的計画の練習です。 - 部分和の
数え上げで 符号の 付け方を数える数の並びのそれぞれに + か - を付けて足したとき、ちょうど目標になる付け方が何通りあるかを数えます。符号の付け方の問題を「和がある数になる選び方の数」に言い換え、1 次元の表で数える練習です。 - 動的計画法で
硬貨の 組み合わせが 何通り あるかを数える何種類かの硬貨を何枚でも使えるとき、ちょうどある金額になる組み合わせが何通りあるかを数えます。並べる順の違いを数えないために、硬貨の繰り返しを外側に置く理由までつかむ練習です。 - 動的計画法で
文字列を 辞書の 単語に 区切れるか調べる空白の抜けた文字列を、辞書にある単語だけで区切れるかを調べます。「前から何文字目までなら区切れるか」を表に書き、欲張りで外れる場合も取りこぼさない動的計画の練習です。 - 動的計画法で
数字だけの 暗号を 文字に 戻す読み方を数えるA を 1、B を 2、…、Z を 26 と置き換えて区切りを消した数字の列が、何通りの文字の並びに読めるかを数えます。最後の 1 桁か 2 桁で場合を分け、前の 2 つの答えを足していく練習です。 - 動的計画法で
最大と 最小の 積を 持ち 歩き、 積が 最大の 続いた 区間を求める負の数と 0 を含む整数の並びから、続いた区間の積のうち最も大きい値を求めます。負の数を掛けると大小が入れ替わるので、そこで終わる区間の最大と最小を 2 つ並べて持ち歩く練習です。 - 動的計画法で
売った 次の 日は 買えない 決まりの 売り 買いの 利益を 最大にする毎日の値段の並びで、何回でも売り買いできるが売った次の日は休む決まりのとき、利益の最大を求めます。持っている、今日売った、休んでいるの 3 つの状態を日ごとに持ち歩く練習です。 - 動的計画法 (DP) と
二分 探索で 最長の 増える 部分列を求める整数の並びから、順を保ったまま飛び飛びに選んで、どんどん大きくなる数の列を作るとき、その最も長い長さを求める。O(n²) の DP から入り、長さごとの「最も小さい末尾」を二分探索で直す O(n log n) に縮めます。 - 動的計画法で
2 つの 単語の 編集距離を求める1 文字の挿入、削除、置き換えを何回すれば、ある単語を別の単語に変えられるかの最小を求めます。2 次元の表で考え、記憶を表の 1 行分まで縮めるところまで詰める練習です。 - 0-1 ナップサックで
荷物を 同じ 重さの 2 組に分ける荷物の重さの並びを、重さの合計が同じ 2 組に分けられるかを調べます。「半分の重さちょうどの選び方があるか」に言い換え、1 次元の表を後ろから埋める 0-1 ナップサックの練習です。 - 動的計画法で
2 つの 文字列を 順を 保って 混ぜると 3 つ目に なるか調べる2 つの文字列の文字を、それぞれの順を変えずに交互に混ぜて 3 つ目の文字列が作れるかを確かめます。2 つの文字列から使った文字数を表の縦と横に取り、作れる所を埋めていく練習です。 - 動的計画法で
低い マスから 順に 埋め、 グリッドの 上り続ける 最長の 道を求める高さの書かれたグリッドを、上下左右の隣へ高さが上がり続けるように進むとき、通れるマスの数の最大を求めます。低いマスから順に「そこで終わる道の長さ」を決めていく練習です。 - 動的計画法で
文字列から 別の 文字列を 拾い出す方法を数える文字列 s から、順番を変えずに文字を拾って文字列 t を作る拾い方が何通りあるかを数えます。t の前から何文字までを作ったかごとの数を、s の文字を 1 つずつ読みながら更新する練習です。 - 区間の
動的計画法で 最後に 割る 風船を 決め、 得点の 合計を 最大にする並んだ風船を 1 つずつ割り、割った風船と左右の隣の数の積を得点にするとき、合計の最大を求めます。区間の中で「最後に割る風船」を決めて、左右を別々の小さな区間に分ける練習です。 - 動的計画法で
ドットと アスタリスクの 入った 型が 文字列全体に 合うか調べる「どの 1 文字でもよい」のドットと「直前の 1 文字を 0 回以上くり返す」のアスタリスクを使った型が、文字列の全体に合うかを確かめます。文字列と型の前から何文字ずつが合うかを表にして埋める練習です。
設計
ヒープで
流れてくる 点数の k 番目に 高い値を すぐ 答える 仕組みを作る 点数が
1 つずつ 届く たびに、 それまでの 全部の 点数の うち k 番目に 高い 値を 返すクラスを 作ります。 上位の k 個だけを 小さい 順の ヒープに 持ち、 根を 答えに する 練習です。 
最小値を
並べて 持ち、 いちばん 小さい 値を すぐ 返す スタックを作る 積む、
取り出す、 いちばん上を 見る、 いま入っている 中の いちばん 小さい 値を 見る、の 4 つの 操作を、 どれも O(1) で こなすスタックを 作ります。 積むたびに 「ここまでの 最小値」も 一緒に 覚えて おく 練習です。 
辞書と
並びを 組み合わせて O(1) で 出し入れと 無作為な 取り出しが できる 集合を作る 値を
足す、 取り除く、 入っている 値から 1 つを 同じ 確率で 選ぶ、の 3 つを、 どれも 平均 O(1) で こなす集合を 作ります。 辞書と 並びの 2 つを 持ち、 取り除く ときは 末尾と 入れ替えて 穴を 作らない 練習です。 辞書と
双方向 リストで LRU キャッシュを 設計する 容量が
決まった 覚え場所で、 いっぱいに なったら 最も 長く 使われていない 物から 捨てる 仕組みを 作る。 辞書で 鍵から 節へ 一度で 飛び、 双方向 リストで 使った 順を 並べると、 読むのも 書くのも 平均 O(1) で 済みます。 辞書と
二分探索で 時刻つきの 設定の 履歴を 設計する 設定の
名前ごとに、 いつどの 値に したかを 全部 残し、 「ある 時刻には どの 値だったか」を 答える 仕組みを 作る。 時刻が 増える 順に 書き足される ことを 使い、 読む ときは 二分探索で 探します。 ヒープで
短い 投稿の SNS の タイムラインを 設計する 投稿する、
フォローする、 外す、 タイムラインを 見る、の 4 つの 操作を 持つ 小さな SNS を 作る。 人ごとの 投稿を 新しい 順の 列と して 持ち、 タイムラインは ヒープで 何本もの 列から 新しい 順に 10 件だけ取り出します。 2 本の
ヒープで 流れてくる 数の 中央値を すぐ 答える 仕組みを作る 数が
1 つずつ 届く たびに 足しておき、 いつ 聞かれても、 それまでの 数の 中央値を 答える 仕組みを 作ります。 小さい 半分と 大きい 半分を 2 本の ヒープに 分けて 持ち、 境目の 2 つだけを 見る 練習です。
- ヒープで
流れてくる 点数の k 番目に 高い値を すぐ 答える 仕組みを作る点数が 1 つずつ届くたびに、それまでの全部の点数のうち k 番目に高い値を返すクラスを作ります。上位の k 個だけを小さい順のヒープに持ち、根を答えにする練習です。 - 最小値を
並べて 持ち、 いちばん 小さい 値を すぐ返すスタックを作る積む、取り出す、いちばん上を見る、いま入っている中のいちばん小さい値を見る、の 4 つの操作を、どれも O(1) でこなすスタックを作ります。積むたびに「ここまでの最小値」も一緒に覚えておく練習です。 - 辞書と
並びを 組み合わせて O(1) で 出し入れと 無作為な 取り出しが できる 集合を作る値を足す、取り除く、入っている値から 1 つを同じ確率で選ぶ、の 3 つを、どれも平均 O(1) でこなす集合を作ります。辞書と並びの 2 つを持ち、取り除くときは末尾と入れ替えて穴を作らない練習です。 - 辞書と
双方 向リストで LRU キャッシュを設計する容量が決まった覚え場所で、いっぱいになったら最も長く使われていない物から捨てる仕組みを作る。辞書で鍵から節へ一度で飛び、双方向リストで使った順を並べると、読むのも書くのも平均 O(1) で済みます。 - 辞書と
二分 探索で 時刻つきの 設定の 履歴を設計する設定の名前ごとに、いつどの値にしたかを全部残し、「ある時刻にはどの値だったか」を答える仕組みを作る。時刻が増える順に書き足されることを使い、読むときは二分探索で探します。 - ヒープで
短い 投稿の SNS の タイムラインを設計する投稿する、フォローする、外す、タイムラインを見る、の 4 つの操作を持つ小さな SNS を作る。人ごとの投稿を新しい順の列として持ち、タイムラインはヒープで何本もの列から新しい順に 10 件だけ取り出します。 - 2 本の
ヒープで 流れてくる 数の 中央値を すぐ 答える 仕組みを作る数が 1 つずつ届くたびに足しておき、いつ聞かれても、それまでの数の中央値を答える仕組みを作ります。小さい半分と大きい半分を 2 本のヒープに分けて持ち、境目の 2 つだけを見る練習です。
海外の
そろった問題 149 / 150 問。準備中の
配列とハッシュ9 / 9 問
ツーポインタ5 / 5 問
スライディングウィンドウ6 / 6 問
スタック7 / 7 問
二分探索7 / 7 問
連結リスト11 / 11 問
- 35連結リストの
つなぎ先を 付け替えて 逆順にする - 36ダミーの
節で 2 本の 並んだ 連結リストを 1 本にまとめる - 37半分に
分けて 後ろを 逆にし、 連結リストを 前と 後ろから 互い 違いに並べ直す - 38間を
あけた 2 本の 指で 連結リストの 後ろから n 番目の節を外す - 39元の
節と 写しの 対応表で random つきの 連結リストを 丸ごと写す - 40繰り
上がりを 持ちながら、 1 の 位から 並んだ 2 本の 連結リストの数を足す - 41速い指と
遅い指で 連結リストの 輪を見つける - 42速い指と
遅い指で 並びの 中の 重なった数を探す - 43辞書と
双方 向リストで LRU キャッシュを設計する - 442 本ずつまとめて
k 本の 並んだ 連結リストを 1 本にする - 45つなぎ先の
付け替えで 連結リストを k 個ずつ逆順にする
木15 / 15 問
- 46再帰で
二分木を 左右反転する - 47深さ優先探索 (DFS) で
二分木の 深さを求める - 48再帰で
二分木の いちばん長い 道の 長さを求める - 49再帰で
二分木の 高さが 釣り合っているか確かめる - 50再帰で
2 本の 二分木が 同じか確かめる - 51再帰で
二分木の 中に 別の 木と 同じ 部分木が あるか確かめる - 52二分探索木の
大小で 2 つの 節の 共通の 祖先を探す - 53幅優先探索 (BFS) と
キューで 二分木を 段ごとに読む - 54幅優先探索 (BFS) で
二分木を 右から 見た ときに 見える 節を並べる - 55深さ優先探索で
根からの 道で いちばん 大きい値を 持ち回り、 二分木の よい 節を数える - 56再帰で
二分探索木の 決まりを確かめる - 57スタックの
中順の 走査で 二分探索木の k 番目に 小さい値を探す - 58辞書と
再帰で 前順と 中順の 並びから 二分木を組み直す - 59再帰で
二分木の 道の 値の 合計が いちばん 大きくなる所を探す - 60前順の
走査で 二分木を 文字列に して、 文字列から 同じ木に組み直す
トライ木3 / 3 問
ヒープ7 / 7 問
バックトラック9 / 9 問
グラフ12 / 13 問
- 80幅優先探索 (BFS) で
グリッドの 島を数える - 81幅優先探索 (BFS) と
辞書で つながりの グラフを写し取る - 82深さ優先探索 (DFS) で
グリッドの いちばん 大きい島の 広さを求める - 83幅優先探索 (BFS) で
東と 西の 両方の 海へ 流れる 場所を探す - 84盤の
端から たどって 囲まれた 空き地だけを埋める - 85幅優先探索 (BFS) で
知らせが 全員に 届くまでの 分を数える - 86幅優先探索 (BFS) で
全部の 部屋から いちばん近い 出口までの 歩数を求める - 87トポロジカルソートで
全部の 講座を 受けられるか調べる - 88トポロジカルソートと
ヒープで 講座を 受ける 順を決める - 89素集合 (Union-Find) で
木に 1 本だけ足された 余分な 道を見つける - 90つながった組の数準備中
- 91幅優先探索 (BFS) の
色塗りで、 つながった 2 人を 別の 組に 分けられるか調べる - 92幅優先探索 (BFS) で
言葉の 梯子の いちばん短い 長さを求める
グラフの応用6 / 6 問
1 次元の動的計画法12 / 12 問
- 99動的計画法 (DP) で
階段の 上り方を数える - 100動的計画法で
通行料つきの 階段を いちばん安く上る - 101動的計画法で
隣り合わない 要素の 合計を 最大にする - 102動的計画法で
輪に なった 並びから 隣り合わない 合計を 最大にする - 103まん中から
広げて 最も 長い 回文の 部分文字列を探す - 104まん中から
広げて 回文に なっている 部分文字列を 全部数える - 105動的計画法で
数字だけの 暗号を 文字に 戻す読み方を数える - 106動的計画法 (DP) で
おつりの 硬貨の 枚数を 最も 少なくする - 107動的計画法で
最大と 最小の 積を 持ち 歩き、 積が 最大の 続いた 区間を求める - 108動的計画法で
文字列を 辞書の 単語に 区切れるか調べる - 109動的計画法 (DP) と
二分 探索で 最長の 増える 部分列を求める - 1100-1 ナップサックで
荷物を 同じ 重さの 2 組に分ける
2 次元の動的計画法11 / 11 問
- 111動的計画法で
碁盤の 目の 左上から 右下への 道順を数える - 112動的計画法で
2 つの 文字列に 共通する 最長の 部分列を求める - 113動的計画法で
売った 次の 日は 買えない 決まりの 売り 買いの 利益を 最大にする - 114動的計画法で
硬貨の 組み合わせが 何通り あるかを数える - 115部分和の
数え上げで 符号の 付け方を数える - 116動的計画法で
2 つの 文字列を 順を 保って 混ぜると 3 つ目に なるか調べる - 117動的計画法で
低い マスから 順に 埋め、 グリッドの 上り続ける 最長の 道を求める - 118動的計画法で
文字列から 別の 文字列を 拾い出す方法を数える - 119動的計画法で
2 つの 単語の 編集距離を求める - 120区間の
動的計画法で 最後に 割る 風船を 決め、 得点の 合計を 最大にする - 121動的計画法で
ドットと アスタリスクの 入った 型が 文字列全体に 合うか調べる
貪欲法8 / 8 問
区間6 / 6 問
数学と幾何8 / 8 問
ビット演算7 / 7 問
そのほかの問題22 問
- ランレングス圧縮で
続く 同じ 文字を縮める - 割り算と
余りで 整数が 回文かを確かめる - 文字列の
単語を 逆順に 並べ替える - ハッシュで
最初の 重複しない 文字を探す - ツーポインタで
0 を 配列の 末尾へ移す - ソートと
ツーポインタで 目標に いちばん近い 3 つの 和を求める - 3 本の
指で 0 と 1 と 2 の 並びを 1 回で 並べ替える - ソートと
ツーポインタで 和が 目標に なる 4 つの 組を 全部集める - スライディングウィンドウで
続いた 1 の 最長を数える - スライディングウィンドウで
幅 k の 平均が 最大の所を探す - 再帰で
入れ子の 配列を 平らにする - 二分探索で
挿入位置を求める - 二分探索で
同じ 値が 続く 範囲の 両端を探す - 二分探索で
上って 下る 並びの 頂上を探す - 深さ優先探索で
二分木の 根から 葉までの 合計を調べる - 再帰で
二分木の 2 つの 節に いちばん近い 共通の 祖先を探す - 再帰で
並びから 高さの そろった 二分探索木を作る - 繰り返しで
二分探索木に 新しい 値を 葉として足す - 再帰で
二分探索木から 値を 消して 木を つなぎ直す - 幅優先探索 (BFS) で
グリッドの 最短の 道を数える - 素集合 (Union-Find) で
つながった 町の まとまりを数える - 辞書と
並びを 組み合わせて O(1) で 出し入れと 無作為な 取り出しが できる 集合を作る
解いた
言葉で