290周赛复盘

不积跬步，无以至千里；不积小流，无以成江海

时间：2020-4-24 讨论：https://leetcode-cn.com/circle/discuss/F9IBSj/

A: 多个数组求交集

思路：

1. 遍历数组
2. 求交集
   1. 方式一， 暴力法全遍历统计各元素出现的次数
   2. 方式二， 每次仅保留重合部分， 或当重合部分为空时终止遍历

function intersection(nums: number[][]): number[] {
    const n = nums.length;
    let ans = nums[0];
    for (let i = 1; i < n && ans.length; i++) {
        const cur = new Set(nums[i]);
        // get intersect
        ans = ans.filter(v => cur.has(v));
    }
    return ans.sort((a, b) => a - b);
};

扩展：

const a = [1, 2, 3], b = [2, 3, 4];
// 并集
let union = Array.from(new Set([...a, ...b]));
// [1, 2, 3, 4]
// 交集
let intersection = a.filter(v => b.includes(v));
// [2, 3]
// 差集
let subtract = a.filter(v => !b.includes(v));
// [1]
// 补集
let complement = [...a.filter(v => !b.includes(v)), ...b.filter(v => !a.includes(v))]
// [1, 4]

B: 统计圆内格点数目

由于 1 <= xi, yi <= 100 ；1 <= ri <= min(xi, yi) 可推到出所有圆在[0, 0] 到 [200, 200] 的区域中。
由于数据规模有限，可暴力计算出所有点。
优化思路：
不断缩小目标方形区域， 保证目标区域可以容纳所有圆。

function countLatticePoints(circles: number[][]): number {
    const n = circles.length;
    let minX = Number.MAX_SAFE_INTEGER, minY = minX,
    maxX = Number.MIN_SAFE_INTEGER, maxY = maxX;
    let squares = [];
    for (let [x, y, r] of circles) {
        minX = Math.min(x - r, minX);
        minY = Math.min(y - r, minY);
        maxX = Math.max(x + r, maxX);
        maxY = Math.max(y + r, maxY);
        squares.push(r ** 2);
    }
    let ans = 0;
    for (let i = minX; i <= maxX; i++) {
        for (let j = minY; j <= maxY; j++) {
            for (let k = 0; k < n; k++) {
                const [x, y, ] = circles[k];
                if ((i - x) ** 2 + (j - y) ** 2 <= squares[k]) {
                    ans++;
                    break;
                }
            }
        }
    }
    return ans;
};

总结： :::info

枚举坐标系中的点：

1828. 统计一个圆中点的数目
几何 https://leetcode-cn.com/tag/geometry/problemset/ ::: 反思：
以为会涉及比较复杂的几何知识，其实关键点在数据规模上

C: 统计包含每个点的矩形数目

思路： 枚举

function countRectangles(rectangles: number[][], points: number[][]): number[] {
    const n = 101;
    let ymap = Array.from({ length: n }, v => []);
    for (let [x, y] of rectangles) {
        ymap[y].push(x);
    }
    for (let nums of ymap) {
        nums.sort((a, b) => a - b);
    }
    let ans = [];
    for (let [x, y] of points) {
        let count = 0;
        for (let h = y; h < n; h++) {
            const nums = ymap[h];
            let left = 0, right = nums.length;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (x > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            count += (nums.length - right);
        }
        ans.push(count);
    }
    return ans;
};

总结： :::info

关键：数据规模

:::

D: 花期内花的数目

思路：

1. 差分， 考虑到数组会超时，优化为哈希表存放差分值
2. 查询， 哈希表

   function fullBloomFlowers(flowers: number[][], persons: number[]): number[] {
    // 离散差分
    let hashMap = new Map();
    for (let [start, end] of flowers) {
        end++;
        hashMap.set(start, (hashMap.get(start) || 0) + 1);
        hashMap.set(end, (hashMap.get(end) || 0) - 1);
    }
    for (let p of persons) {
        if (!hashMap.has(p)) {
            hashMap.set(p, 0);
        }
    }
    let keys = Array.from(hashMap.keys()).sort((a, b) => a - b);
    let pre = 0;
    for (let k of keys) {
        pre += hashMap.get(k);
        hashMap.set(k, pre);
    }
    // 离散查询
    let ans = persons.map(v => hashMap.get(v));
    return ans;
   };
   

总结： :::info 离散化差分 + 离线查询
差分：
731. 我的日程安排表 II
732. 我的日程安排表 III
2015. 每段建筑物的平均高度
2021. 街上最亮的位置
2237. Count Positions on Street With Required Brightness
离线查询：
1697. 检查边长度限制的路径是否存在
1707. 与数组中元素的最大异或值
1847. 最近的房间 :::

启发

关注数据规模