拼多多服务端笔试题分享（过330%）

第一题是求序列的最大的n个数，只是重新定义了大小关系，偶数比奇数都大。直接用堆排序就行。

代码：

import sys

# 调整堆的函数
def tiaozhengdui(nums, start, end, compare):
    dad = start
    son = 2 * dad + 1
    while son < end:
        if son + 1 < end:
            son = son if compare(nums[son], nums[son + 1]) else son + 1
        if compare(nums[son], nums[dad]):
            nums[dad], nums[son] = nums[son], nums[dad]
        dad = son
        son = 2 * dad + 1


# 堆排序，找到前n个数后直接返回
def duipaixu(nums, compare, geshu):
    size = len(nums)
    # 建堆
    for i in range(size // 2 - 1, -1, -1):
        tiaozhengdui(nums, i, size, compare)
    # 排序
    result = []
    n = 0
    for i in range(size - 1, -1, -1):
        nums[i], nums[0] = nums[0], nums[i]
        result.append(str(nums[i]))
        n += 1
        if n == geshu:
            print(','.join(result))
            return
        tiaozhengdui(nums, 0, i, compare)


strinput = sys.stdin.readline().strip()
strnums, strn = strinput.split(';')
n = int(strn)
nums = list(map(int, strnums.split(',')))

# 重新定义的比较函数
def compare(x, y):
    if x % 2 == 0:
        if y % 2 == 0:
            return x > y
        else:
            return True
    else:
        if y % 2 == 0:
            return False
        else:
            return x > y


duipaixu(nums, compare, n)

第二题是找A字符串如何变化为B字符串，直接用dfs暴力搜索就过了。

import sys
n = int(sys.stdin.readline().strip())

road = []
result = []


def find(origin, now, target):
    if now == target:
        result.append(' '.join(road) + ' ' + 'd ' * len(origin))
        return
    if not origin:
        return

    left = origin[0]
    norigin = origin[1:]
    road.append('d')
    find(norigin, now, target)
    road.pop(-1)
    road.append('l')
    find(norigin, left + now, target)
    road.pop(-1)
    road.append('r')
    find(norigin, now + left, target)
    road.pop(-1)


for i in range(n):
    a = sys.stdin.readline().strip()
    b = sys.stdin.readline().strip()
    print("{")
    result = []
    road = []
    find(a, "", b)
    result.sort()
    for r in result:
        print(r)
    print("}")

第三题是骰子的期望，每个骰子有1-x种可能，相当于对n个骰子的可能性做一个全排列。由于只要在n个骰子中求最大值，就可以一个一个骰子的算，用一个哈希表记录下当前情况就好。

from collections import defaultdict
import sys
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split(' ')))

nums.sort()
size = len(nums)
result = {}

if n <= 0:
    print(0)
    exit(0)

allp = nums[0]
result = {k: 1 for k in range(1, nums[0] + 1)}
for i in range(1, size):
    x = nums[i]
    allp *= x
    new_result = defaultdict(int)
    for k, v in result.items():
        for p in range(1, x + 1):
            if k >= p:
                new_result[k] += v * 1
            else:
                new_result[p] += v * 1
    result = new_result

allz = sum([k * v for k, v in result.items()])
print("%.2f" % (allz / allp))

第四题我只过了30%，先用一个数组把所有数存起来，然后用找第K大的方法去算(剑指offer方法)，会报内存溢出，估计只要全存下来就过不了。

#拼多多##笔试题目##秋招##笔经#