2023-09-28 20:51 已编辑 门头沟学院 计算机类
关注
滴滴笔试记录一下思路，没过完全
不知道哪里出了问题，各位大佬看看
1. 记忆化搜索，我是拿一个 (a[0]<<24)|(a[1]<<16)|(a[2]<<8)|i来记忆化，首先要排序a，然后搜i，然后记忆化
2. 换根dp，第一遍dfs，求根节点到所有节点的距离，并求出每一个节点的子节点有多少个，记录在Node数组里；第二遍dfs，记当前节点cur到其他节点的距离为S，则有S[cur]=S[fa]+N-Node[cur]，其中N代表节点个数。
1. 记忆化搜索，我是拿一个 (a[0]<<24)|(a[1]<<16)|(a[2]<<8)|i来记忆化，首先要排序a，然后搜i，然后记忆化
2. 换根dp，第一遍dfs，求根节点到所有节点的距离，并求出每一个节点的子节点有多少个，记录在Node数组里；第二遍dfs，记当前节点cur到其他节点的距离为S，则有S[cur]=S[fa]+N-Node[cur]，其中N代表节点个数。
全部评论
相关推荐
投递滴滴等公司7个岗位 >
小鹏汽车一面9人在聊 点赞 评论 收藏
转发