20200721 网易互娱ME提前批笔试(未允禁转)
20200721 网易互娱ME提前批笔试 4编程
1.翻转一棵多叉树。该多叉树的每个结点的val唯一
多叉树按照先序遍历的顺序，以数组的方式记录。数组的每个元素以数组表示每个treenode，如：[1,0]表示当前结点的val是1，其父结点的val是0，这里规定根节点的父结点总是0。下面的例子表示一棵双层的三叉树
[[1,0], [2,1], [3,1], [4,1]]
思路：
因为树是递归的，一棵树的子树也是树，子树的子树也是树。翻转一棵树，从图像上看=颠倒它的每一棵子树的位置，再递归地翻转每棵子树的子树；从代码上看，如果我对原多叉树进行“先后-左”顺序遍历，就是它的翻转后的树的先序遍历顺序
本题拿到当时有两种思路
1.先利用前序遍历的结果重建出一颗多叉树，然后对重建出来的多叉树按照“先右-左”的顺序遍历，得到的结果就是翻转后的结果，因为要对多叉树重建，当时直觉感觉比较麻烦，所以暂时搁置，第二天才复盘思考的
因为是多叉树，那么TreeNode的结构只能是
class TreeNode:
def __init__(self, v):
self.val = v
self.father = None
self.children = []
通过list[TreeNode]来描述子节点
根据先序遍历重建树，可以设计一个递归方法buildTree(node_data_list)实现
递归的输入和输出是：接受整棵树的先序遍历序列node_data_list，返回建好的树的root；递归式是node.children.append(buildTree(sub_tree))
每次我们需要在原先序遍历序列中找到各个子树对应的部分子序列，作为参数执行递归调用
伪代码模板如下，实际上就两步，方便得很
def buildTree(node_data_list):
# 递归函数先写递归出口
if not node_data_list:
return
## 第一步，build root -【首个结点必然作为node_data_list对应的树的根】 ##
first_ele = node_data_list[0]
... build root_node base on first_ele ...
## 第二步，build every sub_tree and establish relation to root_node ##
find every sub_tree data sequence from node_data_list
for each sub_tree data sequence:
root_node.children.append(buildTree(sub_tree))
return root_node
整个实现的代码如下
class TreeNode:
def __init__(self, v):
self.val = v
self.father = None
self.children = []
class Solution:
def invert_tree(self , node_data_list):
l = len(node_data_list)
# 边界条件
if l <= 1:
return node_data_list
root = self.buildTree(node_data_list, 0)
res = []
self.reverseOrder(root, res)
return res
# 建树，并返回树的根结点
def buildTree(self, node_data_list, first_ele_father):
if not node_data_list:
return
first_ele = node_data_list[0]
node = TreeNode(first_ele[0])
node.father = first_ele_father
sub_tree_start_index = 1
for i in range(2, len(node_data_list)):
ele = node_data_list[i]
if ele[1] == first_ele[0]:
# 获取子树对应的数组数据
sub_tree = node_data_list[sub_tree_start_index:i]
sub_tree_start_index = i
# 对子树进行buildtree
sub_tree_root = self.buildTree(sub_tree, first_ele[0])
node.children.append(sub_tree_root)
sub_tree = node_data_list[sub_tree_start_index:]
sub_tree_root = self.buildTree(sub_tree, first_ele[0])
node.children.append(sub_tree_root)
return node
# “先右-左”顺序访问一棵树
def reverseOrder(self, root, res):
if not root:
return
res.append([root.val, root.father])
for c in root.children[::-1]:
self.reverseOrder(c, res)
s = Solution()
print(s.invert_tree([[1,0],[2,1],[5,2],[6,5],[7,5],[3,1],[4,1]]))
- 直接在先序遍历序列上找规律。通过分析发现，树翻转后的先序遍历结果，就是把各个子树对应的序列sub1，sub2，sub3... 倒置成 ...sub3，sub2，sub1，然后每个sub里再继续倒置，递归下去直至结束。这是我当时采用的解法
递归函数设计
输入输出：输入node_data_list int整型二维数组，输出翻转后的res，也是整型二维数组
递归式：res = [node_data_list[0]] && res += self.invert_tree(node_dlist)
# # 一次ac 40min
# #
# # @param node_data_list int整型二维数组
# # @return int整型二维数组
# #
class Solution:
def invert_tree(self , node_data_list ):
l = len(node_data_list)
# 递归出口
if l <= 1:
return node_data_list
father_id = node_data_list[0][0]
sub_tree = []
end_index = l
# 倒序方式找出各个子树集，就完成了各sub的倒置
for i in range(l-1, 0, -1):
if node_data_list[i][1] == father_id:
sub_tree.append(node_data_list[i:end_index])
end_index = i
res = [node_data_list[0]]
for node_dlist in sub_tree:
# 递归调用
res += self.invert_tree(node_dlist)
return res
s = Solution()
print(s.invert_tree([[1,0],[2,1],[5,2],[6,5],[7,5],[3,1],[4,1]]))
2. 查找运送情报路途中最危险城市
给定n个城市，每个城市用1-n表示。城市1危险系数最高为1，离城市1越近的城市危险系数越高。城市之间有路径相连，且任意两个城市之间的路径唯一。输入一个整数road_num，描述地图中城市间通路的数量，接着输入road_num数量的二元组，如 1 2 表示城市1、2之间直接联通；再接下来输入整数targets，表示情报传送任务的数量，再输入targets个二元组，如 3 6 表示需要将情报送达城市3，4，5，6。要求打印每次情报传送任务中经过的最危险的城市
思路：
首先，需要描述整个地图，这里采用邻接字典 dict {city1:[nei1, nei2, ...], ...}结构，需要遍历所有城市通路，O(road_num)
然后，根据邻接字典，通过BFS或DFS生成城市等级字典
再者，定义一个函数，接受起始城市、目标城市和邻接字典，通过dfs返回它们的联通路径
最后，对每一个target进行分解，如 3 6 ，分解为3-4，4-5，5-6，检查每一小组的联通路径并更新路径上的最危险城市（每一小组都要dfs查路径，复杂度就高了，但好像没有什么好办法）
# ac 40 % 原因超时 1h10min，改不动
# 生成邻接字典
def genNeiborDict(roads):
d = dict()
for r in roads:
a, b = r[0], r[1]
if a not in d:
d[a] = []
if b not in d:
d[b] = []
if a not in d[b]:
d[b].append(a)
if b not in d[a]:
d[a].append(b)
return d
# dfs，生成城市等级字典
def genLevelDict(neibor_d):
level_d = {1:1}
s = set()
s.add(1)
def dfs(neibors, visited, level_to_assign):
for n in neibors:
if n not in visited:
level_d[n] = level_to_assign
visited.add(n)
dfs(neibor_d[n], visited, level_to_assign+1)
dfs(neibor_d[1], s, 2)
return level_d
# dfs回溯定路径
def getRoadMaxCity(neibor_d, a_road):
start, end = a_road
track = [start]
found_flag = [False]
final_track = []
def backtracking(track, end, found_flag, final_track):
if track[-1] == end:
found_flag[0] = True
for ele in track:
final_track.append(ele)
return
last_city = track[-1]
for nex in neibor_d[last_city]:
if nex not in track:
# 修改状态
track.append(nex)
backtracking(track, end, found_flag, final_track)
# 修回
track.pop(-1)
if found_flag[0]:
return
backtracking(track, end, found_flag, final_track)
return final_track
## 处理输入输出 ##
import sys
content = list(sys.stdin)
road_num = int(content[0].strip())
roads = [content[i].strip().split() for i in range(1, road_num)]
for i in range(road_num-1):
roads[i] = [int(ele) for ele in roads[i]]
target_num = int(content[road_num].strip())
targets = [content[i].strip().split() for i in range(1+road_num, 1+road_num+target_num)]
for i in range(target_num):
targets[i] = [int(ele) for ele in targets[i]]
# print(road_num, roads, target_num, targets)
## 处理输入输出完毕 ##
neibor_d = genNeiborDict(roads)
level_d = genLevelDict(neibor_d)
for r in targets:
lev, res_city = float('inf'), 0
r.sort()
begin_city = r[0]
des_city = r[0] + 1
while des_city <= r[1]:
track = getRoadMaxCity(neibor_d, [begin_city, des_city])
# print([begin_city, des_city], track)
for t in track:
if level_d[t] < lev:
lev = level_d[t]
res_city = t
begin_city, des_city = des_city, des_city + 1
print(res_city)
3. 检查病毒类型
没看，return 1 过了50多%骗分
4. 并查集分类问题
给一个list，包含所有元素
再给一个二维list，每个元素是长度为2的list，表示2个ele为同类
求最后分成几类
思路：
特征比较明显的并查集问题。时间不多，疯狂coding
事后总感觉哪里不太对，回想发现并查集的findRoot(ele)方法写错了一个地方。。。导致一直死循环，然而已经提交，凉了
这里罚重写一次
class UFS:
def __init__(self):
self.father = dict()
def findRoot(self, ele):
####！！！！醒醒！！是if 不是 while ！！！！while就死循环了####
if self.father[ele] != ele:
self.father[ele] = self.findRoot(self.father[ele])
return self.father[ele]
def union(self, ele1, ele2):
r1, r2 = self.findRoot(ele1), self.findRoot(ele2)
if r1 != r2:
self.father[r1] = r2
