SWE · CodeSignal OA

Capital One 矩阵命令:反转行、交换行与顺时针旋转

OA 给 n×m 矩阵与命令序列 reverseRow、swap、rotate;逐条执行并维护旋转后的维度和下标。

题目重点:OA 给 n×m 矩阵与命令序列 reverseRow、swap、rotate;逐条执行并维护旋转后的维度和下标。

题意与假设

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

  • 训练版矩阵是非空矩形,命令索引 0-based 且在执行当时当前行数范围内;若旋转后维度改变,后续索引针对新矩阵。
  • reverseRow 只颠倒该行元素顺序,swap 交换整行,rotate 生成顺时针 90° 的新矩阵。
  • 输入可以原地修改的权限未披露;训练版复制初始矩阵,返回新对象。

解题路线

  1. 先把每条命令解析为类型和整数参数,按输入序执行;不要把多个 rotate 提前合并,除非中间没有行操作。
  2. reverseRow r 对当前矩阵第 r 行做反转;swap r1 r2 交换两行,包括 r1==r2 的 no-op。
  3. 若当前尺寸 R×C,顺时针旋转后尺寸 C×R,映射 old[r][c]→new[c][R−1−r];两次连续 rotate 是 180°,但后续 row 操作的索引范围可能不同。
  4. 每一步维护矩阵 dimensions 与操作后的状态;用非方阵 2×3 测维度交换,再做后续 reverse/swap。
  5. 复杂度按每条命令计,若允许惰性旋转视图可以减少复制,但行操作在旋转视图下会变列操作,设计更复杂。

手动走一遍

训练初始 [[1,2,3],[4,5,6]];rotate 后 [[4,1],[5,2],[6,3]];reverseRow 1 后 [[4,1],[2,5],[6,3]];swap 0,2 后 [[6,3],[2,5],[4,1]]。此例强调后续 row 以 3×2 新矩阵为准。

规模与取舍

R×C 矩阵,reverseRow O(C)、swap 行引用 O(1)(若深复制则 O(C))、rotate O(RC) 时间与新空间。K 条命令总成本为各步当前维度的和,最坏 O(KRC),存储 O(RC)。

易错点与追问

容易失分的边界

  • 把顺时针写成逆时针。
  • 非方阵旋转后仍用旧行数检查索引。
  • 将命令排序或合并,改变执行顺序。
  • reverseRow 操作变成反转行的顺序而非元素顺序。
  • 假设无效索引会静默忽略但原题没说。

继续深挖

  • 大量 rotate 如何用方向标记懒执行?
  • 允许子矩阵旋转时怎样改?
  • 矩阵很大但命令很多、最后只查少量单元格如何优化?
✓已复制微信号!