微软笔试8.13

def solution(A):
    # write your code in Python (Python 3.6)
    target = sum(A) / 2
    cur = 0
    cnt = 0
    n = len(A)
    def shift(i, n):
        while i * 2 + 1 < n&nbs***bsp;i * 2 + 2 < n:
            if i * 2 + 2 >= n&nbs***bsp;A[i * 2 + 1] >= A[i * 2 + 2]:
                nxt = i * 2 + 1
            else:
                nxt = i * 2 + 2
            if A[nxt] > A[i]:
                A[i], A[nxt] = A[nxt], A[i]
            i = nxt
    for i in range(n // 2, -1, -1):
        shift(i, n)
    while cur < target:
        A[0] /= 2
        cur += A[0] 
        shift(0, n)
        cnt += 1
    return cnt

def gdc(a, b):
    mod = 1
    while mod != 0:
        mod = a % b
        a = b
        b = mod
    return a
def solution(X, Y):
    # write your code in Python (Python 3.6)
    from collections import defaultdict
    hash_map = defaultdict(int)
    n = len(X)
    for i in range(n):
        a, b = X[i], Y[i]
        m = gdc(a, b)
        hash_map[(a//m, b//m)] += 1
    ans = 0
    for key, val in hash_map.items():
        a, b = key[0], key[1]
        if a * 2 < b:
            ans += hash_map[(b - a, b)] * val
        elif a * 2 == b:
            ans += val * (val - 1) // 2
    return ans % (10 ** 9 + 7)

def solution(A, X, Y):
    # write your code in Python (Python 3.6)
    n = len(A)
    ans = 2 ** 31 - 1
    for i in range(Y):
        left = i
        curSum = 0
        for j in range(X):
            if left + j * Y >= n:
                return ans
            curSum += A[left + j * Y]
        ans = min(ans, curSum)    
        right = left + X * Y
        while right < n:
            curSum = curSum - A[left] + A[right]
            ans = min(ans, curSum)
            left += Y
            right += Y
    return ans