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

---

5/22 1080. 根到叶路径上的不足节点

dfs记录子树叶到根最大值

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def sufficientSubset(root, limit):""":type root: TreeNode:type limit: int:rtype: TreeNode"""def dfs(node,pre):if node==None:return Falseif not node.left and not node.right:return node.val+pre>=limitleft = dfs(node.left,pre+node.val)right = dfs(node.right,pre+node.val)if not left:node.left = Noneif not right:node.right = Nonereturn left or rightv = dfs(root,0)return root if v else None

---

5/23 1090. 受标签影响的最大值

大顶堆 每次取最大value值
记录当前labal数量是否可用

def largestValsFromLabels(values, labels, numWanted, useLimit):""":type values: List[int]:type labels: List[int]:type numWanted: int:type useLimit: int:rtype: int"""from collections import defaultdictimport heapql = [(-values[i],labels[i]) for i in range(len(values))]heapq.heapify(l)mem = defaultdict(int)ans = 0while numWanted>0 and len(l)>0:v,lab = heapq.heappop(l)v = -vif mem[lab]<useLimit:ans +=vmem[lab]+=1numWanted-=1return ans

---

5/24 1377. T 秒后青蛙的位置

dfs 深搜
m[i]记录从i节点能够到达的后续节点
如果跳跃时间为0 或者后续无节点
判断当前节点是否为目标
nxt为后续可以选择的个数

def frogPosition(n, edges, t, target):""":type n: int:type edges: List[List[int]]:type t: int:type target: int:rtype: float"""from collections import defaultdictm = defaultdict(list)for i,j in edges:m[i].append(j)m[j].append(i)mem = [0]*(n+1)def dfs(node,t):nxt = len(m[node])if node>1:nxt -=1if nxt==0 or t==0:return 1 if node==target else 0mem[node] = 1for j in m[node]:if not mem[j]:p = dfs(j,t-1)if p>0:return p*1.0/nxtreturn 0return dfs(1,t)

---

5/25 2451. 差值数组不同的字符串

遍历

def oddString(words):""":type words: List[str]:rtype: str"""def check(w):diff = [0]*(len(w)-1)for i in range(len(w)-1):diff[i] = ord(w[i+1])-ord(w[i])return diffd0 = check(words[0])d1 = check(words[1])if d0==d1:for i in range(2,len(words)):if d0!=check(words[i]):return words[i]return words[0] if d1==check(words[2]) else words[1] 

---

5/26 1091. 二进制矩阵中的最短路径

BFS 广搜
记录每个点是否经过

def shortestPathBinaryMatrix(grid):""":type grid: List[List[int]]:rtype: int"""from collections import defaultdictn=len(grid)if grid[0][0]==1 or grid[n-1][n-1]==1:return -1m = defaultdict(int)l = [(0,0)]m[(0,0)]=1step = [(1,0),(0,1),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]while l:tmp = []for x,y in l:for i,j in step:nx,ny = x+i,y+jif 0<=nx<n and 0<=ny<n and grid[nx][ny]==0:if nx==n-1 and ny==n-1:return m[(x,y)]+1if m[(nx,ny)]==0 :tmp.append((nx,ny))m[(nx,ny)]=m[(x,y)]+1l=tmpreturn -1 if m[(n-1,n-1)]==0 else m[(n-1,n-1)]

---

5/27

---

5/28

---