泰州市建设工程质量监督站网站,专业企业网站建设价格,中国建设银行官方网站诚聘英才,wordpress本地上传插件记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/26 938. 二叉搜索树的范围和2/27 2867. 统计树中的合法路径数目2/28 2673. 使二叉树所有路径值相等的最小代价2/29 2581. 统计可能的树根数目3/1 2369. 检查数组是否存在…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/26 938. 二叉搜索树的范围和2/27 2867. 统计树中的合法路径数目2/28 2673. 使二叉树所有路径值相等的最小代价2/29 2581. 统计可能的树根数目3/1 2369. 检查数组是否存在有效划分3/2 2368. 受限条件下可到达节点的数目3/3 2/26 938. 二叉搜索树的范围和 dfs 判断节点值是否在区间内 class TreeNode(object):def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right
def rangeSumBST(root, low, high)::type root: TreeNode:type low: int:type high: int:rtype: intdef dfs(node):ret 0if node.vallow:if node.left:ret dfs(node.left)if node.vallow and node.valhigh:retnode.valif node.valhigh:if node.right:ret dfs(node.right)return retreturn dfs(root) 2/27 2867. 统计树中的合法路径数目 欧拉筛筛选质数 以质数节点为根 深搜所有非质数的子树 求字数大小 任意两个不同子树节点 路径都通过质数根节点 只有一个节点为质数 符合题意 def countPaths(n, edges)::type n: int:type edges: List[List[int]]:rtype: intprime[]isprime [True]*(n1)isprime[1]Falsefor i in range(2,n1):if isprime[i]:prime.append(i)for p in prime:if p*in:breakisprime[p*i]Falseif i%p0:breakm[[] for _ in range(n1)]for i,j in edges:m[i].append(j)m[j].append(i)global seendef dfs(i,pre):global seenseen.append(i)for j in m[i]:if j!pre and not isprime[j]:dfs(j,i)ans 0cnt[0]*(n1)for i in range(1,n1):if not isprime[i]:continuecur 0for j in m[i]:if isprime[j]:continueif cnt[j]0:seen []dfs(j,0)for k in seen:cnt[k] len(seen)anscnt[j]*curcurcnt[j]anscurreturn ans 2/28 2673. 使二叉树所有路径值相等的最小代价 满二叉树有n个节点 那么存在(n1)//2个叶子节点 对于两个兄弟叶子节点 除了改变其自身 无法改变两个节点路径和的差值 所以将小的叶子节点增加到大的即可 改完叶子节点 将叶子节点的值增加到父节点中 依旧考虑父节点和叔节点的情况 def minIncrements(n, cost)::type n: int:type cost: List[int]:rtype: intans0for i in range(n-2,0,-2):ans abs(cost[i]-cost[i1])cost[i//2] max(cost[i],cost[i1])return ans 2/29 2581. 统计可能的树根数目 首先计算以0位根节点时猜对的个数cnt 当根节点从0换到其某个子节点x时 除了0,x的父子关系发生变化 其他没有变化 所以如果此时(0,x)在猜测中 则cnt-1 如果(x,0)在猜测中 则cnt1 遇到cntk 则ans1 def rootCount(edges, guesses, k)::type edges: List[List[int]]:type guesses: List[List[int]]:type k: int:rtype: intg[[] for _ in range(len(edges)1)]for x,y in edges:g[x].append(y)g[y].append(x)s {(x,y) for x,y in guesses}global cnt,ansans 0cnt 0def dfs(x,p):global cntfor y in g[x]:if y!p:cnt (x,y) in sdfs(y,x)dfs(0,-1)def reroot(x,p,cnt):global ansif cntk:ans1for y in g[x]:if y!p:reroot(y,x,cnt-((x,y) in s) ((y,x) in s))reroot(0,-1,cnt)return ans 3/1 2369. 检查数组是否存在有效划分 dp[i1]判断是否能够有效划分0~i def validPartition(nums)::type nums: List[int]:rtype: boolnlen(nums)dp[False]*(n1)dp[0]Truefor i,x in enumerate(nums):if (i0 and dp[i-1] and xnums[i-1]) or (i1 and dp[i-2] and (xnums[i-1]nums[i-2] or xnums[i-1]1nums[i-2]2)):dp[i1]Truereturn dp[n] 3/2 2368. 受限条件下可到达节点的数目 不考虑受限的节点 建图 DFS搜索 def reachableNodes(n, edges, restricted)::type n: int:type edges: List[List[int]]:type restricted: List[int]:rtype: ints set(restricted)m [[] for _ in range(n)]for x,y in edges:if x not in s and y not in s:m[x].append(y)m[y].append(x)def dfs(x,f):cnt 1for y in m[x]:if y!f:cnt dfs(y,x)return cntreturn dfs(0,-1) 3/3
