[Leetcode]第197场周赛
程序员文章站
2022-06-11 17:45:19
第197场周比赛入口 https://leetcode-cn.com/contest/weekly-contest-197/Number of Good Pairsfrom collections import Counter as Cclass Solution: def numIdenticalPairs(self, nums): def f(x): return x*(x-1) // 2 return sum(map(f, [n for a, n in...
第197场周
比赛入口 https://leetcode-cn.com/contest/weekly-contest-197/
Number of Good Pairs
from collections import Counter as C
class Solution:
def numIdenticalPairs(self, nums):
def f(x): return x*(x-1) // 2
return sum(map(f, [n for a, n in C(nums).items()]))
Number of Substrings With Only 1s
class Solution:
def numSub(self, s: str) -> int:
mod, cnt, A = 10**9+7, 0, []
def f(x): return (x+1)*x // 2
for x in s:
if x == '0':
if cnt > 0:
A.append(cnt)
cnt = 0
else:
cnt +=1
A.append(cnt)
ret = 0
for x in A:
ret = ret + f(x) % mod
return ret
Path with Maximum Probability
class Solution:
def maxProbability(self, n: int, edges, succProb, start: int, end: int):
ret = 0
graph = collections.defaultdict(list)
for x, y in zip(edges, succProb):
a, b = x
graph[a].append((b, y))
graph[b].append((a,y))
A= [(-1.0, start)]
vis = [False]*n
while A:
p,x = heapq.heappop(A)
if vis[x]:
continue
vis[x] = True
if x == end:
return -p
for y, py in graph[x]:
pp = p*py
if not vis[y]:
heapq.heappush(A, (pp, y))
return 0
Best Position for a Service Centre
from math import sqrt
class Solution:
def getMinDistSum(self, A: List[List[int]]) -> float:
ret = 0
n = len(A)
def f(i,j):
d = 0
for x,y in A:
d += sqrt((x - i)**2 + (y - j)**2)
return d
P = sorted([ (i,j) for i in range(101) for j in range(101)], key=lambda x: f(x[0], x[1]))
gx,gy = P[0]
eps = 1e-9
step = 100
ret = f(gx,gy)
dx,dy = [1,-1,0,0], [0,0,1,-1]
while step > eps:
found = False
for i in range(4):
nx,ny = dx[i]*step+gx, gy+dy[i]*step
if f(nx,ny) < ret:
found = True
ret = f(nx,ny)
gx,gy = nx,ny
if not found:
step /= 2
return ret
本文地址:https://blog.csdn.net/weixin_42227482/article/details/107335448
上一篇: 苏州特色美食,到了苏州必须吃这些