LeetCode 每日一题 2024/2/26-2024/3/3

记录了初���解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

目录

• • • 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, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightdef rangeSumBST(root, low, high):    """    :type root: TreeNode    :type low: int    :type high: int    :rtype: int    """    def dfs(node):        ret = 0        if node.val>low:            if node.left:                ret = dfs(node.left)        if node.val>=low and node.val=k 则ans+1  
      def rootCount(edges, guesses, k):    """    :type edges: List[List[int]]    :type guesses: List[List[int]]    :type k: int    :rtype: int    """    g=[[] 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,ans    ans = 0    cnt = 0    def dfs(x,p):        global cnt        for y in g[x]:            if y!=p:                cnt += (x,y) in s                dfs(y,x)    dfs(0,-1)        def reroot(x,p,cnt):        global ans        if cnt>=k:            ans+=1        for 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[i+1]判断是否能够有效划分0~i
        
      def validPartition(nums):    """    :type nums: List[int]    :rtype: bool    """    n=len(nums)    dp=[False]*(n+1)    dp[0]=True    for i,x in enumerate(nums):        if (i>0 and dp[i-1] and x==nums[i-1]) or (i>1 and dp[i-2] and (x==nums[i-1]==nums[i-2] or x==nums[i-1]+1==nums[i-2]+2)):            dp[i+1]=True    return dp[n]
       
      3/2 2368. 受限条件下可到达节点的数目
         
      不考虑受限的节点 建图
      DFS搜索
        
      def reachableNodes(n, edges, restricted):    """    :type n: int    :type edges: List[List[int]]    :type restricted: List[int]    :rtype: int    """    s = 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 = 1        for y in m[x]:            if y!=f:                cnt += dfs(y,x)        return cnt    return dfs(0,-1)        
       
      3/3