题目描述
思路解析
一句话答案：LeetCode 1914 循环轮转矩阵：把矩阵拆成一圈套一圈的同心环，每层顺时针抄成一条链、循环左移 k%环长 位再原样摆回——k 取模避开真转 k 遍，时间 O(m·n)。
轮转 k 次后的矩阵长什么样
给一个 m 行 n 列的整数矩阵 grid，m、n 都是偶数，外加次数 k。把矩阵看成一圈套一圈的同心方环，一次循环轮转让每个数挪到逆时针方向的邻格，每层各转各的。返回做完 k 次后的矩阵。题面第二个例子 grid=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]、k 取 2，两层各转两步得出结果。
老实转 k 次，为什么会卡死
k 能到十的九次方，照定义一次挪一格、每层转满 k 遍，光外圈就得挪十亿量级次，一个用例就耗光时间。另一个隐蔽错法是把整个矩阵当一个大圈转——外圈、内圈是长度不同的独立环，混着转会让两层的数串到对方位置，结果全乱。所以既要压掉重复转动，又得逐层拆开。
一圈就是一条能拉直的独立链
盯住一整圈：外圈 12 个数首尾相接绕成一个环，转动只让它们沿环滑动。既是环，就能从某格起把它拉直成一条一维的链，链上第 x 个数对应环上第 x 个位置。轮转一次在链上就是所有数往前挪一格、链头补到链尾，即循环左移一位——链按顺时针抄，往前挪一格落到逆时针邻格，对上逆时针轮转；转 k 次即左移 k 位。而链左移满自己的长度就回到原样，真正要挪的是 k 对环长取模的余数。
抄链、移位、按原路摆回，一层三步
对每层先固定左上角，按上行左到右、右列上到下、下行右到左、左列下到上的顺时针顺序，把环上的值抄进一条链 nums。四条边共用四个拐角，每段循环都用半开边界、只含起点那端，拐角便只归一条边、只抄一次。抄满一圈后 k 先对 len(nums) 取模，余数为 0 就原样跳过；否则切成 nums[k:]+nums[:k] 完成左移。再按抄链那条路线把新链逐格写回：取链和写回互为逆操作，链上第几个才落回环上第几格。外层的 p 逐层从 0 走到较短边的一半。
grid=[[1..16]]、k 取 2，两层各转出什么
先看外层。从 (0,0) 顺时针抄链：上行 1、2、3，右列 4、8、12，下行 16、15、14，左列 13、9、5，凑成 nums=[1,2,3,4,8,12,16,15,14,13,9,5]，长 12。2 对 12 取模仍是 2，把链头 1、2 搬到链尾。按同路线写回后，第一行从 1、2、3、4 变成 3、4、8、12。
再看内层。从 (1,1) 顺时针抄链得 6、7、11、10，长 4；2 对 4 取模是 2，把链头 6、7 搬到尾，写回内圈四格。两层拼起来就是最后的矩阵。
偶数行列保证每层都是完整一圈
时间 O(m·n)：所有层的环加起来正好铺满整个矩阵，每格只被读写常数次，k 靠取模不会真转很多遍。空间 O(max(m,n))：每次只为当前层开一条链，最外层那条最长，逐层复用不叠加。
m、n 都是偶数保证每层都是完整一圈、不剩孤零零的中心格，最小的一层就是 2×2 四个数。k 恰是某层环长整数倍时取模得 0，这层原样返回，硬去切片纯属白费。层数不同环长也不同，每层都得拿自己的环长各算各的取模，共用一个余数会把某层转错。取环和写回若用了不同绕行方向，数就落到错位的格子里，两趟必须严格同向。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:把一圈数拆成一条链,链头砍 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题