刷题记录合辑

标题不含题号，题号写在正文与 description 中。

759. 员工空闲时间

思路
代码
题解

思路
尝试1: 使用差分数组
题解: 合并数组模板

这个是差分数组的做法
首先使用差分数组统计出每个点的位置，然后统计对应位置元素等于员工数量的区间
这个是稀疏差分数组的实现，由于我们并不查询某个点而是要求要有的区间的内容，所以这个完全可以够我们用

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

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        d = {}
        for emp in schedule:
            for interval in emp:
                start = interval.start
                end = interval.end
                if start not in d:
                    d[start] = 0 
                d[start] += 1
                
                if end not in d:
                    d[end] = 0
                d[end] -= 1
        curr = 0
        res = []
        l = -1
        for t in sorted(d):
            curr += d[t]
            
            if curr == 0:
                if l == -1:
                    l = t
            elif l != -1:
                res.append(Interval(l,t))
                l = -1
        return res

这个题解是用排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        q = []
        heapq.heapify(q)
        for idx, emp in enumerate(schedule):
            for sch in emp:
                heapq.heappush(q, (sch.start, idx, sch))
        # 此时我们得到一个用start来排序的区间堆
        res = []
        current_end = q[0][2].end
        while q:
            top = heapq.heappop(q)[2]
            if top.start > current_end:
                res.append(Interval(current_end,top.start))
            if current_end < top.end: 
                current_end = top.end
        
        return res

这题需要用到python的堆，所以我们学一下python的堆实现:

Stellar heapq

{}
总结

这题使用差分数组是可以的，以下是差分数组的内容:

Stellar 差分数组

使用场景: 对于一个初始数组nums，对其中区间进行多次加减运算，输出最终得到的数组

title:差分数组模板

常规模板
稀疏优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def apply_range_updates(n, updates):
    """
    初始化长度为 n 的数组，应用差分更新，返回最终数组结果。
    
    :param n: 数组长度
    :param updates: 区间更新列表，每项为 (start, end, delta)，含义是对 [start, end] 区间加上 delta
    :return: 应用完所有更新后的数组
    """
    diff  = [0] * (n+2)
    for start, end, delta in updates:
        diff[start] += delta
        diff[end+1] -= delta
    res = [0]*n
    curr = 0
    for i in range(n):
        curr += diff[i]
        res[i] = curr

    return res

这个方法适用于只需要查询完整的区间而不是单个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import defaultdict
# 这里是使用了字典来处理稀疏优化，但是这样似乎没有统计所有正确的res

def sparse_diff_add(events):
    """
    :param events: 每项为 (start, end)，对 [start, end) 范围加1
    :return: 前缀和后每个时间点的在岗人数映射
    """
    # 这里使用初始化，直接diff = {} 得到的也是同样的效果 
    diff = defaultdict(int)

    for start, end in events:
        diff[start] += 1
        diff[end] -= 1

    res = {}
    curr = 0
    for t in sorted(diff.keys()):
        curr += diff[t]
        res[t] = curr

    return res

这题需要用到python的堆，所以我们学一下python的堆实现:

Stellar heapq

需要import heapq

函数 作用 示例
heapq.heappush(heap, item) 将 item 压入堆中 heappush(h, 3)
heapq.heappop(heap) 弹出并返回堆中最小元素 x = heappop(h)
heapq.heapify(list) 将一个普通列表原地转为堆 heapify(h)
heapq.heappushpop(heap, item) 先 push 再 pop（比先 push 后 pop 更快） heappushpop(h, 4)
heapq.heapreplace(heap, item) 弹出最小元素后 push 新元素（原地） heapreplace(h, 5)
heapq.nlargest(k, iterable) 找出前 k 个最大元素（不需要堆） nlargest(2, [1,8,3])
heapq.nsmallest(k, iterable) 找出前 k 个最小元素 nsmallest(2, [1,8,3])
经常用到的是heapify， 默认小根堆
如果需要自定义类比来实现，使用List来实现
为了避免出现无法比较的情况我们应该给每一个点一个唯一标签 
1
heapq.heappush(heap, (node.val, i, node))

相关题目

*

知识点小结

*

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。