1001.网格照明.md

1001.网格照明

/*
 * @lc app=leetcode.cn id=1001 lang=typescript
 *
 * [1001] 网格照明
 */

// @lc code=start
function gridIllumination(n: number, lamps: number[][], queries: number[][]): number[] {}

// @lc code=end

解法 1: 哈希表

function gridIllumination(n: number, lamps: number[][], queries: number[][]): number[] {
  let row = new Map<number, number>(),
    col = new Map<number, number>(),
    left = new Map<number, number>(),
    right = new Map<number, number>(),
    map = new Map<number, Map<number, number>>(),
    maps = [row, col, left, right]
  const add = (num: number, i: number) => maps[i].set(num, (maps[i].get(num) ?? 0) + 1)
  const sub = (count: number) => (num: number, i: number) => {
    maps[i].set(num, maps[i].get(num)! - count)
    if (maps[i].get(num) === 0) maps[i].delete(num)
  }
  for (let [r, c] of lamps) {
    ;[r, c, c - r, c + r].map(add)

    if (!map.has(r)) map.set(r, new Map())
    const m = map.get(r)!
    m.set(c, (m.get(c) ?? 0) + 1)
  }
  let res: number[] = [],
    dirs = [
      [0, 0],
      [-1, -1],
      [-1, 0],
      [-1, 1],
      [0, 1],
      [1, 1],
      [1, 0],
      [1, -1],
      [0, -1],
    ]
  for (let [r, c] of queries) {
    if (row.has(r) || col.has(c) || left.has(c - r) || right.has(c + r)) res.push(1)
    else res.push(0)

    for (let [dr, dc] of dirs) {
      let [nr, nc] = [dr + r, dc + c]
      const count = map.get(nr)?.get(nc)
      if (count) {
        ;[nr, nc, nc - nr, nc + nr].map(sub(count))
        map.get(nr)!.delete(nc)
      }
    }
  }
  return res
}

Case

test.each([
  {
    input: {
      n: 5,
      lamps: [
        [0, 0],
        [4, 4],
      ],
      queries: [
        [1, 1],
        [1, 0],
      ],
    },
    output: [1, 0],
  },
  {
    input: {
      n: 5,
      lamps: [
        [0, 0],
        [4, 4],
      ],
      queries: [
        [1, 1],
        [1, 1],
      ],
    },
    output: [1, 1],
  },
  {
    input: {
      n: 5,
      lamps: [
        [0, 0],
        [0, 4],
      ],
      queries: [
        [0, 4],
        [0, 1],
        [1, 4],
      ],
    },
    output: [1, 1, 0],
  },
])(
  'input: n = $input.n, lamps = $input.lamps, queries = $input.queries',
  ({ input: { n, lamps, queries }, output }) => {
    expect(gridIllumination(n, lamps, queries)).toEqual(output)
  },
)