阿泳在快乐星球
0%

每日一题

发表于

每日一题

每日一题（尽量哈哈）

4.24/2385. 感染二叉树需要的总时间

最开始是想只统计父亲节点来做的，后来发现有一些样例会超时，官解给出的做法是作图（热题100中没有使用过这种技巧）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        graph = defaultdict(list)
        def dfs(node):
            for child in [node.left,node.right]:
                if child:
                    graph[node.val].append(child.val)
                    graph[child.val].append(node.val)
                    dfs(child)
        dfs(root)
        # print(graph)
        q = deque([[start,0]])
        visited = set([start])
        time = 0
        while q:
            nodeVal, time = q.popleft()
            for childval in graph[nodeVal]:
                if childval not in visited:
                    q.append([childval,time+1])
                    visited.add(childval)
            # print(q)
        # print(visited)
        return time

5.10/2960. 统计已测试设备

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countTestedDevices(self, batteryPercentages: List[int]) -> int:
        count = 0
        i=0
        while i<len(batteryPercentages):
            if batteryPercentages[i]>0:
                count+=1
                for j in range(i+1,len(batteryPercentages)):
                    batteryPercentages[j] = max(batteryPercentages[j]-1,0)
                i+=1
            else:
                i+=1
        return count

5.11/2391. 收集垃圾的最少总时间

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        M_c,P_c,G_c = 0,0,0
        M_t,P_t,G_t = 0,0,0
        for i,word in enumerate(garbage):
            for ch in word:
                if ch == "M":
                    M_c+=1
                    M_t = i
                if ch == "P":
                    P_c+=1
                    P_t = i
                if ch == "G":
                    G_c+=1
                    G_t = i
        for i in range(M_t):
            M_c+=travel[i]
        for i in range(P_t):
            P_c+=travel[i]
        for i in range(G_t):
            G_c+=travel[i]
        return M_c+P_c+G_c

5.23/2831. 找出最长等值子数组

滑动窗口：使用hash表记录每个元素出现的位置，之后对于每个元素而言，其最长子数组构成遍历为两个元素的位置（数组的长度）-两个元素邻接的位置（两个元素之间有多少个相同的元素了）=需要删除的元素数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        pos = defaultdict(list)
        for i, num in enumerate(nums):
            pos[num].append(i)

        ans = 0
        for vec in pos.values():
            j = 0
            for i in range(len(vec)):
                # 缩小窗口，直到不同元素数量小于等于 k 
                while vec[i] - vec[j] - (i - j) > k:
                    j += 1
                ans = max(ans, i - j + 1)

        return ans