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

---

12/4 1038. 从二叉搜索树到更大和树

根据题目即 每个节点的值加上其右子树节点综合

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def bstToGst(root):""":type root: TreeNode:rtype: TreeNode"""def dfs(node,fvalue):if not node:return fvaluerv=dfs(node.right,fvalue)node.val+=rvlv=dfs(node.left,node.val)return lvdfs(root,0)return root

---

12/5 2477. 到达首都的最少油耗

dfs 对于某一节点
为了省油 我们需要将其子路径上的节点汇聚到这个节点中 坐满车 再向终点前进

def minimumFuelCost(roads, seats):""":type roads: List[List[int]]:type seats: int:rtype: int"""from collections import defaultdictg = defaultdict(list)for a,b in roads:g[a].append(b)g[b].append(a)global ansans = 0def dfs(cur,p):global anss = 1for nxt in g[cur]:if nxt!=p:cnt = dfs(nxt,cur)s += cntans +=(cnt+seats-1)//seatsreturn sdfs(0,-1)return ans

---

12/6 2646. 最小化旅行的价格总和

dfs 先统计所有路径中各个节点的贡献次数
ans[0] ans[1]表示该节点保持不变 和 减半的值
如果该节点减半 则相邻节点不能减半

def minimumTotalPrice(n, edges, price, trips):""":type n: int:type edges: List[List[int]]:type price: List[int]:type trips: List[List[int]]:rtype: int"""ch = [[] for _ in range(n)]for e in  edges:ch[e[0]].append(e[1])ch[e[1]].append(e[0])cnt = [0]*ndef dfs(node,p,end):if node==end:cnt[node]+=1return Truefor c in ch[node]:if c==p:continueif dfs(c,node,end):cnt[node]+=1return Truereturn Falsefor x,y in trips:dfs(x,-1,y)def dp(node,p):ans = [price[node]*cnt[node],price[node]*cnt[node]//2]for c in ch[node]:if c==p:continue[x,y] = dp(c,node)ans[0],ans[1] = ans[0]+min(x,y),ans[1]+xreturn ansreturn min(dp(0,-1))

---

12/7 1466. 重新规划路线

因为路径为单向 所有点能到0
可以从0开始 考虑能够到达0的点
dfs

def minReorder(n, connections):""":type n: int:type connections: List[List[int]]:rtype: int"""e = [[] for _ in range(n)]for ed in connections:e[ed[0]].append((ed[1],1))e[ed[1]].append((ed[0],0))def dfs(x,p):ans = 0for ed in e[x]:if ed[0]==p:continueans += ed[1]+dfs(ed[0],x)return ansreturn dfs(0,-1)

---

12/8 2008. 出租车的最大盈利

用哈希表m[end]记录终点为end的所有乘客信息
dpi记录到达第i个地点是的最大盈利
dp[i] = max(dp[i-1],dp[startj]+endj-startj+tipj)

def maxTaxiEarnings(n, rides):""":type n: int:type rides: List[List[int]]:rtype: int"""m={}dp = [0]*(n+1)for r in rides:if r[1] not in m:m[r[1]]=[]m[r[1]].append(r)for i in range(1,n+1):dp[i] = dp[i-1]if i not in m:continuefor r in m[i]:dp[i] = max(dp[i],dp[r[0]]+r[1]-r[0]+r[2])return dp[n]

---

12/9 2048. 下一个更大的数值平衡数

在范围内 平衡数是有限的
二分查找比n大的值

def nextBeautifulNumber( n):""":type n: int:rtype: int"""values = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444,14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332,33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555,122333, 123233, 123323, 123332, 132233, 132323, 132332,133223, 133232, 133322, 155555, 212333, 213233, 213323,213332, 221333, 223133, 223313, 223331, 224444, 231233,231323, 231332, 232133, 232313, 232331, 233123, 233132,233213, 233231, 233312, 233321, 242444, 244244, 244424,244442, 312233, 312323, 312332, 313223, 313232, 313322,321233, 321323, 321332, 322133, 322313, 322331, 323123,323132, 323213, 323231, 323312, 323321, 331223, 331232,331322, 332123, 332132, 332213, 332231, 332312, 332321,333122, 333212, 333221, 422444, 424244, 424424, 424442,442244, 442424, 442442, 444224, 444242, 444422, 515555,551555, 555155, 555515, 555551, 666666, 1224444]l,r=0,len(values)-1while l<r:mid = (l+r)>>1if values[mid]<=n:l=mid+1else:r=midreturn values[l]

---

12/10 70. 爬楼梯

一次爬1或2 对于位置n来说 可以由n-1或n-2过来
所以记录前两次的方法 当前位置是前两次相加

def climbStairs(n):""":type n: int:rtype: int"""pre = 0now = 1for i in range(n):next = now + prepre = nownow = nextreturn now

---