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

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

---

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

后序遍历

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class 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 None
            val = l.pop()
            node = TreeNode(val)
            node.right = build(val,maxv)
            node.left = build(minv,val)
            return node
        return build(-1,10001)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

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+b
    else:
        return b*10+a



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

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*cars
    while l+1<r:
        mid = (l+r)//2
        if sum([floor(sqrt(mid//r)) for r in ranks])>=cars:
            r = mid
        else:
            l = mid
    return r


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

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

24小时制

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

1
2
3
4
5
6
7
8
9

---

9/9 207. 课程表

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

def canFinish(numCourses, prerequisites):
    """
    :type numCourses: int
    :type prerequisites: List[List[int]]
    :rtype: bool
    """
    from collections import defaultdict
    if len(prerequisites)==0:
        return True
    classlist = [] #
    afterclass = defaultdict(set) 
    preclass = {x:0 for x in range(numCourses)}
       
    for cls,pre in prerequisites:
        afterclass[cls].add(pre)
        preclass[pre] += 1

    for key in preclass:
        if preclass[key]==0:
            classlist.append(key)
    ans=0
    while classlist:
        tmp = classlist.pop(0)
        ans +=1
        for aftercls in afterclass[tmp]:
            preclass[aftercls] -=1
            if preclass[aftercls]==0:
                classlist.append(aftercls)
    return ans==numCourses    


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

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 defaultdict
    if 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] += 1
        if 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] -=1
            if preclass[aftercls]==0:
                classlist.append(aftercls)
    return order if len(order)==numCourses else []


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---