微软笔试8.13
1. 堆排序，时间复杂度O(nlogn)，空间复杂度O(1)
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 cnt2. 类似两数之和，多一个通分的操作 时间复杂度O(n)，空间复杂度O(n)
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)3. 外循环遍历Y次，内循环遍历(X + (N - X) / Y)次（滑动窗口），输入范围(X - 1) * Y < N，故时间复杂度O(n)，空间复杂度O(1)
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
查看14道真题和解析