开做网站的公司 条件,计算机应用技术与php网站开发,青岛网站推广,甜蜜定制app下载记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 4/1 2810. 故障键盘4/2 894. 所有可能的真二叉树4/3 1379. 找出克隆二叉树中的相同节点4/4 2192. 有向无环图中一个节点的所有祖先4/5 1026. 节点与其祖先之间的最大差值4/…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 4/1 2810. 故障键盘4/2 894. 所有可能的真二叉树4/3 1379. 找出克隆二叉树中的相同节点4/4 2192. 有向无环图中一个节点的所有祖先4/5 1026. 节点与其祖先之间的最大差值4/6 1483. 树节点的第 K 个祖先4/7 1600. 王位继承顺序 4/1 2810. 故障键盘 依次考虑 将字符串放入数组中 记录插入的位置如果逆序 则从头开始插入 loc记录是顺序还是逆序 def finalString(s)::type s: str:rtype: strloc Trueans[]for c in s:if ci:loc not locelif loc:ans.append(c)else:ans [c]ansif loc:return .join(ans)else:return .join(ans[::-1]) 4/2 894. 所有可能的真二叉树 真二叉树总结点必定为奇数 mem[i]记录i个节点的真二叉树情况 class TreeNode(object):def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right
def allPossibleFBT(n)::type n: int:rtype: List[TreeNode]if n3 or n%20:return []mem {}mem[1] [TreeNode(0)]def check(num):if num in mem:return mem[num]tmp []for l in range(1,num-1,2):left check(l)right check(num-1-l)for ln in left:node TreeNode(0)node.left lnfor rn in right:node.right rntmp.append(node)mem[num]tmpreturn tmpreturn check(n) 4/3 1379. 找出克隆二叉树中的相同节点 dfs搜索 class TreeNode(object):def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right
def getTargetCopy(original, cloned, target)::type original: TreeNode:type cloned: TreeNode:type target: TreeNode:rtype: TreeNodedef check(ori,clo):if not ori:return oriif oritarget:return cloleft check(ori.left,clo.left)right check(ori.right,clo.right)if left:return leftreturn rightreturn check(original, cloned) 4/4 2192. 有向无环图中一个节点的所有祖先 如果x为y的祖先 那么x的祖先必定是y的祖先 cur存储祖先节点已经都被考虑过的节点 par[x]记录x当前未被考虑的祖先个数 ans[x]记录x的祖先 def getAncestors(n, edges)::type n: int:type edges: List[List[int]]:rtype: List[List[int]]cur set(list(range(n)))ans [set() for _ in range(n)]m [[] for _ in range(n)]par [0]*nfor x,y in edges:if y in cur:cur.remove(y)m[x].append(y)par[y]1while cur:tmp set()for p in cur:for child in m[p]:ans[child].add(p)ans[child]|ans[p]par[child]-1if par[child]0:tmp.add(child)cur tmpfor i in range(n):ans[i] sorted(list(ans[i]))return ans 4/5 1026. 节点与其祖先之间的最大差值 从根节点往子节点判断 记录当前最大值和最小值 当前节点与最大值最小值能够得到的最大差值 class TreeNode(object):def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right
def maxAncestorDiff(root)::type root: TreeNode:rtype: intglobal ansans 0def check(node,minv,maxv):global ansif not node:returnans max(ans,abs(minv-node.val))ans max(ans,abs(maxv-node.val))minv min(node.val,minv)maxv max(node.val,maxv)check(node.left,minv,maxv)check(node.right,minv,maxv)check(root,root.val,root.val)return ans 4/6 1483. 树节点的第 K 个祖先 dp[i]用来记录i的祖先 因为n很大 使用二维dp[i][j] 记录i的第2^j个祖先 dp[i][0]即为i的父节点 dp[i][j] dp[dp[i][j-1]][j-1] 即i的第2^j个祖先 是i的第2^(j-1) 个祖先的第2^(j-1)个祖先 class TreeAncestor(object):def __init__(self, n, parent)::type n: int:type parent: List[int]self.dp [[] for _ in range(n)]for i in range(n):self.dp[i].append(parent[i])j1while True:tag Truefor i in range(n):v -1if self.dp[i][j-1]!-1:v self.dp[self.dp[i][j-1]][j-1]self.dp[i].append(v)if v!-1:tag Falseif tag:breakj1 def getKthAncestor(self, node, k)::type node: int:type k: int:rtype: intans node pos 0while k and ans!-1:if poslen(self.dp[ans]):return -1if k1:ans self.dp[ans][pos]k k1pos1return ans 4/7 1600. 王位继承顺序 可以看做是一个多叉树 继承顺序为父-子 前序遍历 根左右 dead记录死亡的人 m[x]记录x的儿子 class ThroneInheritance(object):def __init__(self, kingName)::type kingName: strfrom collections import defaultdictself.dead set()self.king kingNameself.m defaultdict(list)def birth(self, parentName, childName)::type parentName: str:type childName: str:rtype: Noneself.m[parentName].append(childName)def death(self, name)::type name: str:rtype: Noneself.dead.add(name)def getInheritanceOrder(self)::rtype: List[str]ans []def pre(name):if name not in self.dead:ans.append(name)if name in self.m:for c in self.m[name]:pre(c)pre(self.king)return ans
