携程9.9算法岗笔试AK代码

感谢携程三道medium,在动辄hard,acm题的笔试里面简直一股清流
第一题最大方阵和:
思路:二维前缀和
x = input().split()
x = list(map(int,x))
n,m,k = x[0],x[1],x[2]
matrix = []
for _ in range(n):
    x = input().split()
    x = list(map(int,x))
    matrix.append(x)
res = 0 
prefix = [[0] * (m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1]
res = 0
for i in range(k,n+1):
    for j in range(k,m+1):
        res = max(res,prefix[i][j] - prefix[i][j-k] - prefix[i-k][j] + prefix[i-k][j-k])
print(res)


第二题,模拟四种状态
思路:直接模拟即可
import heapq
n = int(input())

stack = []
num = 0
def put(x,y):
    heapq.heappush(stack,[y,x])
    global num
    num += x
def get(x):
    global num
    if x > num:return 'no'
    num -= x
    while stack and stack[0][1] <= x:
        x -= heapq.heappop(stack)[1]
    if x:
        stack[0][1] -= x 
    return 'yes'
def nextday():
    global num 
    while stack and stack[0][0] == 1:
        num -= heapq.heappop(stack)[1]
         
    for i in range(len(stack)):
        stack[i][0] -= 1
def getnearst():
    if not stack:return 0
    return stack[0][0]

for i in range(n):
    x = input().split()
    x = list(map(int,x))
    if x[0] == 1:
        put(x[1],x[2])
    elif x[0] == 2:
        print(get(x[1]))
    elif x[0] == 3:
        nextday()
    elif x[0] == 4:
        print(getnearst())

第三题,黑白树
思路:带备忘录的dfs
class Node:
    def __init__(self,color):
        self.child = []
        self.color = color

x = input().split()
x = list(map(int,x))
n,root = x[0],x[1]
cache = {}
 
color = input().split()
color = list(map(int,color))
for i in range(len(color)):
    cache[i+1] = Node(color[i])
while True:
    try:
        x = input().split()
        x = list(map(int,x))
        cache[x[0]].child.append(x[1])
    except:
        break
memo = [0] * (n+1)
def dfs(i):
    if memo[i]!=0:
        return memo[i]
    res = 0 
    for node in cache[i].child:
        if cache[node].color != cache[i].color:
            res += 1
        res += dfs(node)
    memo[i] = res
    return res
dfs(root)
for i in range(1,n+1):
    print(memo[i])




#携程笔试##携程##笔经#
全部评论
第一题直接暴力也过了。。。
点赞
送花
回复
分享
发布于 2021-09-09 21:17
您好,请问我这样切片做只通过18%可能是什么原因呢?
点赞
送花
回复
分享
发布于 2021-09-09 21:21
秋招专场
校招火热招聘中
官网直投
第三题里面的root没有用吗?而且题目里面说1 2只是1和2相连,并没有说1是2的父节点。我是不是想复杂了😓
点赞
送花
回复
分享
发布于 2021-09-09 21:39
大佬,这个题的第一个用例的输出是啥来
点赞
送花
回复
分享
发布于 2021-09-10 01:25
第三题几乎一样啊,只不过我是用了邻接矩阵来表示节点之间的关系,也有备忘录,就过了9%,emmm
点赞
送花
回复
分享
发布于 2021-09-10 09:38
类似这样
点赞
送花
回复
分享
发布于 2021-09-10 09:47
这算是mid题嘛  哎
点赞
送花
回复
分享
发布于 2021-09-10 10:02
看起来第二题写的都差不多为什么我只通过了27%。。离了个大谱
点赞
送花
回复
分享
发布于 2021-09-11 00:11
老哥后续如何了,面试?
点赞
送花
回复
分享
发布于 2021-11-08 09:17
请问,还有单项选择题吗,算法岗,是哪方面的?DL&nbs***bsp;ML
点赞
送花
回复
分享
发布于 2021-11-08 12:02

相关推荐

感觉这一周太梦幻了,就像一个梦,很不真实~~~感觉这个暑期,我的运气占了99成,实力只有百分之一4.15上午&nbsp;腾讯csig&nbsp;腾讯云部门,面完秒进入复试状态4.16下午&nbsp;美团优选供应链部门,4.18上午发二面4.17晚上&nbsp;阿里国际一面,纯拷打,面完我都玉玉了4.18下午&nbsp;阿里国际二面,是我们leader面的我,很轻松~~4.18晚上&nbsp;约了hr面4.19上午&nbsp;hr面,下午两点口头oc4.19晚上&nbsp;意向书说起来我的暑期好像一次都没挂过~~~~~难道我是天生面试圣体?----------------------------------------------------------------------六个月前,我还是0项目0刷题,当时想的是先把论文发出来再去找实习。结果一次组会,老师打破了我的幻想(不让投B会,只让投刊或者A)我拿头投啊!!!然后就开始物色着找实习,顺便做完了mit的6.s081,但是基本上还是没刷过题目-----------------------------------------------------------------------11月&nbsp;&nbsp;一次偶然的机会,面进了某个耳机厂的手环部门,大概是做嵌入式的,用的是CPP。12月&nbsp;莫名其妙拿到了国创的面试机会,0基础四天速成java基础!居然也给我面过了hhhhh,可能是面试没写题吧入职国创后的几个月,一直没活,天天搁那看剧,都快忘了还有暑期实习这回事了~~~~命运的齿轮在2.26开始转动,因为这一天美团开了,我开始慌了,因为那时的我什么都不会。lc,八股,sql全部是0进度。然后就开始了女娲补天,上班刷题,下班继续做之前的开源,顺便学一学八股。3月到现在,lc也刷到快200了,一天最多提交了47次~~~~~~~~~~八股根据别人的面经总结和博客,写了快十万字的笔记~~~~~~~~~~简历上的实习经历和开源,也努力去深挖了,写了几万字的记录~~~~~~所以面试的时候,基本上都能cover了,面试官问到的基础基本都会,不基础的我就把他往我会的地方引。结果好像还不错,基本上每个面试官评价都挺好的emmmmmmmm
投递阿里巴巴等公司10个岗位
点赞 评论 收藏
转发
9 12 评论
分享
牛客网
牛客企业服务