LeetCode 1260. 二维网格迁移Shift 2D Grid题解从暴力模拟到三次旋转的数学优化【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇题解以 LeetCode 1260「二维网格迁移」为核心完整解析题目的迁移规则、约束边界并给出两种解法最直接的模拟法以及利用二维到一维映射 三次旋转的数学分析法。读完本文你将掌握矩阵循环右移类题目的通用套路理解为什么k需要对m * n取模以及三次反转reverse实现原地旋转的数学原理并能直接运行文中的 Python 代码通过该题。题目描述给你一个n行m列的二维网格grid和一个整数k你需要将grid迁移k次。每次「迁移」操作将会引发下述活动位于grid[i][j]的元素将会移动到grid[i][j 1]位于grid[i][m - 1]的元素将会移动到grid[i 1][0]位于grid[n - 1][m - 1]的元素将会移动到grid[0][0]。请你返回k次迁移操作后最终得到的二维网格。换句话说整个网格中的元素每一轮都统一向右平移一格同一行内向右移动行尾元素溢出到下一行的开头最后一个元素右下角则绕回左上角——这正是把整个矩阵按行展开后做一次整体右移一位的直观体现。示例示例 1输入grid [[1,2,3],[4,5,6],[7,8,9]], k 1 输出[[9,1,2],[3,4,5],[6,7,8]]示例 2输入grid [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k 4 输出[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]示例 3输入grid [[1,2,3],[4,5,6],[7,8,9]], k 9 输出[[1,2,3],[4,5,6],[7,8,9]]示例 3 很好地揭示了一个关键性质当k恰好等于元素总数n * m这里是9时网格恢复原状因为每个元素恰好绕行一整圈。约束条件提示1 grid.length 50即1 n 501 grid[i].length 50即1 m 50-1000 grid[i][j] 1000元素可以是负数解法对正负不敏感0 k 100由于n、m最大为 50矩阵规模很小但k最大可达 100若k很大如100而矩阵很小如1 x 1模拟法会做大量无意义循环这正是需要数学优化的原因之一。前置知识数组本仓库 thinkings/basic-data-structure.md 中对数组这一线性结构有系统讲解指出数组是最简单、也最常见的数据结构栈、队列等都可看作受限数组本题的一维化操作正是把二维数组按行拼接视为一段连续的一维数组。数学取模运算利用k % m * n缩小循环范围利用下标对m取模实现行/列间的绕回。本题在仓库中收录于 collections/easy.md第 48 行与 collections/easy.en.md第 49 行属于 easy 难度的数组/模拟入门题也被 introduction.md 列为推荐刷题路径之一。方法一模拟法直接翻译题目思路不引入任何技巧直接按照题目给出的三条迁移规则逐格搬移每轮迁移前先用deepcopy保存旧网格old然后遍历所有(i, j)将old[i][j]写入迁移后的目标位置。这样一轮迁移只依赖迁移前的快照不会发生边搬边被覆盖的串扰问题。由于题目是 easy 难度、数据规模小这种暴力直译的做法勉强可以通过原文档原话由于是 easy上述做法勉强可以过。代码Pythonfrom copy import deepcopy from typing import List class Solution: def shiftGrid(self, grid: List[List[int]], k: int) - List[List[int]]: n len(grid) m len(grid[0]) for _ in range(k): old deepcopy(grid) for i in range(n): for j in range(m): if j m - 1: grid[(i 1) % n][0] old[i][j] elif i n - 1 and j m - 1: grid[0][0] old[i][j] else: grid[i][j 1] old[i][j] return grid代码要点与逻辑推敲行尾元素j m - 1移动到下一行开头grid[(i 1) % n][0]其中(i 1) % n保证最后一行i n - 1时绕回第 0 行从代码结构看elif i n - 1 and j m - 1分支实际上永远不会单独进入因为只要j m - 1就已被第一个分支接管而当i n - 1时(i 1) % n 0恰好在第一个分支里写入grid[0][0]。该分支在逻辑上是冗余的属于原文档作者保留的直译规则写法不影响正确性deepcopy保证old是完整快照代价是每轮 O(n·m) 的拷贝开销。复杂度分析时间复杂度O(k · n · m)——每轮迁移遍历全部n * m个元素共k轮空间复杂度O(n · m)——每轮deepcopy需要一份与网格等大的快照。当k 100、n m 50时需要执行100 × 2500 250000次元素搬运仍可接受但明显存在大量重复劳动因此我们考虑优化。方法二数学分析二维展平 三次旋转思路把二维迁移化归为一维旋转仔细观察迁移规则可以发现规律把二维网格按行展开成一段长度为n * m的一维数组[grid[0][0], grid[0][1], ..., grid[0][m-1], grid[1][0], ..., grid[n-1][m-1]]那么迁移一次恰好等价于把这段一维数组整体右移一位普通元素右移一格、行尾元素成为下一行开头、末尾元素绕回开头。迁移k次等价于一维数组整体右移k位。于是问题转化为经典的一维循环右移问题——LeetCode 上的原题是 189. 旋转数组两者本质都是序列循环右移只是载体分别是数组与链表。仓库 selected/LIS.md 中甚至把循环移位作为独立技巧复用于最长递增子序列的变体题。取模缩小 k右移n * m位等于不移动因此k % m * n这可以把k从最大 100 压缩到[0, n*m)区间内避免无意义的重复旋转。三次旋转法reverse 三段式对长度为L n * m的一维数组右移k位等价于执行三次原地反转reverse(0, L - k - 1) # 反转前 L-k 个元素 reverse(L - k, L - 1) # 反转后 k 个元素 reverse(0, L - 1) # 反转整个数组数学原理这是通用算法结论也是原文档所引循环移位算法的核心设数组分为前段A长度为L - k与后段B长度为k目标结果是把[A, B]变成[B, A]。对任意子段一次反转会逆序该段两次反转则恢复原序。三次反转过程为反转A得[rev(A), B]反转B得[rev(A), rev(B)]反转整体得[rev(rev(B)), rev(rev(A))] [B, A]。于是数组完成右移k位的效果。整个过程只用常数个辅助变量双指针交换是原地操作。代码Pythonfrom typing import List class Solution: def shiftGrid(self, grid: List[List[int]], k: int) - List[List[int]]: n len(grid) m len(grid[0]) # 二维到一维按行展开 arr [grid[i][j] for i in range(n) for j in range(m)] # 取模缩小 k 的范围避免无意义的运算 k % m * n res [] # 双指针原地反转子段 [l, r] def reverse(l: int, r: int) - None: while l r: t arr[l] arr[l] arr[r] arr[r] t l 1 r - 1 # 三次旋转右移 k 位的标准做法 reverse(0, m * n - k - 1) reverse(m * n - k, m * n - 1) reverse(0, m * n - 1) # 一维到二维按每行 m 个元素重新分组 row [] for i in range(m * n): if i 0 and i % m 0: res.append(row) row [] row.append(arr[i]) res.append(row) return res代码要点二维 → 一维arr [grid[i][j] for i in range(n) for j in range(m)]按行序展开保证展平后的下标idx i * m j与迁移规则一致三次反转边界reverse(0, m*n-k-1)、reverse(m*n-k, m*n-1)、reverse(0, m*n-1)三段的切分点正是L - k与上述数学推导一一对应一维 → 二维按i % m 0判断行边界把展平数组重新切回n行m列的网格。复杂度分析时间复杂度O(N)其中N n * m。三次反转各遍历一次数组加上展平与回填各一次整体线性空间复杂度原文档标注为 O(1)。严格来说若把二维数组逻辑上视为一维并直接用双重循环做三次反转不新建arr辅助空间确为 O(1)示例代码中为清晰起见构建了一维arr实际额外占用 O(N) 辅助空间。两种写法的时间复杂度相同读者可自行将三次反转合并进二维下标映射实现严格 O(1) 空间的版本。两种方法对比维度模拟法数学分析三次旋转思路直接翻译迁移规则逐轮搬移二维展平 → 一维右移 → 重新分组时间复杂度O(k · n · m)O(n · m)空间复杂度O(n · m)deepcopy 快照O(1)原地反转逻辑层面对 k 的敏感度k 越大耗时越长先取模与 k 的大小基本无关适用场景快速 AC 的暴力解面试/竞赛的标准优化解当k接近n * m甚至更大时两者差距被放大模拟法仍要做 O(k · n · m) 次搬运而三次旋转法只与网格大小成正比。相关题目与仓库延伸阅读189. 旋转数组本题的一维原型同样的三次旋转可直接套用61. Rotate-List旋转链表把循环右移搬到链表上仓库 thinkings/linked-list.md 第 639 行在讲拼接链表考点时明确提到旋转链表与 25. K 个一组翻转链表、92. 反转链表 II 同属一组套路48. Rotate-Image旋转图像同样是矩阵变换题但旋转方向为 90°思路与本题的平移式迁移不同可对比学习thinkings/basic-data-structure.md数组基础概念的仓库内讲义适合复习前置知识。小结LeetCode 1260「二维网格迁移」表面上是一道矩阵模拟题其内核却是经典的一维数组循环右移把矩阵按行展平后迁移k次就是右移k位先用k % m * n去冗再用三次反转原地完成旋转即可把复杂度从 O(k · n · m) 优化到 O(n · m)。掌握了二维展平 三次旋转这套模板你就能同时拿下 1260、189 以及链表版本的 61 号题真正做到举一反三。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考