拼多多服务端笔试题分享（过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方法)，会报内存溢出，估计只要全存下来就过不了。
