[Leetcode]第197场周赛

第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