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₁ 0L₁ 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; // 约束14 不能在第3位 if (pos 0 path[pos-1] 3 val 5) return 0; // 约束23 与 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×749 种等概率组合的枚举计数。题目五圆形和正方形是否相交3D 坐标系原题描述在 3D 坐标系原点 (0.0, 0.0, 0.0)给定一个圆半径 r 3.0圆心 o (., 0.0,.)以及一个正方形的 4 个角坐标 (., 0.0,.) 等。用最简单、最快速的方法判断圆与正方形是否相交。文档给出的分析2 个形状不相交……完整分析降维观察数据——圆心与正方形四个角的 y 坐标全部为 0.0。这意味着圆与正方形共面于 y0 平面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方法论提炼先找对称与降维机会圆与正方形共面 → 消去 y 维四点判矩形 → 排序定序再建图论/代数模型排列 图遍历垂直 向量点积为 0最后统一到递归 状态标记 剪枝 去重的代码框架上这正是 README.md 所强调的常见解题套路工具。仓库中 codes 目录收录了字符串、数值、数组、矩阵、二叉树等大量可直接编译运行的参考实现如 factorial.c、print_matrix.c本文五题的代码为结合文档思路给出的参考实现可在此基础上对照练习加深对回溯与几何判定的理解。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Learn-Algorithms 算法面试笔记矩阵与二维数组五类高频题的解法与源码解析Learn Algorithms 算法面试笔记矩阵与二维数组五类高频题的解法与源码解析 本篇文章以 6 矩阵.md 为核心骨架整理展开并以仓库源码 prin教程数值的整数次方与平方根Learn-Algorithms 指数类算法面试题全解数值的整数次方与平方根Learn Algorithms 指数类算法面试题全解 导读 在 Learn Algorithms https://link.gitco教程Learn-Algorithms 数列交并集面试题精讲集合交集、有序数组合并与双序列和差最小化Learn Algorithms 数列交并集面试题精讲集合交集、有序数组合并与双序列和差最小化 本文源自本仓库面试题笔记 5.3 数列 交并集.md http教程上一篇5分钟快速上手ImageToSTL图片转3D模型终极指南下一篇终极Outlook CalDav Synchronizer跨平台同步实战精通指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考