LeetCode 每日一题 2022/8/15-2022/8/21

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

---

8/15 641. 设计循环双端队列

长度为k的数组 头尾指针fr,la

class MyCircularDeque(object):

    def __init__(self, k):
        """
        :type k: int
        """
        self.num = 0
        self.l = [-1]*k
        self.k = k


    def insertFront(self, value):
        """
        :type value: int
        :rtype: bool
        """
        if self.num == self.k:
            return False
        if self.num == 0:
            self.l[0] = value
            self.fr = 0
            self.la = 0
        else:
            self.fr = (self.fr-1)%self.k
            self.l[self.fr] = value
        self.num +=1
        return True


    def insertLast(self, value):
        """
        :type value: int
        :rtype: bool
        """
        if self.num == self.k:
            return False
        if self.num == 0:
            self.l[0] = value
            self.fr = 0
            self.la = 0
        else:
            self.la = (self.la+1)%self.k
            self.l[self.la] = value
        self.num +=1
        return True


    def deleteFront(self):
        """
        :rtype: bool
        """
        if self.num == 0:
            return False
        self.fr = (self.fr+1)%self.k
        self.num -=1
        return True


    def deleteLast(self):
        """
        :rtype: bool
        """
        if self.num == 0:
            return False
        self.la = (self.la-1)%self.k
        self.num -=1
        return True


    def getFront(self):
        """
        :rtype: int
        """
        if self.num == 0:
            return -1
        return self.l[self.fr]


    def getRear(self):
        """
        :rtype: int
        """
        if self.num == 0:
            return -1
        return self.l[self.la]



    def isEmpty(self):
        """
        :rtype: bool
        """
        return self.num==0


    def isFull(self):
        """
        :rtype: bool
        """
        return self.num==self.k


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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

---

8/16 1656. 设计有序流

数组保存数据 插入数据后
检查指针节点是否可以往后移动

class OrderedStream(object):

    def __init__(self, n):
        """
        :type n: int
        """
        self.n = n
        self.ptr = 0
        self.l = [""]*(n+1)


    def insert(self, idKey, value):
        """
        :type idKey: int
        :type value: str
        :rtype: List[str]
        """
        ans = []
        self.l[idKey] = value
        while self.ptr<self.n and self.l[self.ptr+1]!="":
            ans.append(self.l[self.ptr+1])
            self.ptr +=1
            if self.ptr>self.n:
                break
        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
26
27

---

8/17 1302. 层数最深叶子节点的和

BFS 记录当前层的和

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def deepestLeavesSum(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    ans = 0
    l = [root]
    while l:
        tmp = []
        ans = 0
        for node in l:
            ans += node.val
            if node.left:
                tmp.append(node.left)
            if node.right:
                tmp.append(node.right)
        l = tmp
    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
26

---

8/18 1224. 最大相等频率

num记录数值出现的次数
fre记录数值出现次数的频率
maxfre记录当前最大的频率
如果maxfre=1 则之后删除任意一个数都满足
如果只有一个maxfre 其他都是maxfre-1 则删除出现最多的一个
如果有一个数只出现一次 其他都是maxfre 则删除出现一次的数

def maxEqualFreq(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    num,fre = {},{}
    ans = 1
    maxfre = 0
    for i,v in enumerate(nums):
        if v in num:
            fre[num[v]]-=1
        num[v] = num.get(v,0)+1
        maxfre = max(maxfre,num[v])
        fre[num[v]] = fre.get(num[v],0)+1
        if maxfre ==1:
            ans = i+1
        if fre[maxfre]==1 and maxfre+fre.get(maxfre-1,0)*(maxfre-1)==i+1:
            ans = i+1
        if fre.get(1,0)==1 and fre[maxfre]*maxfre+1==i+1:
            ans = i+1
    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

---

8/19 1450. 在既定时间做作业的学生人数

从头开始累加 直到查询时间点
开始时间点+1 结束时间点-1

def busyStudent(startTime, endTime, queryTime):
    """
    :type startTime: List[int]
    :type endTime: List[int]
    :type queryTime: int
    :rtype: int
    """
    ans = 0
    for s in startTime:
        if s<=queryTime:
            ans +=1
    for e in endTime:
        if e<queryTime:
            ans -=1
    return ans


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

---

8/20 654. 最大二叉树

递归 找出当前数组中最大值及其位置loc
[:loc]为左子树
[loc+1:]为右子树

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def constructMaximumBinaryTree(nums):
    """
    :type nums: List[int]
    :rtype: TreeNode
    """        
    def dfs(l):
        if len(l)==0:
            return None
        loc = -1
        maxv = float("-inf")
        for i,v in enumerate(l):
            if v>maxv:
                loc = i
                maxv = v
        node = TreeNode(maxv)
        node.left = dfs(l[:loc])
        node.right = dfs(l[loc+1:])
        return node
    return dfs(nums)


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

---

8/21 1455. 检查单词是否为句中其他单词的前缀

分割句子 检查每个单词

def isPrefixOfWord(sentence, searchWord):
    """
    :type sentence: str
    :type searchWord: str
    :rtype: int
    """
    l = sentence.split(" ")
    for loc,v in enumerate(l):
        if v.startswith(searchWord):
            return loc+1
    return -1


1
2
3
4
5
6
7
8
9
10
11
12
13

---