コンピューターサイエンス：アルゴリズム / OS / ネットワーク / DBの導入スライド

基底を n <= 1 と書くのは 0 のためだけではありません。うっかり負の数が来ても底に着かせるための保険です。

基底で return 1 と書くと fib(0) が 1 になり、数列全体が 1 つずれます。ここだけは return n です。

引数が 2 つに増えても、減らすのは exp だけで base は据え置きです。動かす引数を 1 つに決めるのが引数が増えたときのコツです。

この切り方は合計のためだけの小技ではありません。マージソートも木の走査も、同じ「先頭と残り」の形で書かれています。

JavaScript では n / 10 が小数になります。Math.floor を挟まないと桁が落ちきらず、いつまでも 1 桁になりません。

末尾から取り出す書き方でも同じ答えになります。自分がどちら側から組み立てているかを言葉にできれば、その再帰はもう自分のものです。

a より b が大きい状態で呼んでも壊れません。1 手目の a % b が a のまま返り、次の手で勝手に入れ替わります。

全件を走るのは見つからなかったときだけです。手元の試しは大抵見つかるので速く感じますが、遅くなるのは「無いものを探した」ときです。

この取りこぼしは大きい配列では表に出ません。要素 1 個、先頭、末尾の 3 つを手でなぞったかどうかで、バグが残るかが決まります。

引数で渡すのは index だけにしてください。配列そのものを切って渡すと、コピーが log n 回起きて、速いはずの取り柄が消えます。

戻り値は n になることがあります。位置として挿入に使うぶんには正しく、そのまま arr の添字にすると範囲外です。どちらで使うかを先に決めてください。

最大値が欲しいなら全部見るしかありません。ピークは 1 つ返せば正解、と問題をゆるめた瞬間に O(n) が O(log n) に変わります。

回転しているかを先に調べる必要はありません。回転が無い配列でも同じコードが通るので、判定を足すほど分岐が増えて壊れます。

1 周まわって 1 度も交換しなかったら、その時点で抜けてよいということです。この判定を足すだけで、整列済みに近い入力は 1 周で終わります。

交換が少ないのは得ですが代償があります。遠くの最小値を先頭まで引っ張るので、同じ値どうしの元の順番は壊れます。

遅いはずの挿入ソートが Python の sorted の中で今も動いています。小さい配列や並びかけの区間では、これがいちばん速いからです。

取る側を決める比較を <= から < に変えると、同じ値のとき右が先に出ます。安定かどうかは等号 1 文字で決まります。

最悪が出るのはぐちゃぐちゃの入力ではなく、整列済みのほうです。すでに並んだデータほど本番では普通に流れてきます。

値の幅が広いから使えない、で終わりではありません。桁ごとに分けて同じことを繰り返せば基数ソートになり、大きな整数でも比較なしで並びます。

比較関数が返すのは真偽ではなく符号です。a < b と書くと true が 1 と読まれて、後ろへ回せという指示になってしまいます。

幅と高さを 1 か所に持たせておくと、あとから対角線や縦横比が要るようになってもメソッドを 1 つ足すだけで済みます。バラの変数で持つと、どの幅がどの高さと組なのかを呼ぶ側が覚え続けることになります。

空で取り出したとき、Python はその場で落ち、JavaScript は undefined を返して黙って先に進みます。落ちるほうが実は親切で、undefined は数十行あとの関係なさそうな場所で症状が出ます。

1 件ずつなら誤差ですが、キューは秒間に何千件も流れる場所で使われます。標準の deque が速いのは賢い並べ替えをしているからではなく、先頭を消さずに頭の位置だけをずらしているからです。

面接ではリンクリストが主役ですが、実務でまず選ばれるのは配列のほうです。CPU は連続したメモリを先読みするので、手数で勝っていても実測では負けることがあります。

本番で流れてくるデータは、たいてい ID 順や日付順にもう並んでいます。棒のような形は珍しい事故ではなく既定で起きるほうで、AVL 木や赤黒木は最初からその前提で作られています。

value を外からも書き換えられるようにした瞬間、値がおかしくなったとき疑う場所がクラスの外全部に広がります。メソッド経由だけに絞ると、探す場所は 5 つのメソッドの中だけで済みます。

この memo は関数の中にあるから安全です。外に出して使い回すと、前回の呼び出しの値が残ったまま次の計算に混ざります。

前回のメモ化と答えは同じですが、差が出るのは n が大きいときです。再帰版は答えを出す前に、Python なら 1000 段でスタックが先に尽きます。

同じ数列なのに位置が 1 つずれます。フィボナッチと同じと覚えて f(2) を 1 にすると、そこから先が全部ずれたまま答えが出ます。

日本の硬貨は大きい順に取れば必ず最小になるので、貪欲でも一生気づけません。額面が自分たちで決めた値のときだけ、静かに 1 枚多い答えが出ます。

この 2 つを分けているのは表を埋める向きです。1 次元に圧縮したとき容量を昇順で回すと、更新済みの自分を読んで同じ品物を何個でも詰められる側になります。

表を埋めて出るのは長さだけで、どの文字が残ったかは書かれていません。中身が欲しいときは、埋めた表を右下から逆に辿り直す手順を別に書きます。

残りをそのまま繋ぐ 1 行を忘れても、長さが同じ入力なら答えが合ってしまいます。落ちるのは長さの違う入力で、しかも末尾だけが欠けるので気づきにくいです。

余りを取り忘れても答えは合います。遅いだけです。本当に止まるのは空配列のほうで、n が 0 だと k % n が 0 除算になります。長さを見るより先に空かどうかを弾いてください。

閉じ忘れだけは、読んでいる途中で一度も間違いが起きません。最後にスタックが空かを確かめる 1 行を落とすと、この 1 通りだけが素通りします。

読む側は自分 1 文字では符号を決められず、必ず次を覗きます。だから末尾だけは覗く先がなく、i + 1 の範囲チェックを落とすとそこで落ちます。

書く側に先読みは要りません。4 と 9 を値表の行にした瞬間、大きい順に取るだけで正しくなります。判断をコードから消して表へ移す、が貪欲法の効かせ方です。

片側だけ見て水位を決めると、反対側が抜けている場所まで溜めてしまいます。min を max と書き間違えたときも例外は出ず、答えが静かに大きくなるだけです。