Life Odyssey

Leetcode面接高頻出問題まとめ

2 min

友人からもらったので、公開しません。

Leetcode面接高頻出問題まとめ

参考: https://zhuanlan.zhihu.com/p/349940945

200問以上、派生問題含めて約250問。ほとんどがmedium、少数のhard。アルゴリズム面接には十分。

ソート:

  • 基礎: Quick Sort & Merge Sortの実装、計算量、In-place、安定性
  • 入門: Leetcode 148, 56, 27
  • 応用: Leetcode 179, 75

選択:

  • Quick Selection、Heapsort。トレードオフを理解し、C++ STLの対応メソッドを知る。
    • Leetcode 215, 347, 2099
    • Leetcode 4. Median of Two Sorted Arrays

連結リスト:

  • 基礎: 実装と走査。先頭/末尾の挿入削除はO(1)、検索はO(N)
  • 入門: Leetcode 206, 876

快慢ポインタとリスト反転は基本。反転コードは暗記推奨。

  • 応用: Leetcode 160, 141, 92, 328

Heap, Dictionary, Stack, Queue:

  • Queue: Leetcode 225, 346, 281, 1429, 54, 362
  • Stack: Leetcode 155, 232, 150, 224, 20, 1472, 1209, 1249, 735
  • Hashmap: Leetcode 1, 146, 128, 73, 380, 49, 350, 299, 348
  • Heap: Leetcode 973, 347, 23, 264, 1086, 88, 692, 378, 295, 767, 1438, 895
  • Map: Leetcode 729, 981, 846, 218, 480, 318

二分探索:

  • 3つのテンプレート: [L, R), [L, R], Breakpoint
  • 明示的: Leetcode 34, 33, 1095, 162, 278, 74, 240
  • 暗黙的: Leetcode 69, 540, 644, 528, 1300, 1060, 1062, 1891

二つのポインタ:

  • 背向: Leetcode 409, 125, 5
  • 相向: Leetcode 1, 167, 15, 16, 18, 454, 277, 11
  • 同向: Leetcode 283, 26, 395, 340, 424, 76, 3, 1004

DFS (深さ優先探索):

  • 木ベース: Leetcode 543, 226, 101, 951, 124, 236, 105, 104, 987, 1485, 572, 863, 1110
  • BST: Leetcode 230, 98, 270, 235, 669, 700, 108, 333, 285
  • グラフベース: Leetcode 341, 394, 51, 291, 126, 93, 22, 586, 301, 37, 212, 1087, 399, 1274, 1376, 694, 131
  • 順列組合せ: Leetcode 17, 39, 78, 46, 77, 698, 526
  • メモ化探索: Leetcode 139, 72, 377, 1235, 1335, 1216, 97, 472, 403, 329

トポロジカルソート:

  • Leetcode 207, 444, 269, 310, 366

BFS (幅優先探索):

  • 木ベース: Leetcode 102, 103, 297, 314
  • グラフベース: Leetcode 200, 133, 127, 490, 323, 130, 752, 815, 1091, 542, 1293

累積和:

  • Leetcode 53, 1423, 1031, 523, 304

以上は高頻出。以下は中頻出。

Union Find:

  • Leetcode 721, 547, 737, 305

Trie (接頭辞木):

  • Leetcode 208, 211, 1268, 212

単調スタック/キュー:

  • Leetcode 85, 84, 907, 739, 901, 503, 239

走査線:

  • Leetcode 253, 218, 759

動的計画法:

  • Leetcode 674, 62, 70, 64, 368, 300, 354, 256, 121, 55, 45
  • Leetcode 132, 312, 1143, 1062, 718, 174, 115, 72, 91, 639
  • Leetcode 712, 221, 1277, 198, 213, 740, 87, 1140, 322, 518
  • Leetcode 1048, 44, 10, 32, 1235, 1043, 926
Algorithm LeetCode