SWE · VO Coding

Microsoft 3×3 九宫格旋转 180°:坐标映射与原地交换

对九宫格每个位置取对角中心对称坐标,解释为何旋转 180° 等于先反转行顺序再反转各行。

题目重点:对九宫格每个位置取对角中心对称坐标,解释为何旋转 180° 等于先反转行顺序再反转各行。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 输入恰为 3×3 数字矩阵,返回新的 3×3 矩阵,不改输入;若要求原地,可交换每格与其中心对称位置一次。
  • 坐标从 0 开始,旋转 180° 映射 (r,c)→(2−r,2−c),中心 (1,1) 不变。
  • 这不是左右镜像,也不是顺时针 90°。

解题路线

  1. 新矩阵 result[r][c]=grid[2−r][2−c],双循环填满 9 个位置。
  2. 等价操作是把行顺序颠倒,再把每行元素顺序颠倒;只做其中一步是反射,不是旋转。
  3. 若面试要求 O(1) 附加空间,可遍历 9 个坐标,只在 (r,c) 的行优先序小于对称坐标时交换,中心跳过,避免交换两次。
  4. 正确性:连续两次映射 (r,c)→(2−r,2−c)→(r,c),且每个原位置有唯一目标,因此变换是一个置换。

手动走一遍

[[1,2,3],[4,5,6],[7,8,9]] 旋转后为 [[9,8,7],[6,5,4],[3,2,1]],中心 5 不动。左上 1 对应右下 9,左中 4 对应右中 6。

Python 参考实现

下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。

代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。

"""Rotate a 3x3 grid by 180 degrees without mutating the input."""


def rotate_180(grid: list[list[int]]) -> list[list[int]]:
    if len(grid) != 3 or any(len(row) != 3 for row in grid):
        raise ValueError("exactly 3x3 required")
    return [[grid[2 - r][2 - c] for c in range(3)] for r in range(3)]

复杂度

固定 3×3 是 O(1) 时间和 O(1) 新矩阵空间;推广 N×M 时 O(NM) 时间和返回矩阵 O(NM) 空间,原地可 O(1) 附加空间。

易错点与追问

容易失分的边界

  • 只反转每行,得到左右镜像。
  • 只反转行顺序,得到上下镜像。
  • 原地交换每对位置两次,最终回到原矩阵。
  • 把原题 3×3 说成要求通用矩阵或原地。

继续深挖

  • 如何把 N×M 矩阵原地做 180°,中心如何处理?
  • 90° 旋转为何在非方阵中无法原地保持同样形状?
  • 对图像像素缓冲区按行主序如何计算映射下标?
✓已复制微信号!