微软笔试高效AK代码

工厂污染最小化问题

import heapq

def solution(N):
    target = sum(N)/2
    bigHeap, sum_, curr_traget = [], 0, 0
    for i in N:
        heapq.heappush(bigHeap, -i)
    while curr_traget<target:
        ele = heapq.heappop(bigHeap)
        curr_traget+=(-ele)/2
        sum_+=1
        heapq.heappush(bigHeap, ele/2)
    return int(sum_)

有效分数对组合问题

from fractions import Fraction
from collections import defaultdict

def solution(X, Y):
    # write your code in Python (Python 3.6)
    elements = defaultdict(int)
    n , sum_ = len(X), 0
    for i in range(n):
        elements[Fraction(X[i], Y[i])]+=1
    keys = list(elements.keys())
    keys.sort()
    front, back = 0, len(keys)-1
    while keys[front]<=Fraction(1,2) and keys[back]>=Fraction(1,2):
        if keys[front]+keys[back]>1:
            back-=1
        elif keys[front]+keys[back]<1:
            front+=1
        else:
            front_temp = elements[keys[front]]
            back_temp = elements[keys[back]]
            if front!=back:
                sum_ = sum_+front_temp*back_temp
            else:
                sum_+=front_temp*(front_temp-1)/2
            front+=1
            back-=1
        if back==-1 or front==len(keys):
            break
    return int(sum_)

治疗费用最小化问题

def solution(A, X, Y):
    # write your code in Python (Python 3.6)
    A_len, ans = len(A), 1e10
    for i in range(A_len):
        if i+(X-1)*Y<A_len:
            temp = sum(A[i:i + (X-1) * Y + 1:Y])
            if temp<ans:
                ans = temp
        else:
            return ans
            break