题目描述
思路解析动画文字版
记牢这一句:把一圈数拆成一条链,链头砍 k 个接到链尾,再摆回去。转多少次都不用真的一格一格挪,一次取模就搞定。下面从最外层开始。
整张网格 · 从外到内分两层：先给整张网格分层。橙色的是外层,一圈 12 个数;绿色的是内层,一圈 4 个数。行列都是偶数,所以每一层都是完整的一圈,没有落单的中心格。轮转的时候两层各转各的,咱们先攻外层这一圈。
外层 · 锁定这一圈 12 个数：锁定外层这一圈,一共 12 个格子。我们从左上角 (0,0) 出发,按上行、右列、下行、左列的顺时针方向,把这一圈的数依次抄下来,排成一条链。
外层 · 抄上行,左到右：沿着上行,左到右把这几个数抄下来:1、2、3。它们进到链里的顺序,就是它们在环上的顺序。
外层 · 链长到 3 位：把刚抄的接到链尾,现在这条链有 3 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
外层 · 抄右列,上到下：沿着右列,上到下把这几个数抄下来:4、8、12。它们进到链里的顺序,就是它们在环上的顺序。
外层 · 链长到 6 位：把刚抄的接到链尾,现在这条链有 6 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
外层 · 抄下行,右到左：沿着下行,右到左把这几个数抄下来:16、15、14。它们进到链里的顺序,就是它们在环上的顺序。
外层 · 链长到 9 位：把刚抄的接到链尾,现在这条链有 9 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
外层 · 抄左列,下到上：沿着左列,下到上把这几个数抄下来:13、9、5。它们进到链里的顺序,就是它们在环上的顺序。
外层 · 链长到 12 位：把刚抄的接到链尾,现在这条链有 12 个数了。紫色是刚放进来的那个。一整圈全下来了,链就集齐了,接下来对它做轮转。
外层 · 轮转 2 次 = 链头砍 2 个：轮转 2 次,不用真挪 2 回。链长 12,2 对 12 取模还是 2,所以只要把链头的 2 个数,也就是标红的 1 和 2,整体搬到链尾就行。
外层 · 挪完的新链：搬完就是这条新链:原来的链头 1 和 2 跑到了最后面(绿色),其余的数整体往前顶了 2 位。这就是这一层轮转 2 次之后该有的排布,接下来按原位置把它摆回环里。
外层 · 回填上行：按刚才抄链的同一条路线,把新链的数依次摆回上行这几格:3、4、8。位置一一对应,一个不差。
外层 · 回填右列：按刚才抄链的同一条路线,把新链的数依次摆回右列这几格:12、16、15。位置一一对应,一个不差。
外层 · 回填下行：按刚才抄链的同一条路线,把新链的数依次摆回下行这几格:14、13、9。位置一一对应,一个不差。
外层 · 回填左列：按刚才抄链的同一条路线,把新链的数依次摆回左列这几格:5、1、2。位置一一对应,一个不差。
外层 · 这一圈转好了：外层一圈全部摆回,这一层就转好了。可以对照一下第一行,已经从 1、2、3、4 变成了 3、4、8、12。外层收工,接着钻进内层。
内层 · 锁定这一圈 4 个数：外层已经转好了,标成绿色定住。现在轮到内层这一圈,一共 4 个格子。同样从它的左上角 (1,1) 起,顺时针把这 4 个数抄成一条链。
内层 · 抄上行与右列：沿着上行与右列把这几个数抄下来:6、7。它们进到链里的顺序,就是它们在环上的顺序。
内层 · 链长到 2 位：把刚抄的接到链尾,现在这条链有 2 个数了。紫色是刚放进来的那个。继续沿着环往下抄。
内层 · 抄下行与左列：沿着下行与左列把这几个数抄下来:11、10。它们进到链里的顺序,就是它们在环上的顺序。
内层 · 链长到 4 位：把刚抄的接到链尾,现在这条链有 4 个数了。紫色是刚放进来的那个。一整圈全下来了,链就集齐了,接下来对它做轮转。
内层 · 轮转 2 次 = 链头砍 2 个：轮转 2 次,不用真挪 2 回。链长 4,2 对 4 取模还是 2,所以只要把链头的 2 个数,也就是标红的 6 和 7,整体搬到链尾就行。
内层 · 挪完的新链：搬完就是这条新链:原来的链头 6 和 7 跑到了最后面(绿色),其余的数整体往前顶了 2 位。这就是这一层轮转 2 次之后该有的排布,接下来按原位置把它摆回环里。
内层 · 回填上行与右列：按刚才抄链的同一条路线,把新链的数依次摆回上行与右列这几格:11、10。位置一一对应,一个不差。
内层 · 回填下行与左列：按刚才抄链的同一条路线,把新链的数依次摆回下行与左列这几格:6、7。位置一一对应,一个不差。
内层 · 这一圈转好了：内层这一圈也摆回原位,两层都转完了。整张矩阵的最终形态就出来了。
最终矩阵 · 对照答案：两层都转好,最终矩阵就是这张网格,和题面给的答案一模一样。回头看整套流程,核心就三步:拆环成链、链头砍 k 个接到链尾、按原位置摆回去。层与层之间互不影响,分开处理就好。
边界想清:2 乘 2 是最小的一层环;k 是环长整数倍时取模为 0、原样返回;多层时各层按各自环长分别取模。
面试重点:逐层拆环成链、循环左移用取模压 k、时间 O(m 乘 n)、空间 O(m 加 n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]: def rotate(p: int, k: int): nums = [] for j in range(p, n - p - 1): nums.append(grid[p][j]) for i in range(p, m - p - 1): nums.append(grid[i][n - p - 1]) for j in range(n - p - 1, p, -1): nums.append(grid[m - p - 1][j]) for i in range(m - p - 1, p, -1): nums.append(grid[i][p]) k %= len(nums) if k == 0: return nums = nums[k:] + nums[:k] k = 0 for j in range(p, n - p - 1): grid[p][j] = nums[k] k += 1 for i in range(p, m - p - 1): grid[i][n - p - 1] = nums[k] k += 1 for j in range(n - p - 1, p, -1): grid[m - p - 1][j] = nums[k] k += 1 for i in range(m - p - 1, p, -1): grid[i][p] = nums[k] k += 1 m, n = len(grid), len(grid[0]) for p in range(min(m, n) >> 1): rotate(p, k) return grid复杂度
- 时间：O(m·n)，所有层的环加起来正好覆盖矩阵的每一个格子。取环、轮转、回填每个格子都只被读写常数次,k 通过一次取模压成不超过环长,不会真的转 k 遍。所以总时间随格子数线性增长,与 m 乘 n 成正比
- 空间：O(max(m,n))，按峰值算。每次只为当前这一层开一条链 nums,最外层的环最长,长度是 2 乘 m 加 2 乘 n 再减 4 的量级,即 O(m 加 n)。逐层处理时旧链可以复用,峰值就是最长的那条环,不额外随面积增长
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么 k 要先取模,不取会怎样?
追问时间和空间复杂度各是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
迷宫中离入口最近的出口
LeetCode 1926 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题