LeetCode 每日一题 2023/9/4-2023/9/10

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

---

9/4 449. 序列化和反序列化二叉搜索树

后序遍历

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Codec:def serialize(self, root: TreeNode) -> str:"""Encodes a tree to a single string."""ans = []def find(node):if node:find(node.left)find(node.right)ans.append(node.val)find(root)return " ".join(map(str,ans))def deserialize(self, data: str) -> TreeNode:"""Decodes your encoded data to tree."""l = list(map(int,data.split()))def build(minv,maxv):if l==[] or l[-1]<minv or l[-1]>maxv:return Noneval = l.pop()node = TreeNode(val)node.right = build(val,maxv)node.left = build(minv,val)return nodereturn build(-1,10001)

---

9/5 2605. 从两个数字数组里生成最小数字

先取两个交集的最小值 如果不存在交集
去两个数组最小值组成一个两位数

def minNumber(nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: int"""l = list(set(nums1)&set(nums2))if len(l)>0:return min(l)a,b=min(nums1),min(nums2)if a<b:return a*10+belse:return b*10+a

---

9/6 1123. 最深叶节点的最近公共祖先

dfs 记录各个节点深度
如果左右子树深度都是最深则当前节点为要求节点

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def lcaDeepestLeaves(root):""":type root: TreeNode:rtype: TreeNode"""ans=Nonemaxd = -1def dfs(node,dep):global ans,maxdif not node:maxd = max(maxd,dep)return depleft = dfs(node.left,dep+1)right = dfs(node.right,dep+1)if left==right==maxd:ans = nodereturn max(left,right)dfs(root,0)return ans

---

9/7 2594. 修车的最少时间

二分查找 最多用时min(ranks)*cars^2

def repairCars(ranks, cars):""":type ranks: List[int]:type cars: int:rtype: int"""from math import floor,sqrt l,r=0,min(ranks)*cars*carswhile l+1<r:mid = (l+r)//2if sum([floor(sqrt(mid//r)) for r in ranks])>=cars:r = midelse:l = midreturn r

---

9/8 2651. 计算列车到站时间

24小时制

def findDelayedArrivalTime(arrivalTime, delayedTime):""":type arrivalTime: int:type delayedTime: int:rtype: int"""return (arrivalTime+delayedTime)%24

---

9/9 207. 课程表

bfs classlist存储当前可以学习的课程
afterclass 存储这门课的后续课程
preclass 存储这门课的条件课程数量

def canFinish(numCourses, prerequisites):""":type numCourses: int:type prerequisites: List[List[int]]:rtype: bool"""from collections import defaultdictif len(prerequisites)==0:return Trueclasslist = [] #afterclass = defaultdict(set) preclass = {x:0 for x in range(numCourses)}for cls,pre in prerequisites:afterclass[cls].add(pre)preclass[pre] += 1for key in preclass:if preclass[key]==0:classlist.append(key)ans=0while classlist:tmp = classlist.pop(0)ans +=1for aftercls in afterclass[tmp]:preclass[aftercls] -=1if preclass[aftercls]==0:classlist.append(aftercls)return ans==numCourses    

---

9/10 210. 课程表 II

bfs classlist存储当前可以学习的课程
afterclass 存储这门课的后续课程
preclass 存储这门课的条件课程数量

def findOrder(numCourses, prerequisites):""":type numCourses: int:type prerequisites: List[List[int]]:rtype: List[int]"""from collections import defaultdictif len(prerequisites)==0:return [x for x in range(numCourses)]classlist = [] #存储当前可以学习的课程afterclass = defaultdict(set) #存储这门课的后续课程preclass = {x:0 for x in range(numCourses)}#存储这门课的条件课程数量firstset = set(range(numCourses))for cls,pre in prerequisites:afterclass[pre].add(cls)preclass[cls] += 1if cls in firstset:firstset.remove(cls)classlist = list(firstset)order = []while classlist:tmp = classlist.pop(0)order.append(tmp)for aftercls in afterclass[tmp]:preclass[aftercls] -=1if preclass[aftercls]==0:classlist.append(aftercls)return order if len(order)==numCourses else []

---