9.10美团笔试

又是凌晨做笔试的一天，心累+1

4个编程。

1. 两个人分别以1/x和1/y的速度从左往右和从右往左工作，规定做到第k个的时候小丽获胜，判断是否获胜输出Tie/Win/Lose

思路：不要用分数去计算，把分数的分母交换一下方便计算，小丽速度为y，另外一个人速度为x，小丽时间为k*y，另外一个人时间为（n-k+1）*x，比较时间长短即可。

def judge(n, k, x, y):
    s1, s2 = y, x
    t1, t2 = k * s1, (n - k + 1) * s2

    if t1 == t2:
        return "Tie"
    elif t1 < t2:
        return "Win"
    else:
        return "Lose"

t = int(input())
for i in range(t):
    n, x, y, k = map(int, input().split())
    res = judge(n, k, x, y)
    print(res)

2. n长度的数组，一次操作为使一个数+1。问最小操作次数，使得数组和不为0，乘积也不为0。

思路：计算一下数组的和与数组中0的个数，分情况讨论。和不为0且没有0的情况下输出0；和为0且没有0的情况下输出1；和不为0但是有0的情况下输出0的个数；和为0但是也有0的情况下也输出0的个数。

可能分情况讨论最后有点问题，过了82%的case

n = int(input().strip())
arr = list(map(int, input().split()))
suma = 0
cnt_0 = 0
for num in arr:
    suma += num
    if num == 0:
        cnt_0 += 1

if suma != 0 and cnt_0 == 0:
    print(0)
elif suma == 0 and cnt_0 == 0:
    print(1)
elif suma != 0 and cnt_0 != 0:
    print(cnt_0)
else:
    print(cnt_0)

3. 完全二叉树的路径上最大值。长度为1至正无穷的结点，然后有n个宝藏，给出了对应结点位置和宝藏价值多少，每次只能从根节点到子节点，求可以获得的最大价值和。

思路：先用一个数组存储每个位置的宝藏价值，在类似于dp一样遍历，每次判断为奇数或者偶数加上根节点的价值，同时记录最大值。

这个不知道什么问题，也是过了82%的case

n = int(input().strip())
p = list(map(int, input().split()))
w = list(map(int, input().split()))
maxi = max(p)
arr = [0]*(maxi+1)
res = -1
for i in range(n):
    ind = p[i]
    val = w[i]
    arr[ind] += val
for j in range(maxi+1):
    if j % 2 == 0:
        prev = arr[j // 2]
    else:
        prev = arr[(j - 1) // 2]
    arr[j] += prev
    res = max(res, arr[j])
print(res)

4. 给一个长度为n的数组，和一个除数m。每次可以选择数组中的一个数加上10的k次幂再对m取余数，k取0~9。输出数组每个位置的数变成0的最小次数。

思路：首先用一个dic存储了10的所有次幂对m取余数的结果。然后遍历数组，当可以整除的时候对应结果为0，当不能够整除的时候需要计算m-这个数的差可以被dic中的余数加起来的次数。

这里我写了一个find函数去计算次数，但是细节有问题，导致用例没有过。

def find(dic, num):
    res = -1
    values = dic.values()
    for v in values:
        if v == 0:
            continue
        elif v == num:
            return 1
        elif num % v == 0:
            res = max(res,v)
        else:
            continue
    return num//res


n, m = map(int, input().split())
arr = list(map(int, input().split()))
dic = {}
for j in range(10):
    dic[j] = pow(10, j) % m
nums = [0] * n
for i in range(n):
    val = arr[i] % m
    if val == 0:
        nums[i] = 0
    else:
        dif = m - val
        print(dif)
        times = find(dic, dif)
        nums[i] = times
print(" ".join(nums))

选择：HDFS，attention,，数据转换

#美团笔试##美团#