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]]))

2. 直接在先序遍历序列上找规律。通过分析发现，树翻转后的先序遍历结果，就是把各个子树对应的序列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