广东做网站的公司有哪些,广东vs北控直播,东莞专业网站建站设计,电商网站怎么做聚合题目
有一个大型的 (m - 1) x (n - 1) 矩形田地#xff0c;其两个对角分别是 (1, 1) 和 (m, n) #xff0c;田地内部有一些水平栅栏和垂直栅栏#xff0c;分别由数组 hFences 和 vFences 给出。
水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)#xff0c;垂直栅栏为… 题目
有一个大型的 (m - 1) x (n - 1) 矩形田地其两个对角分别是 (1, 1) 和 (m, n) 田地内部有一些水平栅栏和垂直栅栏分别由数组 hFences 和 vFences 给出。
水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。
返回通过 移除 一些栅栏可能不移除所能形成的最大面积的 正方形 田地的面积或者如果无法形成正方形田地则返回 -1。
由于答案可能很大所以请返回结果对 109 7 取余 后的值。
注意田地外围两个水平栅栏坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) 以及两个垂直栅栏坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) 所包围。这些栅栏 不能 被移除。 示例 1 输入m 4, n 3, hFences [2,3], vFences [2]
输出4
解释移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。示例 2 输入m 6, n 7, hFences [2], vFences [4]
输出-1
解释可以证明无法通过移除栅栏形成正方形田地。提示
3 m, n 1091 hFences.length, vFences.length 6001 hFences[i] m1 vFences[i] nhFences 和 vFences 中的元素是唯一的。 Problem: https://leetcode.cn/problems/maximum-squar100169 e-area-by-removing-fences-from-a-field/description/ [TOC]
思路 遍历所有的横向栏杆与纵向栏杆算出横向栏杆之间的差和纵向栏杆之间的差并存储两个集合最终的答案就是两个集合的交集的平方 复杂度
时间复杂度: O(m^2n^2) 空间复杂度: O(mn) Code
class Solution:def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) - int:ans -1hFences.append(m)hFences.insert(0,1)row set()for i in range(len(hFences)):for j in range(0,i):row.add(abs( hFences[i] - hFences[j] ))vFences.append(n)vFences.insert(0,1)col set()for i in range(len(vFences)):for j in range(0,i):col.add(abs(vFences[i] - vFences[j]))if abs(vFences[i] - vFences[j]) in row :ans max(ans,pow(abs(vFences[i] - vFences[j]),2))for val in row:if val in col:ans max(ans,pow(val,2))return ans % 1_000_000_007 if
