微软笔试8/19凉经
第一题 压路机
XY两个数组，Y没用，我就只遍历X数组
def solution(X, Y, W): X = sorted(list(set(X))) result, p = 0, -10**12 for i in range(len(X)): if p + W < X[i]: p = X[i] result += 1 return result第二题 组成最大回文数字
题目：用所给字符串中的数字组成一个值最大的回文字符串
（焯！！！提交了之后才发现写错了一个地方，centre初始化成0了，已在下面修改。只给几个样例测试我就疏忽。md，啊啊啊啊啊啊啊啊啊啊抓狂了！我是铸币吧啊啊啊啊这么简单的题没法AC啊啊啊啊啊啊啊）
def solution(S): hashmap = collections.defaultdict(int) result, centre = "", "" for s in S: hashmap[int(s)] += 1 for i in range(9, -1, -1): if hashmap[i] > 0 and hashmap[i] % 2 == 0: if result == "" and i == 0: continue result += str(i) hashmap[i] -= 2 break for i in range(9, -1, -1): if hashmap[i] > 0: if result == "" and i == 0: continue centre = str(i) hashmap[i] -= 1 break return result+centre+result[::-1]第三题 省油搭车
题目：一个城市，好多路口，每个路口的人都要去node 0上班，可以一起搭车，可以中途换车，车容量5，走一个edge燃料多一个，怎么走省油。
一开始以为是个图论，是不是还得用动态规划，懵了一会儿，发现其实是个树，写一个递归做bfs回溯可解决。我写法很图省事儿，没有样例测试不知道是不是会超时，佬们勿喷
def solution(A, B): def bfs(root=0): nodes = [] fuel, passengers = 0, 1 for i in range(len(A)): if A[i] == root&nbs***bsp;B[i] == root: nodes.append(A[i] if B[i] == root else B[i]) A[i] = B[i] = None for node in nodes: fuel_, passengers_ = bfs(node) fuel += fuel_ + (passengers_ // 5 + 1) passengers += passengers_ return fuel, passengers return bfs()[0]
总结：第一题还可以优化，第二题写错，多好的机会没把握住。投微软就当刷LeetCode了，唉
#秋招##微软##笔试# 
投递美团等公司6个岗位 >