企业网站建设与实现的论文,网站建设2017国内排行,调用别人网站注册表单,兰州市建设局网站国贸大厦834 Sum of Distances in Tree
思路#xff1a;一颗无向的树有N个节点#xff0c;分别标记为0,1,2,…N-1#xff0c;有若干条边。结果返回每个节点到其他节点的路径和。 以上面这棵树为例。从节点0到其他点的路径查找过程是#xff1a;节点0有两条边分别到达子节点1和子节…834 Sum of Distances in Tree
思路一颗无向的树有N个节点分别标记为0,1,2,…N-1有若干条边。结果返回每个节点到其他节点的路径和。 以上面这棵树为例。从节点0到其他点的路径查找过程是节点0有两条边分别到达子节点1和子节点2递归查找节点1节点1没有子节点节点2继续查找节点2的子节点…依次下去。递归每进一层路径就需要加1。 遍历完节点0以后再以节点1为根节点遍历。 时间复杂度O(N*E),E是边的数目。这个思路超时。既然是超时定是因为有重复计算的。例如遍历边(0,2)之后又遍历了一次(2,0)。但是该怎么合并计算我没想出来。 学习接下来的描述相当于翻译官方解释吧。 用一颗新的树为例子。节点0和节点4是父子关系也是相邻节点。现在观察一下相邻节点连接后路径和发生什么变化。 将节点0和节点4的路径断开得到下图。 记stsum[0] 表示节点0在节点0子树上的路径和。stsum[4]表示节点4在节点4子树上的路径和。count[0]表示节点0子树的节点数。answer[0]表示节点0在整个树的路径和。answer[4]表示节点4在整个树的路径和。
当节点0和节点4之间加上路径后answer[0] stsum[0] stsum[4] count[4]。因为节点0到节点4子树上所有点的距离与节点4到节点4子树上所有点的距离都要加1。answer[4] stsum[4] stsum[0] count[0]。而且能得到answer[0]-answer[4]count[4]-count[0]。
所以得到结论:相邻节点父子节点x,y在整个树的路径和是answer[x]−answer[y]count[y]−count[x]answer[x] -answer[y] count[y] - count[x]answer[x]−answer[y]count[y]−count[x]。 编码过程 1 answer[]存储以每个节点为根节点在整个树的路径和 2 count[] 存储以每个节点为根节点的子树的节点数初始化每个元素值1 3 对某个节点node,dfs后序遍历,先处理子节点,计算每个子节点y的count和stsumcount[node]count[child]count[node]count[child]count[node]count[child]stsum[node]stsum[child]count[child]stsum[node] stsum[child]count[child]stsum[node]stsum[child]count[child]当遍历了所有的边以后answer[node]stsum[node]answer[node] stsum[node]answer[node]stsum[node]如果我们从节点0开始遍历。这次遍历结束后只有answer[0]是正确的。其他节点都没有遍历完全。 4 再看上面分析了两个相邻节点父子节点的路径和关系。如果有节点parent和子节点child则有answer[child]answer[parent]−count[child](N−count[child])answer[child] answer[parent] - count[child] (N - count[child])answer[child]answer[parent]−count[child](N−count[child])因为我们已经得到answer[0]的正确结果可以依据算式计算节点0的子节点的answer。算式中之所以使用count[child]来计算count[parent]N−count[child])count[prent]N - count[child])count[prent]N−count[child])count[prent]是因为在上一步的后续遍历过程中count[parent]的值已经发生变化不再是parent、child状态下的count (原文的解释是count[child]从child得到parent比较容易)。用先序遍历再次遍历树修改每个子节点的answer得到最终结果。 代码
301 Remove Invalid Parentheses
思路最直接的想法把s中每一个(,)去掉检查新的字符串是不是有效字符串如果是则加入到结果集。 这样不符合题意的要求去掉最少的括号。那么需要计算最少去掉几个左括号去掉几个右括号就可以是有效字符串。 在编码过程中注意去重。 代码 学习可以改进不再需要判断是否是有效字符串。添加变量open。有效字符的特征是左括号在前所以open0左右括号个数相同open0多余的左右括号都去掉了leftCount0 and rightCount0。 代码
