滴滴 10.11 后端笔试：矩阵行列交换与正方形构造

《面试题目》

1. 选择题（25 道）：Java 基础、Redis、MySQL、408 相关内容。
2. 编程题一：给定原矩阵和目标矩阵，判断能否通过相邻交换行或相邻交换列把原矩阵变成目标矩阵，若能，求最少交换次数；不能则返回 -1。
3. 编程题二：平面内有 n 个建筑，给定它们各自的坐标，求由其中 4 个建筑作端点构成的正方形，要求正方形内部和边上不存在其他建筑。

《参考解析》

编程题一：相邻交换行列到目标矩阵

先做可行性判断。行交换只能改变行的顺序、不能改变任何一行的内容，列交换同理，所以两个必要条件必须同时成立：原矩阵的「行多重集」等于目标矩阵的行多重集，且列多重集也相等——也就是把每一行看成一个整体（字符串或元组）后，两边排序应当完全一致；列同理。任一不满足直接返回 -1。

两个条件都满足后，最少交换次数可以拆成两个独立问题：把原矩阵的行排列成目标矩阵的行顺序所需的相邻交换次数，加上列的相邻交换次数。经典结论是——把一个排列通过相邻交换变成目标排列，最少交换次数等于该排列的逆序对数量（用树状数组或归并排序在 O(n log n) 内求出）。

实现上有两个容易踩的坑：

一是重复行/列的处理。如果矩阵里有完全相同的两行，目标行到原行的映射不唯一，随便选一个映射会得到偏大的逆序对数。正确做法是贪心匹配：按目标矩阵从上到下扫描，每一行去原矩阵里找第一个尚未被占用且内容相同的行作为映射来源，列同理——这样得到的映射逆序对最少。

二是行列是否真的独立。在这个问题的常规设定下，行排列与列排列互不干扰，答案是两者相加；但实现时要注意先把行列映射算清楚再分别求逆序数，不要在过程中反复重建矩阵。n 较大时注意用 O(n log n) 的逆序对算法，别写 O(n²) 的冒泡计数。

编程题二：找内部无点的正方形

几何构造题，核心是枚举边并利用「垂直且等长」直接算出另外两个顶点，避免枚举四个点。

给定一条边的两个端点 p1(x1,y1)、p2(x2,y2)，令 dx = x2-x1、dy = y2-y1，则与它垂直且等长的边向量是 (-dy, dx) 或 (dy, -dx)，于是另外两个顶点分别是 p1 + (-dy, dx)、p2 + (-dy, dx)（或另一侧的对称形式）。两个方向都要试，因为正方形可以落在这条边的两侧。判断这两个顶点是否存在于给定的点集里，用哈希表存坐标做 O(1) 查询；为了让每个正方形只被统计一次，可以规定 p1 < p2（按坐标字典序）并对两个方向都生成。

第二步校验「内部和边上不存在其他建筑」。把候选正方形的四条边与四个顶点确定下来后，遍历其余所有点判断是否落在正方形内部或边界上——用叉积判断点在平行四边形内（正方形是特例）：对四条有向边，点必须始终在同一侧或恰好在边上。这一步是 O(n)，整体 O(n² × n) = O(n³)；n 不大（几百量级）时完全够用，如果 n 上千，可以按候选正方形的包围盒做一次空间筛选（网格分桶或 kd-tree），先排除掉明显的远点再逐一精确判断。

三个必须注意的细节：坐标是整数，所有运算都可以用整数完成，不要中途转浮点导致判等失败；斜正方形（45° 那种）必须支持，别只按轴对齐的正方形写；边界算不算「存在其他建筑」——题目明确写了「内部和边上都不能有」，所以叉积为零（共线且在边上）要判为非法，不能只判断严格内部。最后注意四个端点本身是允许的，遍历时要跳过这四个点。