欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[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

[Leetcode]第197场周赛

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

[Leetcode]第197场周赛

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

[Leetcode]第197场周赛

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

[Leetcode]第197场周赛

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