Algorithms study cheatsheets
Coding interview 的 Matrix cheatsheet
Matrix 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
Matrix 是二维数组。涉及 matrix 的题通常和 dynamic programming 或 graph 遍历相关。
Matrix 可用来表示 graph：每个 cell 是 node，通常有 4 个邻居（边界与角落除外）。本页聚焦“不把 matrix 当 graph”的题型；如果要把 matrix 当 graph，请看 graph section。
Corner cases
- Empty matrix（注意检查每行长度是否为 0）
- 1 x 1 matrix
- 只有一行或一列
Techniques
创建空的 N x M matrix
在 traversal 或 DP 题里，几乎总需要创建一个同尺寸的空矩阵，用来存 visited state 或 DP table。要熟悉你所用语言的写法。
Python 一行写法：
# Assumes that the matrix is non-empty
zero_matrix = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
Python 拷贝 matrix：
copied_matrix = [row[:] for row in matrix]
转置矩阵（Transpose）
Transpose 是把行变成列、列变成行。
很多 grid-based game（如 Tic-Tac-Toe、Sudoku、Crossword、Connect 4、Battleship）都可用 matrix 建模，经常要检查横向/纵向的胜利条件。一个技巧是：先写横向验证逻辑，然后对 matrix 转置，复用横向逻辑来验证原本的纵向。
Python 转置：
transposed_matrix = zip(*matrix)
Essential questions
该 topic 必练题。
Recommended practice questions
在掌握基础后推荐练习。