Swift教室 Swift と競技プログラミングの教室

Part 5

Arai60 — コーディング面接編

Arai60 は、コーディング面接対策として選ばれた LeetCode の 60 問です。 出典は Kohei Arai さんの記事 で、 「各問題を 30 分以内にバグなしで実装できれば準備完了」という基準が示されています。

進め方

  1. まず自力で考えます。5〜10 分考えて分からなければ、すぐに答えを見ます。
  2. 答えを理解したら、何も見ずに書き直します。
  3. 10 分以内にノーミスで 3 回連続書けるようになるまで繰り返します。

分からない問題でうんうん唸る時間は、上達に寄与しません。 パターンを覚えて、手が勝手に動く状態を作るのが目的です。

このサイトでの解き方

各ページに問題の要約と、Solution クラスのスターターコードがあります。 右のエディタで実装して「採点」を押すと、テストコードが動いて OK / NG が分かります。

問題文の原文は各ページの LeetCode リンクから読んでください。 Premium 限定の問題（4 問）はその旨を明記しています。

  1. 01. Linked List Cycle Linked List / LeetCode 141 (Easy) — 連結リストに循環があるかを速さの違う 2 つのポインタで判定する。
  2. 02. Linked List Cycle II Linked List / LeetCode 142 (Medium) — 循環が始まるノードをフロイドの循環検出法で特定する。
  3. 03. Remove Duplicates from Sorted List Linked List / LeetCode 83 (Easy) — ソート済み連結リストの重複ノードを取り除き、各値を 1 回だけ残す。
  4. 04. Remove Duplicates from Sorted List II Linked List / LeetCode 82 (Medium) — 重複した値のノードをすべて取り除き、一度だけ現れた値を残す。
  5. 05. Add Two Numbers Linked List / LeetCode 2 (Medium) — 逆順に格納された 2 つの数を、桁上がりに注意して足す。
  6. 06. Valid Parentheses Stack / LeetCode 20 (Easy) — 括弧の並びが正しいかをスタックで判定する。
  7. 07. Reverse Linked List Stack / LeetCode 206 (Easy) — 連結リストを反転する。参照の付け替えを 1 パスで行う。
  8. 08. Kth Largest Element in a Stream Heap / LeetCode 703 (Easy) — ストリームに値を追加しながら K 番目に大きい値を返すクラスを設計する。
  9. 09. Top K Frequent Elements Heap / LeetCode 347 (Medium) — 出現回数の多い上位 K 種類の値を求める。
  10. 10. Find K Pairs with Smallest Sums Heap / LeetCode 373 (Medium) — 2 つのソート済み配列から、和が小さい順に K 個のペアを取り出す。
  11. 11. Two Sum HashMap / LeetCode 1 (Easy) — 値から添字を引く辞書で、和が target になる 2 数を 1 回の走査で探す。
  12. 12. Group Anagrams HashMap / LeetCode 49 (Medium) — ソートした文字列をキーにしてアナグラムをまとめる。
  13. 13. Intersection of Two Arrays HashMap / LeetCode 349 (Easy) — 集合の intersection で 2 つの配列の共通要素を重複なく取り出す。
  14. 14. Unique Email Addresses HashMap / LeetCode 929 (Easy) — 正規化したアドレスを集合に集めて宛先の種類を数える。
  15. 15. First Unique Character in a String HashMap / LeetCode 387 (Easy) — 出現回数を辞書で数え、2 回目の走査で最初の一意な文字を探す。
  16. 16. Subarray Sum Equals K HashMap / LeetCode 560 (Medium) — 累積和の出現回数を辞書に持ち、和が k の部分配列を数える。
  17. 17. Number of Islands Graph / LeetCode 200 (Medium) — 見つけた陸地を DFS で塗りつぶしながら島を数える。
  18. 18. Max Area of Island Graph / LeetCode 695 (Medium) — DFS の戻り値で面積を集計し、最大の島を求める。
  19. 19. Number of Connected Components in an Undirected Graph Graph / LeetCode 323 (Medium) — 隣接リストと探索で連結成分を数える。Premium 限定。
  20. 20. Word Ladder Graph / LeetCode 127 (Hard) — 1 文字違いの単語をたどる BFS で最短の変換手数を求める。
  21. 21. Maximum Depth of Binary Tree Tree / LC 104 (Easy) — 二分木の最大の深さ。木の再帰の型を覚える。
  22. 22. Minimum Depth of Binary Tree Tree / LC 111 (Easy) — 最小の深さ。子が片方だけのノードの罠に注意。
  23. 23. Merge Two Binary Trees Tree / LC 617 (Easy) — 2 つの木を重ねて値を足す。同時再帰の練習。
  24. 24. Convert Sorted Array to Binary Search Tree Tree / LC 108 (Easy) — ソート済み配列から高さ平衡な BST を作る。
  25. 25. Path Sum Tree / LC 112 (Easy) — 根から葉への経路で合計が一致するか。
  26. 26. Binary Tree Level Order Traversal Tree / LC 102 (Medium) — レベルごとの走査。BFS の基本形。
  27. 27. Binary Tree Zigzag Level Order Traversal Tree / LC 103 (Medium) — レベルごとに向きを反転して走査する。
  28. 28. Validate Binary Search Tree Tree / LC 98 (Medium) — BST の検証。値の範囲を上から伝える再帰。
  29. 29. Construct Binary Tree from Preorder and Inorder Traversal Tree / LC 105 (Medium) — 2 つの走査結果から元の木を復元する。
  30. 30. Paint Fence DP / LC 276 (Easy) — 柵を k 色で塗る場合の数。2 状態の DP。
  31. 31. Longest Increasing Subsequence DP / LeetCode 300 (Medium) — 最長増加部分列の長さを O(N²) の DP で求める。
  32. 32. Maximum Subarray DP / LeetCode 53 (Medium) — 連続部分配列の最大和。Kadane 法を DP として理解する。
  33. 33. Unique Paths DP / LeetCode 62 (Medium) — 格子上の経路数を 2 次元 DP で数える。
  34. 34. Unique Paths II DP / LeetCode 63 (Medium) — 障害物のある格子の経路数。DP の初期条件に注意。
  35. 35. House Robber DP / LeetCode 198 (Medium) — 隣り合う家を選べない条件での最大金額。取る・取らないの DP。
  36. 36. House Robber II DP / LeetCode 213 (Medium) — 円環版 House Robber。場合分けで直線の DP に帰着する。
  37. 37. Best Time to Buy and Sell Stock DP / LeetCode 121 (Easy) — 1 回の売買の最大利益。最安値を更新しながら 1 パスで走査する。
  38. 38. Best Time to Buy and Sell Stock II DP / LeetCode 122 (Medium) — 何回でも売買できる場合の最大利益。隣接差分の和に帰着する。
  39. 39. Word Break DP / LeetCode 139 (Medium) — 文字列を辞書の単語の連結に分割できるか判定する DP。
  40. 40. Coin Change DP / LeetCode 322 (Medium) — 金額を作る最小コイン枚数。作れない場合は -1 を返す。
  41. 41. Search Insert Position Binary Search / LeetCode 35 (Easy) — ソート済み配列に target を挿入すべき位置を二分探索で求める。
  42. 42. Find Minimum in Rotated Sorted Array Binary Search / LeetCode 153 (Medium) — 回転したソート済み配列の最小値を二分探索で求める。
  43. 43. Search in Rotated Sorted Array Binary Search / LeetCode 33 (Medium) — 回転したソート済み配列から target の位置を二分探索で探す。
  44. 44. Capacity To Ship Packages Within D Days Binary Search / LeetCode 1011 (Medium) — D 日以内に荷物を運びきる最小の積載量を答えの二分探索で求める。
  45. 45. Pow(x, n) Recursion / LeetCode 50 (Medium) — x の n 乗を繰り返し二乗法で O(log n) で計算する。
  46. 46. K-th Symbol in Grammar Recursion / LeetCode 779 (Medium) — 0 と 1 が増殖する列の k 番目の記号を再帰で求める。
  47. 47. Split BST Recursion / LeetCode 776 (Medium) — BST を値 V 以下と V 超の 2 つの BST に分割する。Premium 限定。
  48. 48. Longest Substring Without Repeating Characters Sliding Window / LeetCode 3 (Medium) — 同じ文字を含まない最長部分文字列の長さをスライディングウィンドウで求める。
  49. 49. Minimum Size Subarray Sum Sliding Window / LeetCode 209 (Medium) — 和が target 以上になる最短の連続部分配列を尺取り法で求める。
  50. 50. Permutations Greedy / Backtracking / LeetCode 46 (Medium) — 相異なる整数のすべての順列をバックトラッキングで列挙する。
  51. 51. Subsets Greedy / Backtracking / LeetCode 78 (Medium) — すべての部分集合を列挙する
  52. 52. Combination Sum Greedy / Backtracking / LeetCode 39 (Medium) — 同じ数を何度も使って和を target にする組合せ
  53. 53. Generate Parentheses Greedy / Backtracking / LeetCode 22 (Medium) — 正しい括弧列を n 組ぶんすべて生成する
  54. 54. Move Zeroes その他 / LeetCode 283 (Easy) — 0 を順序を保ったまま末尾へ移動する
  55. 55. Meeting Rooms その他 / LeetCode 252 (Easy) — 会議の区間が重ならず全部に出席できるか判定する
  56. 56. Meeting Rooms II その他 / LeetCode 253 (Medium) — すべての会議を開くのに必要な会議室の最小数
  57. 57. Is Subsequence その他 / LeetCode 392 (Easy) — s が t の部分列かを判定する
  58. 58. Next Permutation その他 / LeetCode 31 (Medium) — 配列を辞書順で次の順列に書き換える
  59. 59. String to Integer (atoi) その他 / LeetCode 8 (Medium) — 文字列を規則に従って 32bit 整数に変換する
  60. 60. ZigZag Conversion その他 / LeetCode 6 (Medium) — 文字列をジグザグに並べて行順に読み直す