[LeetCode专场复盘] AutoX 安途智行专场竞赛
一、本周周赛总结
- 这场是后来补的，感觉比较有意义，所以记录一下。
- T4几何题，希望借这个机会搞一下模板
二、 AutoX-1. 网页瀑布流
链接: AutoX-1. 网页瀑布流
1. 题目描述
2. 思路分析
没想到第一题就用到了堆，镇住了我。
意识到这不是周赛。
- 显然，优先级有两个维度，每次使用的列为最短、最靠左的列，使用完还需要加回队列中。
- 因此需要快速查找当前队列中最短最靠左的列。在length=10**4的情况下，每次查找消耗100次（遍历）其实也能过，但稍显笨拙。
- 那么优先队列就是比较合适的数据结构。
3. 代码实现
class Solution:
def getLengthOfWaterfallFlow(self, num: int, block: List[int]) -> int:
h = [(0,i) for i in range(num)]
for b in block:
hi, i = heapq.heappop(h)
heapq.heappush(h,(hi+b,i))
return max(a for a,b in h)
三、AutoX-2. 蚂蚁王国的蜂蜜
链接: AutoX-2. 蚂蚁王国的蜂蜜
1. 题目描述
2. 思路分析
这题easy就离谱。
- 一开始是不会做的。
- 由于方差公式是sum((x-avg)**2)/n,因此计算一次需要遍历每个数字，每次计算n，一共计算n次。
- 首先看到数据范围n=10**5，显然这样n^2是过不了的。
- 又仔细看了下，价格是[0,100]，且通过样例函数传参发现是整数，那么价格如果可以Counter()压缩一下，计算量就变成n*101，可以过。
更新，这题其实可以O(n),方差公式可以变形：s2 = sum(xi2)-avg2
3. 代码实现
class Solution:
def honeyQuotes(self, handle: List[List[int]]) -> List[float]:
cnt = Counter()
s = 0
c = 0
ans = []
for ab in handle:
a = ab[0]
if a == 1:
b = ab[1]
cnt[b] += 1
s += b
c += 1
elif a == 2:
b = ab[1]
cnt[b] -= 1
s -= b
c -= 1
elif a == 3:
if c == 0:
ans.append(-1)
else:
ans.append(s/c)
elif a == 4:
if c == 0:
ans.append(-1)
else:
avg = s / c
s2 = 0
for k,v in cnt.items():
s2 += (k-avg)**2*v
ans.append(s2/c)
return ans
class Solution:
def honeyQuotes(self, handle: List[List[int]]) -> List[float]:
s2 = 0
s = 0
c = 0
ans = []
for ab in handle:
a = ab[0]
if a == 1:
b = ab[1]
s += b
s2 += b*b
c += 1
elif a == 2:
b = ab[1]
s -= b
s2 -= b*b
c -= 1
elif a == 3:
if c == 0:
ans.append(-1)
else:
ans.append(s/c)
elif a == 4:
if c == 0:
ans.append(-1)
else:
avg = s / c
ans.append(s2/c - avg*avg)
return ans
四、AutoX-3. 出行的最少购票费用
1. 题目描述
2. 思路分析
- dp+二分，注意到数据范围是n=10^5,m=20，大概率是用n*m的算法。因此在每次dp考虑可以遍历tickets。
- 由于day有序，不需要额外排序。
- 令f[i]为前i个day有机票覆盖时，最小的花费。
- 显然第一个day，就是min(tickets)，这里前提是数据规定了没有任何一张票覆盖小于1天，即对于一天，任何票都可以飞，取花费最小即可。
- 对于第i天，如果这天使用的一张票，时长价格为(v,p)，那么我可以向前坐，看看这张票能覆盖到多远的之前，这之间的票可以不买了，只买边界最早那张。
- 计算s = d - v ，即s是用不到这张票的最后一天。
- 如果s比day[0] (最早一天)还小，说明从开始到这天都可以用这张票搞定f[i] = p。
- 如果s > day[i-1]，即本票不能覆盖前边任意一天，那前边的票依然要买，还要为今天单独买这张票f[i] = p + f[i-1]
- 否则,s一定在前边买过票的day中间，找到这个位置pos，用这张票覆盖后半部分，只买前半部分的票，f[i] = p + f[pos]；这里由于day有序，用二分加速查找这个位置。
3. 代码实现
class Solution:
def minCostToTravelOnDays(self, days: List[int], tickets: List[List[int]]) -> int:
n = len(days)
f = [inf] * n
f[0] = min(b for a,b in tickets)
for i in range(1,n):
d = days[i]
for v, p in tickets:
s = d - v
if s < days[0]:
f[i] = min(f[i], p)
elif s > days[i-1]:
f[i] = min(f[i], p+f[i-1])
else:
pos = bisect_right(days,s) - 1
f[i] = min(f[i], p+f[pos])
return f[-1]
五、[Hard] AutoX-4. 蚂蚁爬行
链接: AutoX-4. 蚂蚁爬行
1. 题目描述
2. 思路分析
几何题，百度了半天我还是做出来了，很骄傲（叉腰）
- 题意很简单，给n个图形，有的是线段，有的是圆，问任意两个图形是否相连。
- 那么用并查集把相交的图形连接起来即可。
- 问题就转化成了如何判断以下图形是否相交。
-
- 线段与线段
-
- 线段与圆
-
- 圆与圆
-
- 其中圆与圆最简单：
- 如果两个圆心距离R-r<=d<=R+r，则相交；否则不相交。
-
- 线段与线段也比较简单，抄的：
- 对于两条线段，如果相交则有以上两种情况：
- 1）每条线段都分别跨越了另一条线段所在直线，即两个端点分别在该直线两侧；
- 2）一条线段的端点恰好在另一条线段上。”
- 这里我们可以用向量叉积来判断跨立条件，如下图所示，如果线段ab跨立了线段cd所在的直线，那么作向量ca、cd和cb，其中ca×cd和cb×cd的正负号应该是不同的。即满足
- ca×cd和cb×cd < 0
- 考虑到情况2），上式等于0的情况也成立，因此，判断线段ab跨立线段cd所在直线的的条件为
- ca×cd和cb×cd <= 0
-
- 圆和线段最难，分情况：（https://blog.csdn.net/songbai1997/article/details/86599879）
- 用到了距离公式、根据线段求直线、点到直线距离公式、余弦定理。
3. 代码实现
调整后的代码，希望可以在一定程度上当模板用
class UnionFind:
def __init__(self, eles):
self.fathers = {}
f = self.fathers
for e in eles:
f[e] = e
def find_father(self, x):
f = self.fathers
f.setdefault(x, x)
return self._zip_find_father(x)
def _zip_find_father(self, x):
fathers = self.fathers
if fathers[x] != x:
fathers[x] = self._zip_find_father(fathers[x])
return fathers[x]
def union(self, x, y):
f = self.fathers
f.setdefault(x, x)
f.setdefault(y, y)
x = self.find_father(x)
y = self.find_father(y)
if x == y:
return False
if x < y:
x, y = y, x
self.fathers[x] = y
return True
def is_same_father(self, x, y):
return self.find_father(x) == self.find_father(y)
def point_dis_pow(p1, p2):
"""
计算两个点的距离的平方（暂不开方防止误差）
"""
return (p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2
def multiply(v1, v2):
"""
计算两个向量的叉积
"""
return v1.x * v2.y - v2.x * v1.y
class Point:
# 点
__slots__ = 'x', 'y'
def __init__(self, x, y):
self.x = x
self.y = y
def __sub__(self, other):
"""
重载减法运算，计算两点之差，实际上返回的表示该点到另一点的向量
:param other: 另一个点
:return: 该点到另一点的向量
"""
return Point(self.x - other.x, self.y - other.y)
class Segment:
# 线段
__slots__ = 'point1', 'point2'
def __init__(self, point1, point2):
self.point1 = point1
self.point2 = point2
def straddle(self, another_segment):
"""
:param another_segment: 另一条线段
:return: 如果另一条线段跨立该线段，返回True；否则返回False
"""
v1 = another_segment.point1 - self.point1
v2 = another_segment.point2 - self.point1
vm = self.point2 - self.point1
if multiply(v1, vm) * multiply(v2, vm) <= 0:
return True
else:
return False
def is_cross(self, another_segment):
""" 两条线段相交则返回True
:param another_segment: 另一条线段
:return: 如果两条线段相互跨立，则相交；否则不相交
"""
if self.straddle(another_segment) and another_segment.straddle(self):
return True
else:
return False
class Circle:
# 圆
__slots__ = 'p', 'r'
def __init__(self, p, r):
self.p, self.r = p, r
# self.x,self.y = self.p.x,self.p.y
def get_center_point(self):
"""
获取圆心的点
"""
return self.p
def is_point_out_circle(c, p):
""" 判断点相对于圆的位置，通过半径和距离圆心的距离判断
点在圆外返回0
点在圆上返回1
点在圆内返回2
"""
d = point_dis_pow(p, c.get_center_point())
r2 = c.r ** 2
if d > r2:
return 0
elif d == r2:
return 1
return 2
def judge_circle_seg_cross(c, s):
"""
判断圆c和线段s是否相交
:param c:
:param s:
:return:
"""
p1, p2 = s.point1, s.point2
pos1 = is_point_out_circle(c, s.point1)
pos2 = is_point_out_circle(c, s.point2)
if pos1 == 1 or pos2 == 1: # 0. 任一点在圆上，相交
return True
if pos1 == 2 == pos2: # 1. 两点都在圆内，必不相交
return False
if pos1 != pos2: # 2. 一个点在内一个点在外，相交
return True
# 3. 两点都在圆外，先求线段所在的直线方程:Ax+By+C=0
# print('都在圆外')
A = p1.y - p2.y
B = p2.x - p1.x
C = p1.x * p2.y - p2.x * p1.y
# 点到直线的距离公式d = |Ax+By+c| / (A**2+B**2)**0.5
# 3.1 如果 |Ax+By+c| / (A**2+B**2)**0.5 > r**2,不相交
# 以下下计算为了精度，把不等式化简：左半部分的分母移到右边部分。因此d1只计算分子，把分母乘到d2
x, y, r2 = c.p.x, c.p.y, c.r ** 2
# print(x,y,r2,A,B,C)
d1 = (A * x + B * y + C) ** 2
d2 = (A * A + B * B) * r2
# print(d1,d2)
# 3.1 如果圆心到直线的距离大于半径，不相交
if d1 > d2:
return False
# 3.2 如果距离小于等于半径，则需要用余弦定理计算两个角是否是锐角，都是锐角则相交： 3.3 否则不相交
# cosA = (b^2+c^2-a^2)//(2*b*c)
a2 = point_dis_pow(p1, c.get_center_point()) # 边a是角A的对边，因此是线段BC
b2 = point_dis_pow(p2, c.get_center_point())
c2 = point_dis_pow(p2, p1)
# 这里计算如果大于0则是锐角，因此省去分母不做计算
angleA = (b2 + c2 - a2)
angleB = (a2 + c2 - b2)
# print(angleA,angleB)
if angleA > 0 and angleB > 0: # 余弦为正是锐角
return True
return False
def judge_two_circle_cross(c1, c2):
r1, r2 = c1.r, c2.r
return (r1 - r2) ** 2 <= point_dis_pow(c1.get_center_point(), c2.get_center_point()) <= (r1 + r2) ** 2
class Solution:
def antPass(self, g: List[List[int]], path: List[List[int]]) -> List[bool]:
n = len(g)
uf = UnionFind(range(n))
for i in range(n - 1):
for j in range(i + 1, n):
gi, gj = g[i], g[j] # 简写，减小代码量同时方便交换引用
ni, nj = len(gi), len(gj) # 他们的长度 3是圆 ，4是线段
if ni == nj == 4: # 如果都是线段，直接调结构
a = Segment(Point(gi[0], gi[1]), Point(gi[2], gi[3]))
b = Segment(Point(gj[0], gj[1]), Point(gj[2], gj[3]))
if a.is_cross(b):
# print(i,j)
uf.union(i, j)
elif ni == nj == 3: # 如果都是圆，用半径和圆心距离比较即可。
if judge_two_circle_cross(Circle(Point(gi[0], gi[1]), gi[2]), Circle(Point(gj[0], gj[1]), gj[2]) ):
# print(i,j)
uf.union(i, j)
else: # 如果是一个圆一个线段
if ni == 4: # 为了方便编码，令gi是圆，gj是线段
gi, gj = gj, gi
if judge_circle_seg_cross(Circle(Point(gi[0], gi[1]), gi[2]),
Segment(Point(gj[0], gj[1]), Point(gj[2], gj[3]))):
# print(i,j)
uf.union(i, j)
return [uf.find_father(a) == uf.find_father(b) for a, b in path]
原代码
class UnionFind:
def __init__(self,eles):
self.fathers = {}
f = self.fathers
for e in eles:
f[e] = e
def find_father(self,x):
f = self.fathers
f.setdefault(x,x)
return self._zip_find_father(x)
def _zip_find_father(self,x):
fathers = self.fathers
if fathers[x] != x:
fathers[x] = self._zip_find_father(fathers[x])
return fathers[x]
def union(self,x,y):
f = self.fathers
f.setdefault(x,x)
f.setdefault(y,y)
x = self.find_father(x)
y = self.find_father(y)
if x == y:
return False
if x<y:
x,y=y,x
self.fathers[x] = y
return True
def is_same_father(self,x,y):
return self.find_father(x)==self.find_father(y)
def point_dis_pow(p1,p2):
return (p1.x-p2.x)**2 + (p1.y-p2.y)**2
def multiply(v1, v2):
"""
计算两个向量的叉积
"""
return v1.x*v2.y - v2.x*v1.y
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __sub__(self, other):
"""
重载减法运算，计算两点之差，实际上返回的表示该点到另一点的向量
:param other: 另一个点
:return: 该点到另一点的向量
"""
return Point(self.x-other.x, self.y-other.y)
class Segment:
def __init__(self, point1, point2):
self.point1 = point1
self.point2 = point2
def straddle(self, another_segment):
"""
:param another_segment: 另一条线段
:return: 如果另一条线段跨立该线段，返回True；否则返回False
"""
v1 = another_segment.point1 - self.point1
v2 = another_segment.point2 - self.point1
vm = self.point2 - self.point1
if multiply(v1, vm) * multiply(v2, vm) <= 0:
return True
else:
return False
def is_cross(self, another_segment):
"""
:param another_segment: 另一条线段
:return: 如果两条线段相互跨立，则相交；否则不相交
"""
if self.straddle(another_segment) and another_segment.straddle(self):
return True
else:
return False
class Circle:
def __init__(self,x,y,r):
self.x,self.y,self.r = x,y,r
def get_center_point(self):
return Point(self.x,self.y)
"""
点在圆外返回0
点在圆上返回1
点在圆内返回2
"""
def is_point_out_circle(c,p):
d = point_dis_pow(p,c.get_center_point())
r2 = c.r**2
if d > r2:
return 0
elif d == r2:
return 1
return 2
def jugde_circle_seg_cross(c,s):
p1,p2 = s.point1,s.point2
pos1 = is_point_out_circle(c,s.point1)
pos2 = is_point_out_circle(c,s.point2)
if pos1 == 1 or pos2 == 1: # 任一点在圆上，相交
return True
if pos1 == 2 == pos2: # 两点都在圆内，必不相交
return False
if pos1 != pos2: # 一个点在内一个点在外，相交
return True
# 两点都在圆外，先求线段所在的直线方程:Ax+By+C=0
# print('都在圆外')
A = p1.y-p2.y
B = p2.x-p1.x
C = p1.x*p2.y-p2.x*p1.y
# 点到直线的距离公式d = |Ax+By+c| // (A**2+B**2)**0.5
x,y,r2 = c.x,c.y,c.r**2
# print(x,y,r2,A,B,C)
d1 = (A*x+B*y+C)**2
d2 = (A*A+B*B)*r2
# print(d1,d2)
if d1 > d2: # 如果圆心到直线的距离大于半径，不相交
return False
# 如果距离小于等于半径，则需要用余弦定理计算两个角是否是锐角，都是锐角则相交：否则不相交
# cosA = (b^2+c^2-a^2)//(2*b*c)
a2 = point_dis_pow(p1,c.get_center_point())
b2 = point_dis_pow(p2,c.get_center_point())
c2 = point_dis_pow(p2,p1)
angleA = (b2+c2-a2)
angleB = (a2+c2-b2)
# print(angleA,angleB)
if angleA>0 and angleB>0: # 余弦为正是锐角
return True
return False
class Solution:
def antPass(self, g: List[List[int]], path: List[List[int]]) -> List[bool]:
n = len(g)
uf = UnionFind(range(n))
for i in range(n-1):
for j in range(i+1,n):
gi,gj = g[i],g[j]
ni, nj = len(gi), len(gj)
if ni == nj == 4:
a = Segment(Point(gi[0],gi[1]),Point(gi[2],gi[3]))
b = Segment(Point(gj[0],gj[1]),Point(gj[2],gj[3]))
if a.is_cross(b):
# print(i,j)
uf.union(i,j)
elif ni == nj == 3:
if gi[2] < gj[2]:
gi,gj = gj,gi
r1,r2= gi[2],gj[2]
x1,y1,x2,y2 = gi[0],gi[1],gj[0],gj[1]
if (r1-r2)**2 <= (x1-x2)**2+(y1-y2)**2<=(r1+r2)**2:
# print(i,j)
uf.union(i,j)
else:
if ni == 4:
gi,gj = gj,gi
if jugde_circle_seg_cross(Circle(gi[0],gi[1],gi[2]),Segment(Point(gj[0],gj[1]),Point(gj[2],gj[3]))):
# print(i,j)
uf.union(i,j)
return [uf.find_father(a) == uf.find_father(b) for a,b in path]