古狗新鲜VO挂经

SSGEZREAL 发表于 2022-5-4 14:33
继续第三题 我想了一下其实这就是个二维版的painting area every day 对于某一行或者某一列来说用maintain ...

第三题这个解法靠谱，简单分析了下，不知道对不对
按level排列是nlogn
遍历长方形的时候merge 每一行的covered 1D intervals
并且累加面积
复杂度是kn，由于窗口大小固定，k小于某个常数
所以nlogn+kn?

求问bq问了啥？谢谢楼主～

匿名者 发表于 2022-5-5 11:32
求问bq问了啥？谢谢楼主～

BQ很常规的, 没有特别的坑感觉, 比如说 同事之间take了不属于你的credit你怎么处理. 怎么处理和同事之间的不同意见之类的..

第三题不是二维线段树么？先按level 从下到上排序。每个长方形就是对应线段树的node的set操作。可以采用懒标记，只有pushdown的时候更新之前被覆盖的长方形的面积。

第三題想了一下, 應該算 LC 2158 的變種吧 , 2D 的 2158
2158 有一種解法是用 把每一個區間的點當成 key, 然後 end 的點存成 value, 這樣就可以避免重複
->
class Solution:
    def amountPainted(self, paint: List[List[int]]) -> List[int]:
        ans = []
        seen = {}
        for start, end in paint:
            cnt = 0
            while start < end:
                if start in seen:
                    start = seen[start]
                else:
                    seen[start] = end
                    cnt += 1
                    start += 1
            ans.append(cnt)
        return ans

所以應該只要把每一個 row 當成一個 2158 的 1D array,  然後 sort window array, 讓 size 數字越大的越先處理, 這樣應該可以更簡化一些 ?
def findAllSquare(self, squares: list, windows: List[List[int]]):
    # each item in squares is like [(startx, starty), (endx, endy), size]
    record = defaultdict(int)
    squares.sort(key=lambda x: -x[2])
    counter = defaultdict(int)
    for i, s in enumerate(squares):
        endy = s[1][1]
        j = s[0][1]
        for i in range(s[0][0], s[1][0]+1):
            while j <= s[1][1]:
                if (i, j) in record: # 已經有更大的size 直接跳到 結束的點
                    j = record[(i,j)]
                else:
                    windows[i][j] = s[2] # 還沒有更大的size, record當前的size
                    record[(i,j)] = endy+1
    for i in range(len(windows)):
        for j in range(len(windows[0])):
            counter[windows[i][j]] += 1
    return counter

第四题我连LC答案都看的晕乎。。。这难度QAQ 是在下太菜了

SSGEZREAL 发表于 2022-5-5 04:33
继续第三题 我想了一下其实这就是个二维版的painting area every day 对于某一行或者某一列来说用maintain ...

同意, 感覺這應該是最優解