难度: Hard
Submission
运行时间: 1632 ms
内存: 17.0 MB
class Solution:
def minDayskVariants(self, points: List[List[int]], k: int) -> int:
# 映射到x轴和y轴是不对的
# 应该进行旋转
# 以最下面的点作为基准，顺时针旋转45℃
def pointMap(x,y):
return x - y,y + x
# 根据曼哈顿距离，判断点在多少个区域中
def getPointAreas(x,y,d):
t = 0
for a,b in points:
if abs(a-x)+abs(b-y) <= d:
t += 1
return t
# 求下面两直线交点
'''
(a,0) k = 1
y = x - a
(0,b) k = -1
y = -x + b
'''
# 判断是否为整数
def getCross(a,b,d):
# 交点就是整数
if (b-a) % 2 == 0:
return True
# 若不是整数，就取最近的四个整数点，用曼哈顿距离判断
y = (b - a) // 2
x = y + a
xc = [0,0,1,1]
yc = [0,1,0,1]
t = 0
for h in range(4):
nx = x + xc[h]
ny = y + yc[h]
t = max(t,getPointAreas(nx,ny,d))
return t >= k
# d天后
def check(D):
rows = set()
cols = set()
xc = [0,-1,0,1]
yc = [-1,0,1,0]
# 存储映射后的矩形边界
pMap = []
for x,y in points:
tmpx = set()
tmpy = set()
for h in range(4):
nx = x + xc[h] * D
ny = y + yc[h] * D
nx,ny = pointMap(nx,ny)
rows.add(nx)
cols.add(ny)
tmpx.add(nx)
tmpy.add(ny)
l,r = sorted(list(tmpx))
pMap.append([l,r])
l,r = sorted(list(tmpy))
pMap[-1].append(l)
pMap[-1].append(r)
# 离散化
rows = sorted(list(rows))
cols = sorted(list(cols))
# 记录离散化后每个位置的覆盖数目
t = [[0] * len(cols) for _ in range(len(rows))]
# 遍历映射后的边界
for x1,x2,y1,y2 in pMap:
# 二分查找离散化后的位置
l = bisect_left(rows,x1)
r = bisect_right(rows,x2)
d = bisect_left(cols,y1)
u = bisect_right(cols,y2)
# 覆盖位置全+1
for i in range(l,r):
for j in range(d,u):
t[i][j] += 1
# 验证是否有点大于等于k
for i in range(len(rows)):
for j in range(len(cols)):
if t[i][j] >= k and getCross(rows[i],cols[j],D):
# 交点可能不是整数，需要计算出交点
return True
return False
cnt = Counter()
for x,y in points:
cnt[(x,y)] += 1
# 因为点可以重复，若最多重复位置满足k，那就一天都不用就满足了
if cnt.most_common(1)[0][1] >= k:
return 0
# 二分结果
start = 1
end = int(1e15)
while start <= end:
middle = (start + end) // 2
if not check(middle):
start = middle + 1
else:
end = middle - 1
return start
Explain
题解使用了二分搜索方法寻找满足至少k个病毒种类在D天内可以覆盖一个区域的最短时间。关键步骤包括：1. 通过旋转坐标系来更合理地处理问题中的曼哈顿距离；2. 二分搜索天数D，检查在D天内是否存在一个点能被至少k个点覆盖；3. 使用离散化处理潜在的覆盖区域，避免直接在连续的坐标空间中操作，减少计算量；4. 使用复杂的边界和覆盖检查逻辑来验证每个点的覆盖情况。核心逻辑包括点的旋转映射、区域覆盖计算、以及对所有可能的区域执行覆盖点数的验证。
时间复杂度: O(log(MaxD) * n * m^2)
空间复杂度: O(m * n)
class Solution:
def minDayskVariants(self, points: List[List[int]], k: int) -> int:
# 旋转坐标点，以适应曼哈顿距离的计算
def pointMap(x,y):
return x - y, y + x
# 根据曼哈顿距离，计算点(x, y)能覆盖的区域数量
def getPointAreas(x, y, d):
t = 0
for a, b in points:
if abs(a-x) + abs(b-y) <= d:
t += 1
return t
# 计算可能的交点是否能满足整数条件，或其附近点的覆盖情况
def getCross(a, b, d):
y = (b - a) // 2
x = y + a
xc = [0, 0, 1, 1]
yc = [0, 1, 0, 1]
t = 0
for h in range(4):
nx = x + xc[h]
ny = y + yc[h]
t = max(t, getPointAreas(nx, ny, d))
return t >= k
# 检查D天内是否有满足条件的覆盖点
def check(D):
rows, cols = set(), set()
pMap = []
for x, y in points:
tmpx, tmpy = set(), set()
for h in range(4):
nx, ny = pointMap(x + xc[h] * D, y + yc[h] * D)
rows.add(nx)
cols.add(ny)
tmpx.add(nx)
tmpy.add(ny)
l, r = sorted(list(tmpx))
pMap.append([l, r])
l, r = sorted(list(tmpy))
pMap[-1].extend([l, r])
rows, cols = sorted(list(rows)), sorted(list(cols))
t = [[0] * len(cols) for _ in range(len(rows))]
for x1, x2, y1, y2 in pMap:
l, r = bisect_left(rows, x1), bisect_right(rows, x2)
d, u = bisect_left(cols, y1), bisect_right(cols, y2)
for i in range(l, r):
for j in range(d, u):
t[i][j] += 1
for i in range(len(rows)):
for j in range(len(cols)):
if t[i][j] >= k and getCross(rows[i], cols[j], D):
return True
return False
cnt = Counter()
for x, y in points:
cnt[(x, y)] += 1
if cnt.most_common(1)[0][1] >= k:
return 0
start, end = 1, int(1e15)
while start <= end:
middle = (start + end) // 2
if not check(middle):
start = middle + 1
else:
end = middle - 1
return start
Explore
在算法中进行坐标点的旋转映射（例如通过变换 x-y 和 y+x），主要是为了简化曼哈顿距离的计算。曼哈顿距离要求计算两点间在各个坐标方向上的距离总和。通过这种映射，原本形成的菱形（曼哈顿距离的等距线）被转换为正方形或矩形，这使得对于距离的处理、区域的覆盖判断以及算法中的搜索和优化步骤变得更为直观和简单。
选择曼哈顿距离而不是欧几里得距离可能是基于具体问题的设定或者简化计算的需要。曼哈顿距离（各坐标值之差的绝对值之和）在某些情况下更适合描述某些场景下的实际距离，如城市中的街区距离。此外，曼哈顿距离在计算和实现上通常比欧几里得距离更为简单，特别是在涉及到优化和算法复杂度时更有优势。
在二分搜索中确定搜索范围的最大值MaxD通常基于问题的上下文和输入数据的特点。一个通用的方法是考虑极端情况，例如所有点都位于一个坐标的最远距离，或者计算使得所有点至少被覆盖一次所需的最大距离。在许多情况下，可以设置一个较大的数，如1e15，这个数足够大以包括所有合理的情况，然后通过二分搜索逐步缩小实际需要的范围。
离散化处理坐标点是为了简化问题和减少计算量。在许多算法中，特别是涉及到空间覆盖或区域搜索的场景中，直接使用原始坐标可能会导致处理大量稀疏数据和不必要的计算复杂度。离散化可以将连续的坐标转换为有限的、较小的离散集合，从而优化存储和计算，提高算法的效率和执行速度。这种方法在处理大规模数据或需要频繁查询和更新操作的场景中尤为有用。