微软：2022-8-19-笔试

讨论动态：https://www.nowcoder.com/feed/main/detail/c5f5334140504629b1f3225cad4aa2fd

第一题

直接求解+二分优化，复杂度 ，但是无法证明直接求解的是最优解*。

Code

import bisect
import math
from collections import Counter, defaultdict

def solution(X, Y, W):
    cnt = Counter(X)
    N = len(cnt.keys())
    mi, mx = int(2e9), 0
    for i in cnt.keys():
        mi = min(mi, i)
        mx = max(mx, i)
    if mx - mi <= W:
        return 1
    x_pos = list(sorted(cnt.keys()))
    i = 0
    ans = 0
    while i < N:
        x = x_pos[i]
        y = x + W + 0.5
        j = bisect.bisect(x_pos, y)
        i = j
        ans += 1
    return ans

第二题

比较通用的解法是：贪心+堆优化。
由于问题的特性，可以只对10个数进行统计和遍历就行，因此可以实现一种更为简洁的写法。

Code

from collections import Counter
import heapq
class Num:
    def __init__(self, val, cnt=1):
        self.val = val
        self.cnt = cnt

    def __lt__(self, other):
        if self.cnt > 1 and other.cnt > 1:
            return self.val > other.val
        elif self.cnt > 1:
            return True
        elif other.cnt > 1:
            return False
        else:
            return self.val > other.val

    def __repr__(self):
        return 'Num(%d, %d)' % (self.val, self.cnt)

def solution(S):
    ans = 0
    counter = Counter([int(i) for i in S])
    nums = [Num(val, cnt) for val, cnt in counter.items()]
    heapq.heapify(nums)
    left, right = '', ''
    leading_zero = None
    while len(nums):
        n = heapq.heappop(nums)
        cnt = n.cnt
        val = n.val
        is_leading_zero = (len(left) == 0 and val == 0) # leading zero
        if is_leading_zero:
            if len(nums) == 0:
                cnt = 1
            else:
                leading_zero = n
                continue
        if cnt == 1:
            left += str(val)
            break
        half = cnt // 2
        left += str(val) * half
        right = str(val) * half + right
        if cnt % 2 == 1:
            heapq.heappush(nums, Num(val, 1))
        if leading_zero:
            heapq.heappush(nums, leading_zero)

    ans = left + right
    return ans

第三题

直接 DFS 即可。
每次 DFS 返回一个 cost 和人数，当前点的 cost 、人数分别为由深层DFS返回的 cost 之和、人数之和，在当前非0的点返回前再对 cost 加上 ceil(当前人数/5)。

Code

import math
from collections import Counter, defaultdict

vis = defaultdict(bool)
g = defaultdict(list)

def dfs(u):
    vis[u] = True
    cost = 0
    cnt = 1
    for v in g[u]:
        if not vis[v]:
            c, n = dfs(v)
            cost += c
            cnt += n
    if u != 0:
        cost += int(math.ceil(cnt / 5))
    return cost, cnt

def solution(A, B):
    N = len(A)
    for i in range(N):
        a = A[i]
        b = B[i]
        g[a].append(b)
        g[b].append(a)
    cost, cnt = dfs(0)
    return cost