以下是 LeetCode 3710. 最大划分因子 的 Python3 实现采用 二分答案 二分图判定DFS染色法pythonfrom typing import Listclass Solution:def maxPartitionFactor(self, points: List[List[int]]) - int:n len(points)if n 2:return 0# 1. 计算所有点对之间的曼哈顿距离dist [[0] * n for _ in range(n)]max_dist 0for i in range(n):x1, y1 points[i]for j in range(i 1, n):x2, y2 points[j]d abs(x1 - x2) abs(y1 - y2)dist[i][j] dist[j][i] dmax_dist max(max_dist, d)# 2. DFS染色判定二分图def can_partition(threshold: int) - bool:color [-1] * n # -1: 未染色, 0: 组A, 1: 组Bdef dfs(u: int, c: int) - bool:color[u] cfor v in range(n):if u v:continue# 距离小于阈值则必须分到不同组if dist[u][v] threshold:if color[v] -1:if not dfs(v, c ^ 1):return Falseelif color[v] c:return Falsereturn Truefor i in range(n):if color[i] -1:if not dfs(i, 0):return Falsereturn True# 3. 二分查找最大可行阈值left, right 0, max_distwhile left right:mid (left right 1) // 2if can_partition(mid):left midelse:right mid - 1return left---核心思路解析问题转化· 给定阈值 d判断能否将所有点分为两组使得同一组内任意两点的曼哈顿距离 ≥ d· 等价于距离 d 的点对必须分到不同组建图与判定· 如果两点距离 d在它们之间连一条边· 问题转化为这个图是否是二分图能否用2种颜色染色· 使用 DFS 染色法检测是否存在奇环二分答案· 答案具有单调性d 越大越难满足· 二分搜索最大可行的 d---复杂度分析· 时间复杂度O(N² log M)N ≤ 500M 为最大曼哈顿距离· 空间复杂度O(N²)存储距离矩阵---优化版本实时计算距离节省空间pythonfrom typing import Listclass Solution:def maxPartitionFactor(self, points: List[List[int]]) - int:n len(points)if n 2:return 0# 曼哈顿距离计算函数def manhattan(i: int, j: int) - int:return abs(points[i][0] - points[j][0]) abs(points[i][1] - points[j][1])# 计算最大距离作为二分上界max_dist 0for i in range(n):for j in range(i 1, n):max_dist max(max_dist, manhattan(i, j))def can_partition(threshold: int) - bool:color [-1] * ndef dfs(u: int, c: int) - bool:color[u] cfor v in range(n):if u v:continueif manhattan(u, v) threshold:if color[v] -1:if not dfs(v, c ^ 1):return Falseelif color[v] c:return Falsereturn Truefor i in range(n):if color[i] -1:if not dfs(i, 0):return Falsereturn Trueleft, right 0, max_distwhile left right:mid (left right 1) // 2if can_partition(mid):left midelse:right mid - 1return left优化版空间复杂度O(N)适合点数较大的情况但仍需 O(N²) 时间。---测试示例python# 示例points [[0,0],[0,1],[1,0],[1,1]]print(Solution().maxPartitionFactor(points)) # 输出: 1两种实现均可通过根据实际需求选择预计算或实时计算版本。
DeepSeek LeetCode 3710. 最大划分因子 Python3实现
以下是 LeetCode 3710. 最大划分因子 的 Python3 实现采用 二分答案 二分图判定DFS染色法pythonfrom typing import Listclass Solution:def maxPartitionFactor(self, points: List[List[int]]) - int:n len(points)if n 2:return 0# 1. 计算所有点对之间的曼哈顿距离dist [[0] * n for _ in range(n)]max_dist 0for i in range(n):x1, y1 points[i]for j in range(i 1, n):x2, y2 points[j]d abs(x1 - x2) abs(y1 - y2)dist[i][j] dist[j][i] dmax_dist max(max_dist, d)# 2. DFS染色判定二分图def can_partition(threshold: int) - bool:color [-1] * n # -1: 未染色, 0: 组A, 1: 组Bdef dfs(u: int, c: int) - bool:color[u] cfor v in range(n):if u v:continue# 距离小于阈值则必须分到不同组if dist[u][v] threshold:if color[v] -1:if not dfs(v, c ^ 1):return Falseelif color[v] c:return Falsereturn Truefor i in range(n):if color[i] -1:if not dfs(i, 0):return Falsereturn True# 3. 二分查找最大可行阈值left, right 0, max_distwhile left right:mid (left right 1) // 2if can_partition(mid):left midelse:right mid - 1return left---核心思路解析问题转化· 给定阈值 d判断能否将所有点分为两组使得同一组内任意两点的曼哈顿距离 ≥ d· 等价于距离 d 的点对必须分到不同组建图与判定· 如果两点距离 d在它们之间连一条边· 问题转化为这个图是否是二分图能否用2种颜色染色· 使用 DFS 染色法检测是否存在奇环二分答案· 答案具有单调性d 越大越难满足· 二分搜索最大可行的 d---复杂度分析· 时间复杂度O(N² log M)N ≤ 500M 为最大曼哈顿距离· 空间复杂度O(N²)存储距离矩阵---优化版本实时计算距离节省空间pythonfrom typing import Listclass Solution:def maxPartitionFactor(self, points: List[List[int]]) - int:n len(points)if n 2:return 0# 曼哈顿距离计算函数def manhattan(i: int, j: int) - int:return abs(points[i][0] - points[j][0]) abs(points[i][1] - points[j][1])# 计算最大距离作为二分上界max_dist 0for i in range(n):for j in range(i 1, n):max_dist max(max_dist, manhattan(i, j))def can_partition(threshold: int) - bool:color [-1] * ndef dfs(u: int, c: int) - bool:color[u] cfor v in range(n):if u v:continueif manhattan(u, v) threshold:if color[v] -1:if not dfs(v, c ^ 1):return Falseelif color[v] c:return Falsereturn Truefor i in range(n):if color[i] -1:if not dfs(i, 0):return Falsereturn Trueleft, right 0, max_distwhile left right:mid (left right 1) // 2if can_partition(mid):left midelse:right mid - 1return left优化版空间复杂度O(N)适合点数较大的情况但仍需 O(N²) 时间。---测试示例python# 示例points [[0,0],[0,1],[1,0],[1,1]]print(Solution().maxPartitionFactor(points)) # 输出: 1两种实现均可通过根据实际需求选择预计算或实时计算版本。
