美团机器学习实习 笔试记录 4.16

ac4题,最后一个18%应该是超时了。

第一题ac 
直接暴力,需要注意
1. 并列第一
2. 同一个人只能算一次
两种情况
用set保存下学生编号避免重复计算人次就好。
# -*- coding:utf-8 -*-

try:
    while True:
        N, M = map(int, input().split())
        scores = []
        for i in range(N):
            scores.append(list(map(int, input().split())))
        res = set()
        for i in range(M):
            max = -1
            ans = []
            for j in range(N):
                if scores[j][i] > max:
                    ans = []
                    ans.append(j)
                    max = scores[j][i]
                elif scores[j][i] == max:
                    ans.append(j)
                else:
                    pass
            for it in ans:
                res.add(it)
        print(len(res))
except:
    pass

第二题ac 
直接实现伪代码,用set()判断是否开始循环即可。
# -*- coding:utf-8 -*-

try:
    while True:
        a, b, m, x = map(int, input().split())
        s = set()
        while True:
            x = (a * x + b) % m
            if x in s:
                print(len(s))
                break
            else:
                s.add(x)
except:
    pass

第三题ac
有个坑,最开始是想直接 left = K//N, right = K%N,最后结果就是 nums[left][right],只过了45。
后面发现要注意数字重复的情况:比如 2 2 1 的排序是   (2,1) (2,1) (2,2) (2,2) (2,2) (2,2)
# -*- coding:utf-8 -*-

# try:
while True:
    N, K = map(int, input().split())
    nums = sorted(list(map(int, input().split())))
    if N == 0:
        continue
    leftIndex = K // N
    # rightIndex = K % N
    # if rightIndex == 0:
    #     rightIndex = N
    #     leftIndex -= 1

    cnt = 1
    l = leftIndex - 1
    r = leftIndex + 1
    while l >= 0 and nums[l] == nums[leftIndex]:
        l -= 1
        cnt += 1
    while r < N and nums[r] == nums[leftIndex]:
        r += 1
        cnt += 1

    leftIndex = l + 1
    rightIndex = (K - leftIndex * N) // cnt

    if rightIndex == 0:
        rightIndex = N
        leftIndex -= 1

    print("({},{})".format(nums[leftIndex], nums[rightIndex-1]))

#
# except:
#     pass

第四题ac

try:
    INT_MAX = 99999999
    n, k = map(int, input().split())
    A = sorted(list(map(int, input().split())))

    cen = (n + 1) / 2
    last_idx = 0
    min_res = INT_MAX
    temp = -1
    for i in range(n):
        if A[i] < k:
            temp = i
        if A[i] == k and min_res > abs(cen - 1 - i):
            last_idx = i
            min_res = abs(cen - 1 - i)

    left, right = 0, 0
    if min_res == INT_MAX:
        n += 1
        left = temp + 1
        right = n - left - 1
    else:
        left = last_idx
        right = n - left - 1

    if left == right:
        print(0)
    elif left < right:
        sub = right - left
        if min_res == INT_MAX:
            sub += 1
        print(sub - 1)
    else:
        sub = left - right
        if min_res == INT_MAX:
            sub += 1
        print(sub)
except:
    pass

第五题 
滑动窗口遍历S子串
DFS 匹配T子序列
用字典保存重复结果 + 剪枝,过18%超时,目测应该是DP

# -*- coding:utf-8 -*-

MOD = 1e9 + 7

def helper(s, t, len_s, len_t, now_s, now_t, ans):
    if now_s == len_s:
        ans[0] += 1
        ans[0] %= MOD
        return 0
    if now_t == len_t:
        return 0


    for i in range(now_t, len_t):
        if s[now_s] == t[i] and len_s - now_s <= len_t - i:
            helper(s, t, len_s, len_t, now_s+1, i+1, ans)



try:
    while True:
        S = input()
        T = input()
        lenS = len(S)
        lenT = len(T)
        ans = [0]
        dic = {}
        for lens in range(1, lenS+1):
            left = 0
            while left + lens <= lenS:
                # print(S[left:left+lens])
                x = S[left:left+lens]
                if x in dic:
                    ans[0] += dic[x]
                    ans[0] %= MOD
                else:
                    tt = ans[0]
                    helper(x, T, lens, lenT, 0, 0, ans)
                    dic[x] = ans[0] - tt
                    # print("xxx")
                left += 1
        print(int(ans[0]))
except:
    pass




#美团笔试##美团##实习##笔经##笔试题目##春招#
全部评论
嵌入式实习笔试和机器学习实习笔试考题一样
点赞 回复 分享
发布于 2020-04-16 22:58
楼主厉害,票四题都是Ac100%吗
点赞 回复 分享
发布于 2020-04-16 21:20
python就是好,c++还得判断long什么的,是不是溢出
点赞 回复 分享
发布于 2020-04-16 21:20

相关推荐

牛客40297450...:不是研究生强,是你强
点赞 评论 收藏
分享
牛油果甜奶昔:别的先不说,牛客还能内推护士?
点赞 评论 收藏
分享
评论
3
13
分享

创作者周榜

更多
正在热议
更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务