RCS.101.c

Map of Contents

RCS.101.c

Backtracking

[RCS.101 x Miters] Backtracking (1)

[RCS.101 x Miters] Backtracking (2)

Basic Graphs

[RCS.101 x Miters] Basic Graphs (1)

[RCS.101 x Miters] Basic Graphs (2)

Heap

[RCS.101 x Miters] Heap

Backtracking

• Learning Material

  • Princeton: Combinatorial Search

    • CodeForce: Friendly Rooks (OJ for N-rooks problem)

  • Illinois: Backtracking

  • LeetCode The Hard Way: Backtracking

Practices
M 797. All Paths From Source to Target	👉 Forum
M 46. Permutations	👉 Forum
M 079. Letter Tile Possibilities	👉 Forum
M 17. Letter Combinations of a Phone Number	👉 Forum

Graduation Challenge
M 22. Generate Parentheses	👉 Forum
M 216. Combination Sum III	👉 Forum
H 51. N-Queens	👉 Forum
M 967. Numbers With Same Consecutive Differences	👉 Forum

---

Basic Graphs

Trees

Trees are a common non-linear data structure. They don’t store data in a linear way, but instead organize hierarchically. A tree is normally represented by nodes which contain a value and point to other nodes.

Learning Material

• Google Tech Dev Guide: Trees

• Learning Material

  • LeetCode The Hard Way: Graph Theory

  • LintCode: 第二章：数据结构（上）之并查集与字典树

  • Disjoint Set, CodeForce: UnionFind (aka Disjoint Set Union, DSU, UnionFind)

    Quick Find, Quick Union

    • E 1971. Find if Path Exists in Graph

    • E Number of Islands

  • Google Tech Dev Guide: Graphs

• Practices

  • M 105. Construct Binary Tree from Preorder and Inorder Traversal

  • M 178 · Graph Valid Tree

  • M 128. Longest Consecutive Sequence

  • M 990. Satisfiability of Equality Equations

• Graduation Challenge

  • 能答出 Undirected graphs, Directed graphs, Weighted graphs, Cyclic graphs, Acyclic Graph 的區別

  • M 1202. Smallest String With Swaps

  • M 547. Number of Provinces

  • M 1319. Number of Operations to Make Network Connected

---

Heap

A heap is a tree-based data structure that usually comes in two varieties: (1) Max-heaps where the the value in any node is greater than all the values in it's child nodes and (2) Min-heaps where the value in any node is less than all of the values in it's child nodes.

Learning Material

• LeetCode the Hard Way: Heap (Priority Queue)

  • E 1046. Last Stone Weight

  • E 464 · Sort Integers II with Heap Sort

• Google Tech Dev Guide: Heaps

• Practices

  • E 2974. Minimum Number Game

  • E 506. Relative Ranks

  • M 2336. Smallest Number in Infinite Set

• Graduation Challenge

  • E 1464. Maximum Product of Two Elements in an Array

  • E 1337. The K Weakest Rows in a Matrix

  • M 451. Sort Characters By Frequency

  • M 1845. Seat Reservation Manager