LC 253 会议室2

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1

var minMeetingRooms = function (intervals) {
    const n = intervals.length;
    // 按照开始时间排序
    intervals.sort((a, b) => a[0] - b[0])

    let minQueue = new MinPriorityQueue();
    minQueue.enqueue(intervals[0][1]); // 现将第一个会议的结束时间入heap
    // 当遍历到下一个会议时，只关注是否有会议室空闲出来
    for (let i = 1; i < n; i++) {
        const [s, e] = intervals[i];
        // 当minqueue里堆顶元素的结束时间早于当前startTime，则意味着会议室空闲出来一间，则先将它移除heap
        if (minQueue.size() && minQueue.front().element <= s) {
            minQueue.dequeue();
        }
        // 最后将自己入heap
        minQueue.enqueue(e)
    }
    return minQueue.size()
};

// 第二种方案，直接一遍扫描，按照开始时间和结束时间，分别维护两个指针
var minMeetingRooms = function (intervals) {
    const n = intervals.length;
    const start = intervals
        .sort((a, b) => a[0] - b[0])
        .slice()
        .map((ele) => ele[0]);
    const end = intervals
        .sort((a, b) => a[1] - b[1])
        .slice()
        .map((ele) => ele[1]);
    let s = 0,
        e = 0; // 两个指针分别指向start和end两个数组
    let res = 0;
    while (s < n) {
        // 当前释放出了空闲会议室
        if (start[s] >= end[e]) {
            res -= 1;
            e++;
        }
        // 无论房间是否空闲，s指针都要去查看下一个会议，并且新增一个房间
        res += 1;
        s++;
    }
    return res;
};

LC 362 敲击计数器
设计一个敲击计数器，使它可以统计在过去 5 分钟内被敲击次数。（即过去 300 秒）

您的系统应该接受一个时间戳参数 timestamp (单位为 秒 )，并且您可以假定对系统的调用是按时间顺序进行的(即 timestamp 是单调递增的)。几次撞击可能同时发生。

实现 HitCounter 类:

HitCounter() 初始化命中计数器系统。
void hit(int timestamp) 记录在 timestamp ( 单位为秒 )发生的一次命中。在同一个 timestamp 中可能会出现几个点击。
int getHits(int timestamp) 返回 timestamp 在过去 5 分钟内(即过去 300 秒)的命中次数。

var HitCounter = function() {
    this.count = 0
    this.queue = [] // 双端队列，优化同个timestamp可能出现过多次数
};

HitCounter.prototype.hit = function(timestamp) {
    if(this.queue.length && timestamp === this.queue[this.queue.length - 1][0]){
        // 如果与队尾元素一样，则将队尾元素cnt+1，重新入队
        const [t, c] = this.queue.pop()
        this.queue.push([t, c + 1])
    }else{
        this.queue.push([timestamp, 1])
    }
    this.count += 1
};

HitCounter.prototype.getHits = function(timestamp) {
    while(this.queue.length && timestamp - this.queue[0][0] >= 300){
        const [t, c] = this.queue.shift()
        this.count -= c
    }
    return this.count
};

LC 366 收集叶子结点
给你一棵二叉树，请按以下要求的顺序收集它的全部节点：

依次从左到右，每次收集并删除所有的叶子节点
重复如上过程直到整棵树为空
输入: [1,2,3,4,5]

      1
     / \
    2   3
   / \     
  4   5

输出: [[4,5,3],[2],[1]]

var findLeaves = function(root) {
    const res = []

    const dfs = (root) => {
        if(!root) return -1 // 对于null返回-1高度
        const left = dfs(root.left)
        const right = dfs(root.right)
        const height = Math.max(left, right) + 1
        if(res[height] ===  undefined) res[height] = new Array()
        res[height].push(root.val)
        return height
    }

    dfs(root)
    return res
};

1062 最长重复子串
这题可以使用动态规划来完成，思路和最长公共子串类似。

var longestRepeatingSubstring = function(s) {
    const n = s.length
    const f = new Array(n).fill(0).map(()=>new Array(n).fill(0))
    let res = 0
    // f[i][j]表示以s[i]结尾与s[j]结尾的相同子串的最大长度，i < j
    for(let i = 0; i < n; i++){
        if(s[0] === s[i]){
            // 初始化与0号位相同的字串长度
            f[0][i] = 1
            f[i][0] = 1
        }
    }
    for(let i = 1; i < n; i++){
        for(let j = i + 1; j < n; j++){
            if(s[i] === s[j]){
                f[i][j] = f[i - 1][j - 1] + 1
                res = Math.max(res, f[i][j])
            }
        }    
    }
    return res
};