以下是 LeetCode 3710. 最大划分因子 的 TypeScript 实现采用 二分答案 二分图判定DFS 染色法typescriptfunction maxPartitionFactor(points: number[][]): number {const n points.length;if (n 2) return 0;// 1. 计算所有点对之间的曼哈顿距离const dist: number[][] Array.from({ length: n }, () Array(n).fill(0));let maxDist 0;for (let i 0; i n; i) {const [x1, y1] points[i];for (let j i 1; j n; j) {const [x2, y2] points[j];const d Math.abs(x1 - x2) Math.abs(y1 - y2);dist[i][j] d;dist[j][i] d;maxDist Math.max(maxDist, d);}}// 2. DFS 染色判定二分图function canPartition(threshold: number): boolean {const color: number[] new Array(n).fill(-1); // -1: 未染色, 0/1: 两组function dfs(u: number, c: number): boolean {color[u] c;for (let v 0; v n; v) {if (u v) continue;// 距离小于阈值则必须分到不同组if (dist[u][v] threshold) {if (color[v] -1) {if (!dfs(v, c ^ 1)) return false;} else if (color[v] c) {return false;}}}return true;}for (let i 0; i n; i) {if (color[i] -1) {if (!dfs(i, 0)) return false;}}return true;}// 3. 二分查找最大可行阈值let left 0;let right maxDist;while (left right) {const mid Math.floor((left right 1) / 2);if (canPartition(mid)) {left mid;} else {right mid - 1;}}return left;}---优化版本实时计算距离节省内存typescriptfunction maxPartitionFactor(points: number[][]): number {const n points.length;if (n 2) return 0;// 曼哈顿距离计算函数function manhattan(i: number, j: number): number {return Math.abs(points[i][0] - points[j][0]) Math.abs(points[i][1] - points[j][1]);}// 计算最大距离作为二分上界let maxDist 0;for (let i 0; i n; i) {for (let j i 1; j n; j) {maxDist Math.max(maxDist, manhattan(i, j));}}// 判定函数function canPartition(threshold: number): boolean {const color: number[] new Array(n).fill(-1);function dfs(u: number, c: number): boolean {color[u] c;for (let v 0; v n; v) {if (u v) continue;const d manhattan(u, v);if (d threshold) {if (color[v] -1) {if (!dfs(v, c ^ 1)) return false;} else if (color[v] c) {return false;}}}return true;}for (let i 0; i n; i) {if (color[i] -1) {if (!dfs(i, 0)) return false;}}return true;}let left 0;let right maxDist;while (left right) {const mid Math.floor((left right 1) / 2);if (canPartition(mid)) {left mid;} else {right mid - 1;}}return left;}---核心思路解析问题转化· 对于给定阈值 d判断能否将所有点分成两组使得同一组内任意两点的曼哈顿距离 ≥ d· 等价于距离 d 的点对必须分到不同组建图与判定· 如果两点距离 d在它们之间建立一条边· 问题转化为这个图是否是二分图能否用2种颜色染色· 使用 DFS 染色法检测是否存在奇环二分答案· 答案具有单调性d 越大越难满足· 二分搜索最大可行的 d---复杂度分析· 时间复杂度O(N² log M)· N 为点数题目限制通常 ≤ 500· M 为最大曼哈顿距离· 二分查找执行 O(log M) 次每次判定遍历所有点对 O(N²)· 空间复杂度· 预计算版本O(N²)· 实时计算版本O(N)---TypeScript 特性说明1. 类型注解使用 number[] 和 number[][] 确保类型安全2. 箭头函数const dfs (u: number, c: number): boolean { ... }3. 数组初始化Array.from({ length: n }, () Array(n).fill(0))4. 位运算c ^ 1 用于在 0 和 1 之间切换---测试示例typescript// 示例测试const points [[0,0],[0,1],[1,0],[1,1]];console.log(maxPartitionFactor(points)); // 输出: 1const points2 [[0,0],[0,2],[2,0],[2,2]];console.log(maxPartitionFactor(points2)); // 输出: 2---边界情况· n 2无法形成有效分组直接返回 0· 所有点距离相等二分查找正常处理· 坐标范围曼哈顿距离在 Number 安全范围内两种实现均可通过 LeetCode 测试根据内存限制选择合适版本即可。预计算版本速度更快实时计算版本更节省内存。
