2020 第25周 LeetCode 记录

发表于 |

1476. Subrectangle Queries

二维数组的更新与查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class SubrectangleQueries:

    def __init__(self, rectangle: List[List[int]]):
        self.rect = rectangle
        self.rows, self.cols = len(self.rect), len(self.rect[0])

    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        for i in range(row1, row2 + 1):
            for j in range(col1, col2 + 1):
                self.rect[i][j] = newValue

    def getValue(self, row: int, col: int) -> int:
        return self.rect[row][col]



# Your SubrectangleQueries object will be instantiated and called as such:
# obj = SubrectangleQueries(rectangle)
# obj.updateSubrectangle(row1,col1,row2,col2,newValue)
# param_2 = obj.getValue(row,col)

1480. Running Sum of 1d Array

统计动态和，始终用一个变量记录当前值，遍历。

1
2
3
4
5
6
7
8
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        res = []
        sum = 0
        for i in nums:
            sum += i
            res.append(sum)
        return res

1481. Least Number of Unique Integers after K Removals

对 arr 中出现数字的次数进行统计，并按照升序进行排序，遍历排序后的结果，如果 sum + elem_v 小于等于 k，那么表示此时还可以继续删除数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        res = dict(Counter(arr))
        res = sorted(res.items(),key=lambda item:item[1])
        sum = 0
        len_elem = len(res)
        for (elem_k,elem_v) in res:
            if sum + elem_v <= k:
                len_elem -=1
                sum += elem_v
            else:
                break
        return len_elem

1482. Minimum Number of Days to Make m Bouquets

对所有天数进行排序，使用二分法判断是否满足，其中判断是否可以组成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
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if n < m * k:
            return -1
        def count(day: int):
            num = sums = 0
            for i in range(n):
                if num >= m:
                    break
                if bloomDay[i] <= day:
                    sums += 1
                else:
                    sums = 0
                if sums == k:
                    num += 1
                    sums = 0
            return num >= m
        days = sorted(set(bloomDay))
        l, r = 0, len(days)-1
        while l < r:
            mid = l + (r - l) // 2
            if count(days[mid]):
                r = mid
            else:
                l = mid + 1
        return days[l]

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

题目描述不清楚，我理解是 dfs ，只是传入的是两个 Tree，判断符合条件后直接返回另一个 Tree Node。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        def traverse(original, cloned, target):
            if not original or not cloned:
                return None
            
            if original == target:
                return cloned
            
            return traverse(original.left, cloned.left, target) or \
                traverse(original.right, cloned.right, target)
        return traverse(original, cloned, target)