微软 0813笔试 python
py选手分享一下，测试用例都过了。。。
第一题：优先队列(堆)，每次只对堆顶进行操作：
def solution1(A: list)-> int: target = sum(A)/2 n = len(A) pq = PriorityQueue(n) for it in A: pq.put(-it) ans = 0 tmp = 0 while tmp<target: cur = pq.get()/2 tmp -= cur pq.put(cur) ans += 1 return ans
第二题：gcd + 哈希表
def simpleFraction(a: int, b: int): g = gcd(a, b) return a//g, b//g def solution2(X: list, Y: list)->int: from collections import defaultdict MOD = 10**9+7 d = defaultdict(int) for a, b in zip(X, Y): a, b = simpleFraction(a, b) d[(a, b)] += 1 ans = 0 vis = set() for (fir, sec), val in d.items(): if (fir, sec) in vis: continue if fir==sec-fir: ans += (val*(val-1)//2)%MOD else: target = (sec-fir, sec) if target in d: ans += (d[target]*val)%MOD vis.add(target) ans %= MOD vis.add((fir, sec)) return ans第三题：列表索引求和
def solution3(A: list, X: int, Y: int):
ans = float("inf")
n = len(A)
for i in range(n):
end = i+Y*(X-1)
if end>=n:
return ans
ans = min(ans, sum(A[i: end+1:Y]))
return ans 
