行列
01 / 共通の仕組み
行列は単なる線形列ではなく、2 次元の座標空間 — 各セルは2 つの添字で指定され、 その組み合わせ方が問題ごとに異なる。要は正しい「歩き方」を見つけること。 3 つの古典的なサブパターン:その場回転(転置 + 行反転)、螺旋走査(4 つの境界が内側に収縮)、階段探索(片方向は単調増加、もう片方向は単調減少となる角から開始)。
01 / 一文での本質
90° 時計回りの回転は、転置 + 各行を反転に分解できる —— 2 つのきれいなその場走査の合成が ちょうど回転になる、追加グリッド不要。
問題行列をその場で 90° 時計回りに回転M3×3
3×3 の正方行列。転置後に各行を反転することで、その場で 90° 時計回りに回転する。
ステップ
0 / 11
フェーズ
入力
残り交換
—
0 / 11
02 / パターンの骨格
# フェーズ 1 — 転置:i < j について m[i][j] と m[j][i] を交換for i in 0..n-1:for j in i+1..n-1:m[i][j], m[j][i] ← m[j][i], m[i][j]# フェーズ 2 — 各行を反転for i in 0..n-1:for j in 0..n/2-1:m[i][j], m[i][n-1-j] ← m[i][n-1-j], m[i][j]# 合成 ≡ 90° 時計回り、合計 O(N²)、追加 O(1)
03 / このパターンを使うべき合図
「行列 / 画像を 90° 回転」
代表例 —— LC 48。第 2 のグリッドを確保するのではなく、
転置 → 各行反転 でちょうど回転になる。「行列を転置」
LC 867 —— フェーズ 1 単独。同じ二重ループから反転を抜くだけ。 このプリミティブを単独で認識できると応用が広がる。
「反転 / 鏡像」
反時計回り 90° = 各行を先に反転してから転置(または転置 + 各列反転)。 同じ 2 プリミティブを順序や軸を変えるだけ —— 両パスがその場で完結する形を選ぶ。
「層ごとの回転」
もう一つの O(1) 追加空間アプローチ:同心の枠を 4 元サイクルとして回す(上 ← 左 ← 下 ← 右 ← 上)。 複雑度は同じだが添字計算が脆い。1 パスで済ませる必要があるときだけ使う。
04 / よくある落とし穴
i.
転置で
i < j ではなく正方形全体を回してしまう。転置は各ペアを 1 度だけ交換する。内側の
j を 0 から n-1 まで回すと、各ペアが 2 度交換され元に戻る。 必ず j > i(厳密上三角)に絞ること。ii.
時計回りと反時計回りの取り違え。
時計回り = 転置 + 各行反転。反時計回り = 転置 + 各列反転(または各行反転 + 転置)。 方向を間違えやすい;2×2 の
[[1,2],[3,4]] で検算 —— 時計回りは [[3,1],[4,2]] になる。iii.
1 パスでその場処理しようとする。
可能(層ごと / 4 元サイクル)だが添字計算がややこしく、オフバイワンを誘いやすい。 2 段に分けるのが最も明瞭:各段は一行のスワップループ、合成が回転。やむを得ないときだけ 1 パスを採る。
05 / LeetCode で練習
4 問。1 問目は教科書的な 90° 回転;残りの 3 問は同じプリミティブ(転置、行反転)と、グリッド操作を多段の合成として捉える思考の練習。
— / どれをいつ使うか
その場回転
グリッド自体の幾何変換 — 90° / 180° 回転、転置、鏡像 — を行う問題で使う。 2 段(転置 + 行反転)に分解すれば追加グリッド無しでその場処理できる。
転置 + 反転 · LC 48
螺旋走査
縮小していく矩形の外周沿いに全セルを訪問する必要があるとき — 螺旋出力、螺旋充填、層カウント。 4 つの境界を保持し、1 周ごとに内側へ収縮させる。
4 つの境界 · LC 54 · LC 59
階段探索
行と列の両方向で単調な行列で、値を探すときに使う。 片方向が厳密に増加、もう片方向が厳密に減少する角から始めれば、 1 回の比較で 1 行または 1 列を丸ごと除外できる。
右上角から · LC 240 · O(N + M)