字节笔试10-8

第一题:染色
有一个树,根节点是1,你可以给它染红,蓝,绿三种颜色,但是每一个结点的染色不能和他的父亲结点和爷爷结点颜色相同。第一行输入n,代表n个结点,第二行输入n-1组数,代表n-1条边,左右分别是u,v,u是v的父亲结点。请给出任意一种可行的解。

样例如下,
输入为:
4
1 2
3 4
1 3

输出:
BGRG

一开始楼主也不会,真的放了个国庆直接废了,而且本身基础也不扎实,再加上一下比较慌没看到根节点其实已经给出来了就是1,就没做出来,其实后来静下心来看看是很简单的(心态真的很重要)。

为什么说简单呢? 第一,他给了我们三种颜色,说子节点不和父亲结点、爷爷结点同色,由于3>2,随便父亲和爷爷结点是什么搭配,你一定至少剩下一种颜色可以选。所以我们从根节点1开始随便选一种颜色,必定可以走到最后,不存在走到半路无解还需要回溯的情况。所以也就不需要什么dfs,回溯法云云。

我是这么想的:建立一个队列用二叉树层序遍历,一开始直接用红色,后续就有哪种用哪种就完了

代码如下:

n = int(input().strip())
g = dict()
for i in range(1,n+1):
    g[i] = []
for _ in range(n-1):
    u,v = list(map(int,input().strip().split()))
    g[u].append(v)
colors = ['R','G','B']
res = ['R']*n
queue = [(1,'R',None)]
while queue:
    node,cur_col,father_col = queue.pop(0)
    for child in g[node]:
        for color in colors:
            if color!=cur_col and color!=father_col:
                res[child-1] = color
                queue.append((child,color,cur_col))
print(res)

queue的每一个结点都记录当前结点编号,当前结点颜色以及父亲结点颜色,那么从queue中pop出来的结点,我们去找他的子节点,然后遍历colors一定能找到一种可用的颜色,再添加到答案中并把孩子结点也塞到queue中,直到层序遍历完,答案也就有了。

#字节跳动##笔试##秋招#
全部评论
2*n个人前往餐厅聚餐,餐厅共有两排,每排坐n个人,第一排的第个人和第二排的第i个人面对面一共上了2*n道菜,由于距离限制,每个人只能吃到自己面前的、自己两边的和自己对面的人面前的菜。 现在已知一共有两种人: 1.能吃蘑菇的。 2.不能吃蘑菇的 对于第二类人,他每在能吃到的菜里发现一次蘑菇,他的愤怒值就会加1。第一类人不会有任何愤怒值。现在给定了每个人的座位安排,以及所有菜中包含蘑菇的菜的数量x。请你安排一种合适的上菜顺序使得所有人的愤怒值之和尽可能小。 有人有这题么,是用动规做么,求具体思路
1 回复 分享
发布于 2023-10-08 23:56 天津
第一题还记得吗
点赞 回复 分享
发布于 2023-10-08 22:03 黑龙江
这道题要自己建立树吧,而且节点号可能跟树的顺序不一样😓😓可烦了,比如5可能是第二个节点,6可能是第三个节点
点赞 回复 分享
发布于 2023-10-08 22:05 黑龙江
这道题写了个层序遍历但是才过了60%,剩下的说超时,没想通
点赞 回复 分享
发布于 2023-10-08 22:06 吉林
听其他人评论说这个题目存在“无向边”的说法(明明都说了是树),那么按照无向边来做的话,就需要额外加一个从v到u的图来增加判断,感觉会很复杂。。。反正存在很多争议,我觉得这么复杂的模式不应该出在第一题,而且我也听说了还有人到后面再提交就100%了。。。
点赞 回复 分享
发布于 2023-10-08 22:08 湖南

相关推荐

10-25 00:32
香梨想要offer:感觉考研以后好好学 后面能乱杀,目前这简历有点难
点赞 评论 收藏
分享
1 6 评论
分享
牛客网
牛客企业服务