Learn-Algorithms 面试题拾遗：几何相交与排列组合类算法题全解析-平芜编程栈

教程

【免费下载链接】Learn-Algorithms

算法学习笔记

项目地址：https://gitcode.com/gh_mirrors/le/Learn-Algorithms

本文基于《Learn-Algorithms》仓库中 97 其他.md 整理的五类高频笔试题展开：两圆相交最长弦的几何极值、四点判定矩形、全排列生成及其带约束去重变体、圆与正方形相交判定。每道题均从数学分析出发，落到可运行的参考代码，并交叉引用仓库内字符串排列分析、DFS/BFS 遍历框架与面试解题套路作为印证。读完本文，你将掌握：全排列类问题的"图遍历 + 回溯 + 剪枝 + 去重"四步套路，以及几何相交类问题"降维 + 距离比较 + 特例边界"的通用解法，可直接应对同类面试题。

题目一：两个圆相交，过交点 A1 的直线何时截得最长弦 B1B2

原题描述：两个圆相交，交点为 A1、A2。过 A1 点作一条直线，分别与两个圆再相交于另一点 B1、B2。直线 B1B2 可绕 A1 点旋转。问：在什么情况下，B1B2 最长？

分析：这是几何 + 函数极值问题，关键在于把"任意旋转直线"这个自由度转化成可用一元函数描述的变量。

固定一个圆，弦长只取决于方向。对圆 O₁，过定点 A1 的弦 A1B1 的长度 L₁ 由直线方向角 θ 唯一决定。设圆 O₁ 半径 R₁，圆心到直线（过 A1）的垂直距离为 d₁(θ)，则弦长公式为： L₁ = 2·√(R₁² − d₁²(θ)) 当直线方向与 O₁A1 方向垂直时，d₁ = 0，L₁ = 2R₁ 取最大（此时 A1B1 恰为直径）。
两圆叠加：B1B2 = A1B1 + A1B2（当 B1、B2 在 A1 异侧时相加；同侧时是相减，显然不优），即 L(θ) = L₁(θ) + L₂(θ)。
极值位置：由于每个圆在"直线 ⊥ 圆心连线方向"时取得各自最大弦长，直觉上最优方向位于使两条弦都接近各自直径的方向附近。严格的证明思路是：以 A1 为原点、A1A2 为极轴建立极坐标系，把 L(θ) 写成 θ 的表达式后求导找驻点；当两圆半径与圆心距满足一定关系时，最长弦出现在某条特定的过 A1 直线上。
面试回答要点：先指出单圆弦长公式与极值条件，再说明总弦长是两个单圆弦长之和，最终方向与两圆半径及 A1 位置相关，可在该方向求导得驻点。本题考察的是把几何问题代数化的能力，不必死记结论，讲清"降维到直线方向 θ"这一分析过程即可得分。

题目二：输入四个点的坐标，求证四点是否构成矩形

原题描述：给定平面内任意四个点的坐标（输入顺序不定），判断它们能否构成一个矩形。

文档给出的关键点：

相邻两边斜率之积等于 −1（即两邻边垂直）；
矩形边与坐标系平行时，斜率无穷大，不能用斜率乘积判断；
输入四点可能不按顺序，需要先对四点排序。

完整解法（推荐：向量法，天然规避斜率无穷大）：

排序定序：先按 x（再按 y）对四点排序，得到左下、左上、右下、右上四个位置，从而确定四边形的顶点顺序；
向量判垂直：矩形等价于"两条对角线相等且互相平分"或"任意相邻两边点积为 0"。设排序后四点为 P1、P2、P3、P4，构造边向量 v1 = P2−P1、v2 = P3−P2、v3 = P4−P3、v4 = P1−P4，判断：
- v1 ⊥ v2（点积为 0）且 v2 ⊥ v3 且 v3 ⊥ v4 且 v4 ⊥ v1；
- 同时 v1 与 v3 长度相等、v2 与 v4 长度相等（对边相等）。
边界情况：所有边与坐标轴平行时，向量法仍成立（点积公式直接计算，不涉及斜率除法），这正是文档强调"斜率无穷大不能用乘积判断"的缘由——向量法是最稳妥的实现。

参考实现（C 语言伪代码）：

typedef struct { double x, y; } Point; int is_rectangle(Point p[4]) { // 1. 按 (x, y) 排序，确定顶点顺序 qsort(p, 4, sizeof(Point), cmp); // 2. 依次取出四边向量 Point v1 = {p[1].x - p[0].x, p[1].y - p[0].y}; Point v2 = {p[3].x - p[1].x, p[3].y - p[1].y}; Point v3 = {p[2].x - p[3].x, p[2].y - p[3].y}; Point v4 = {p[0].x - p[2].x, p[0].y - p[2].y}; // 3. 相邻边点积为 0（垂直） if (dot(v1, v2) != 0 || dot(v2, v3) != 0 || dot(v3, v4) != 0 || dot(v4, v1) != 0) return 0; // 4. 对边相等 return len2(v1) == len2(v3) && len2(v2) == len2(v4); }

浮点坐标建议改用"点积绝对值小于 ε"判断垂直，以容忍精度误差。此题的矩阵/二维坐标类题目还可参考仓库 6 矩阵.md 中的矩阵与二维数组处理思路。

题目三：1、2、3、4、5 五个不同数字的全排列

原题描述：用 1、2、3、4、5 五个互不相同的数字，打印出所有不同的排列（共 5! = 120 种）。

文档要点："这就是一个无向图的遍历，把每个数字看成一个节点。"

这是本题最关键的建模视角：把"数字序列"看成图上的路径——第 i 位选哪个数字，就是从当前位置走向哪个"数字节点"。于是全排列 = 从任意起点出发、不重复访问每个节点恰好一次的深度优先遍历（DFS）。

与 DFS 和 BFS 搜索算法中"DFS 用递归、走不通就回溯到上一步状态换条路走"的描述完全对应；
图遍历的"已访问标记"在排列问题中就是"used[] 数组"：used[i] = 1表示数字 i 已出现在当前前缀中，递归返回时置回 0（回溯）；
仓库面试题 README 中"图的递归：用一个布尔数组 visited 做标记就行了"正是这个套路的标准表述。

参考实现（C）：

#include <stdio.h> int a[] = {1, 2, 3, 4, 5}; int used[6] = {0}; int path[5]; int cnt; void permute(int pos) { int i; if (pos == 5) { // 5 位全部填满，输出一个排列 for (i = 0; i < 5; i++) printf("%d", path[i]); printf("\n"); cnt++; return; } for (i = 0; i < 5; i++) { if (used[a[i]]) continue; // 每个数字只能使用一次（图的 visited） used[a[i]] = 1; // 标记已访问 path[pos] = a[i]; // 当前位填入 permute(pos + 1); // 递归填下一位 used[a[i]] = 0; // 回溯：撤销标记 } } int main() { permute(0); printf("total = %d\n", cnt); // 输出 120 return 0; }

延伸：关于排列生成的其他算法，仓库 1 字符串.md 指出"排列的产生也有很多种算法，去看看组合数学，还有逆序生成排列和一些不需要递归生成排列的方法"，并提示 Knuth《TAOCP》第一卷深入讲解了排列的生成——递归回溯只是最直观的一种，字典序生成（next_permutation）与逆序生成可作为进阶方向。

题目四：用 1、2、2、3、4、5 六个数字打印所有不同排列（带约束）

原题描述：用 1、2、2、3、4、5 这六个数字，写一个 main 函数，打印出所有不同的排列（如 512234、412345 等），要求："4" 不能在第三位，"3" 与 "5" 不能相连。

文档给出的三个关键点：

去掉 3、5 之间的"联通"：即任一排列中 3 与 5 不能相邻，这是图论中"删边"的对应物——把"可相邻"看成节点间的连边，本题等价于在删除 (3,5) 边的图中做路径遍历；
2 重复，过滤重复结果（可用 TreeSet）：两个 2 视为同一节点，需要去重，避免同一排列被输出两次；
4 不能在第三位：在递归的第 3 层（pos == 2）直接剪枝，不填 4。

参考实现（C）：

#include <stdio.h> int nums[] = {1, 2, 2, 3, 4, 5}; int used[6] = {0}; int path[6]; int valid(int pos, int val) { if (pos == 2 && val == 4) return 0; // 约束1：4 不能在第3位 if (pos > 0 && path[pos-1] == 3 && val == 5) return 0; // 约束2：3 与 5 不能相连 if (pos > 0 && path[pos-1] == 5 && val == 3) return 0; return 1; } void permute(int pos) { int i, last = -1; if (pos == 6) { for (i = 0; i < 6; i++) printf("%d", path[i]); printf("\n"); return; } for (i = 0; i < 6; i++) { if (used[i]) continue; if (last == nums[i]) continue; // 去重：同层跳过重复数字（2 只取一次） if (!valid(pos, nums[i])) continue; // 剪枝：约束检查 used[i] = 1; path[pos] = nums[i]; last = nums[i]; permute(pos + 1); used[i] = 0; } } int main() { permute(0); return 0; }

要点讲解：

同层去重而非全局去重：先对 nums 排序，使相同数字相邻；递归中同一层（同一 pos）跳过与前一次相同值的数字，即可保证"不同排列"不重复输出。这正是文档提到的"TreeSet 过滤重复结果"在回溯框架中的高效等价实现；
剪枝时机：约束检查放在进入递归之前（前序遍历位置），比生成完整排列后再过滤快得多，体现了仓库 README.md 中"拿到题目以后能快速套思路和代码框架"的刷题思路；
数字间的"相连/不相连"用约束函数判断，等价于在 DFS/BFS 图遍历中的状态合法转移判断，是"删边后图遍历"模型的工程化落地。

关联阅读：字符串场景下的同类问题（输入 abcca 输出字符出现个数不变的所有排列）见 1 字符串.md 的"字符串的排列"一节；组合计数的数学背景可参考 9 智力思维训练.md 中 rand7() 构造 rand10() 的组合数分析方法（7×7=49 种等概率组合的枚举计数）。

题目五：圆形和正方形是否相交（3D 坐标系）

原题描述：在 3D 坐标系原点 (0.0, 0.0, 0.0)，给定一个圆：半径 r = 3.0，圆心 o = (., 0.0,.)；以及一个正方形的 4 个角坐标 (., 0.0,.) 等。用最简单、最快速的方法判断圆与正方形是否相交。

文档给出的分析："2 个形状不相交……"

完整分析：

降维：观察数据——圆心与正方形四个角的 y 坐标全部为 0.0。这意味着圆与正方形共面于 y=0 平面，3D 问题退化为 2D 问题。这是本题最核心的观察点：把 3D 判定投影到 xz 平面（去掉 y 维），复杂度从三维降到二维。
相交判定的通用法则：圆与矩形（正方形是特例）相交 ⇔ 圆心到矩形"最近点"的距离 ≤ r。关键在于求矩形区域到圆心的最近距离 d：
- 若圆心落在矩形内部，d = 0，必然相交；
- 否则 d = 圆心到矩形四条边线段的最短距离（点到线段距离取最小值）。
边界情形：d == r 视为相切（通常算作相交边界）；d > r 不相交。文档留下的"2 个形状不相交"正是指向 d > r 的情形。
"最简单最快速"的落点：y 坐标全为 0 直接消去一维；再用点到矩形（而非逐边）的最近点公式一次算完，避免分支判断，达到 O(1) 时间、O(1) 空间。

参考实现（C）：

#include <math.h> typedef struct { double x, y, z; } Point3D; double clamp(double v, double lo, double hi) { // 将 v 约束到 [lo, hi] return v < lo ? lo : (v > hi ? hi : v); } /* 判定圆心在 xz 平面投影是否在正方形内（正方形边与轴平行） */ int circle_intersects_square(Point3D c, double r, Point3D sq[4]) { double xmin, xmax, zmin, zmax; int i; /* 求正方形包围盒（边与坐标轴平行的情形） */ xmin = xmax = sq[0].x; zmin = zmax = sq[0].z; for (i = 1; i < 4; i++) { if (sq[i].x < xmin) xmin = sq[i].x; if (sq[i].x > xmax) xmax = sq[i].x; if (sq[i].z < zmin) zmin = sq[i].z; if (sq[i].z > zmax) zmax = sq[i].z; } /* 圆心到矩形的最近点（clamp 到矩形范围） */ double nx = clamp(c.x, xmin, xmax); double nz = clamp(c.z, zmin, zmax); double d = sqrt((c.x - nx) * (c.x - nx) + (c.z - nz) * (c.z - nz)); return d <= r; /* d <= r 相交（含相切） */ }

变体提醒：若正方形可绕轴旋转（非轴对齐），最近点不再是简单的 clamp，需分别计算圆心到四条边线段的距离取最小。面试时先问清"正方形是否轴对齐"，这正是本题"最简单最快速"的前提条件。

小结：五道题的通用解题套路

综合以上五题，可与仓库面试题 README 的"刷题框架套路"互相印证：

题型	核心模型	关键技术	对应仓库素材
两圆最长弦	函数极值	弦长公式 + 方向角降维求导	4 数值问题.md
四点判矩形	几何判定	排序定序 + 向量点积（规避斜率无穷大）	6 矩阵.md
无重复全排列	图遍历	DFS 递归 + used[] 回溯标记	DFS 和 BFS、1 字符串.md
带约束去重排列	图遍历 + 剪枝	同层去重 + 约束剪枝 + 删边模型	README.md
圆与正方形相交	降维 + 距离判定	3D→2D 投影 + 点到矩形最近距离	6 矩阵.md