LeetCode 题解工作台
循环轮转矩阵
给你一个大小为 m x n 的整数矩阵 grid ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。 矩阵由若干层组成，如下图所示，每种颜色代表一层： 矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
我们先计算得到矩阵的层数 ，然后从外到内逐层模拟循环轮转的过程。 对于每一层，我们按照顺时针方向，将上、右、下、左四条边的元素依次放入数组 中。记数组 的长度为 。接下来，我们将 模 。然后从数组的第 个位置开始，将数组中的元素依次放回矩阵的上、右、下、左四条边。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个大小为 m x n 的整数矩阵 grid ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。
矩阵由若干层组成，如下图所示，每种颜色代表一层：
矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。轮转示例如下：
返回执行 k 次循环轮转操作后的矩阵。
示例 1：
输入：grid = [[40,10],[30,20]], k = 1 输出：[[10,20],[40,30]] 解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。
示例 2：
输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2 输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]] 解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。
提示：
m == grid.lengthn == grid[i].length2 <= m, n <= 50m和n都是 偶数1 <= grid[i][j] <= 50001 <= k <= 109
解题思路
方法一：逐层模拟
我们先计算得到矩阵的层数 ，然后从外到内逐层模拟循环轮转的过程。
对于每一层，我们按照顺时针方向，将上、右、下、左四条边的元素依次放入数组 中。记数组 的长度为 。接下来，我们将 模 。然后从数组的第 个位置开始，将数组中的元素依次放回矩阵的上、右、下、左四条边。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate recognizes the need to break the matrix into individual layers for independent rotation.
- question_mark
Look for efficient handling of large k values, ensuring that the number of rotations is minimized using modulo.
- question_mark
Evaluate how well the candidate handles matrix reconstruction after the rotations are completed.
常见陷阱
外企场景- error
Failing to account for large values of k and performing redundant rotations.
- error
Incorrectly reconstructing the matrix after rotating the layers, potentially missing positions.
- error
Overcomplicating the problem by treating the matrix as a whole rather than focusing on individual layers.
进阶变体
外企场景- arrow_right_alt
Rotating the matrix in the opposite direction (clockwise).
- arrow_right_alt
Working with an odd-dimensional matrix, requiring adjustments in layer extraction.
- arrow_right_alt
Rotating a matrix that is not square but rectangular.