3.25美团算法笔试

a了3.18,那个0.18自认为思路没问题,自测也没问题,不知道为什么只对了0.18

python版本代码如下:

第一题

数火车,其实就是一个栈,给一个入栈顺序,一个出栈顺序,问你这种情况是不是可能的

T = int(input())

for _ in range(T):

    flag = True

    n = int(input())

    x_list = list(map(int, input().split()))

    y_list = list(map(int, input().split()))

    def is_possible_order(x_list, y_list):

        stack = []

        i = 0

        for x in y_list:

            while not stack or stack[-1] != x:

                if i == len(x_list):

                    return False

                stack.append(x_list[i])

                i += 1

            stack.pop()

        return True if not stack else False

    flag = is_possible_order(x_list, y_list)

    if flag is True:

        print('Yes')

    else:

        print('No')

第二题

糖果美味值

经典动态规划,就是看现在这个选不选。这个选了,意味着前两个都不能选了,所以是a[i]+dp[i-3],如果不选,那就等于选到前面为止的美味值即dp[i-1]

n = int(input())

a = [int(x) for x in input().split()]

dp = [0] * n

dp[0] = a[0]

dp[1] = max(a[1], a[0])

dp[2] = max(a[2], a[0], a[1])

for i in range(3,n):

    dp[i] = max(dp[i-3] + a[i], dp[i-1])

print(dp[n-1])

第三题

也是很经典的动态规划,就是不知道为什么只a了18%,这个dp就是现在能拿几块巧克力,dp[?]这个?是当前背包的容量,每选一个,就要减去当前巧克力的重量(cho[i]^2),同时多一个巧克力

import sys

n, m = map(int, sys.stdin.readline().strip().split())

cho = list(map(int, sys.stdin.readline().strip().split()))

ask = list(map(int, sys.stdin.readline().strip().split()))

bagsize = max(ask)

dp = [0] * (bagsize + 1)

for i in range(n):

    for j in range(bagsize, cho[i] * cho[i]-1, -1):

        dp[j] = max(dp[j], dp[j-cho[i] * cho[i]] + 1)

res = []

for i in range(m):

    print(dp[ask[i]])

第四题

给一个字符串,以分号分割。每个key=value当做一个键值对存到字典里。给一串字符串查找,如果没有这个key输出empty,如果有一个就输出value,如果有多个就输出最新的(可以直接覆盖,这样找到的就是最新的)。唯一要注意的就是直接按照“;”分割会导致最后多一个空字符串,删了就可以

S = list(input().strip().split(';'))[:-1]

dic_ = {}

for i in S:

    left, right = i.split('=')

    dic_[left] = right

q = int(input())

for _ in range(q):

    q_str = input().split()

    if q_str[0] not in dic_:

        print('EMPTY')

    else:

        print(dic_[q_str[0]])

#我的实习求职记录##软件开发2023笔面经#
全部评论
第三题,直接排序先取小的,所以整成前缀和,用二分做,毕竟人家不是说了背包最大1e18么,这玩意多大心里没数么?
3 回复 分享
发布于 2023-03-25 23:34 青海
正解应该是排序,排序之后前缀和二分把,第一时间想到了背包好像不太行
点赞 回复 分享
发布于 2023-03-26 00:32 江西
纳尼,第四题我就这里q_str = input().split() 没有用split(),我只过了18%,淦!
点赞 回复 分享
发布于 2023-03-26 10:10 福建
第三题贪心算法,排序一下就行
点赞 回复 分享
发布于 2023-03-26 17:05 江苏

相关推荐

9.14一面介绍项目项目中的ETL项目中的拉链表项目中的UDF项目中的Kmeans和DBSCAN八股说一下HDFS说一下进程和线程说一下数据倾斜说一下kafka说一下数仓的建模(雪花,星形,星座)说一下数仓分层的作用OLAP和OLTP的区别说一下数据库三范式手撕两道SQL手写冒泡排序(一面全部答出来了)9.18二面,二面感觉很考验对大数据的理解介绍项目项目中感觉做的最好的地方是哪些介绍一下中国软件杯的比赛你觉得你的项目和比赛在哪些地方体现出了大数据的思路讲讲你对大数据的理解讲讲你对数仓分层的理解讲讲你对数据仓库和数据库的区别的理解数仓和数据库都是SQL Boy, 你对两个SQL Boy的区别的理解有没有用过Doris和clickhouse(没有)说一下LSM Tree说一下Bit Map我看你项目里有lambda框架,讲一下lambda框架说一下Hive中的去重说一下模糊去重(这是真的不会。。。)说一下Kmeans和KNN的区别讲一下Java的集合框架手撕力扣原题,二叉树的层序遍历反问9.23 HR面介绍一下你自己为什么选择大数据你是保研的,你的成绩排名是多少为什么不选择考公或者读博你认为现在公司需要什么样的人才你在秋招的时候是怎么介绍自己的你自己有什么优势(疯狂推销自己,我学习能力强)你说你学习能力强,怎么体现出来的(幸亏我脑子转的快,答上来了)两道场景题1.你入职后,你的师傅负责带你学习,但是刚过了一周,你的师傅被紧急抽调了。这种情况下你如何学习技术。2.入职后,有人得到了晋升,而你没有。但是你感觉你自己的付出不少于他们。你会怎么做。反问9.26 oc #美团求职进展汇总#
点赞 评论 收藏
分享
6 24 评论
分享
牛客网
牛客企业服务