997.找到小镇的法官.md

997.找到小镇的法官

/*
 * @lc app=leetcode.cn id=997 lang=typescript
 *
 * [997] 找到小镇的法官
 */

// @lc code=start
function findJudge(n: number, trust: [number, number][]): number {}
// @lc code=end

解法 1: 模拟

function findJudge(n: number, trust: [number, number][]): number {
  const map: { [key: number]: number } = [...new Array(n).keys()].reduce(
      (o, i) => Object.assign(o, { [i + 1]: 0 }),
      {},
    ),
    judge = new Set<number>([...new Array(n).keys()]),
    nojudge = new Set<number>()
  for (const [a, b] of trust) {
    map[b] = (map[b] ?? 0) + 1
    nojudge.add(a)
    if (judge.has(a - 1)) judge.delete(a - 1)
    if (!nojudge.has(b)) judge.add(b - 1)
  }

  if (judge.size === 1) {
    const num = [...judge][0] + 1
    if (map[num] === n - 1) return num
  }
  return -1
}

Case

test.each([
  { input: { n: 2, trust: [[1, 2]] }, output: 2 },
  {
    input: {
      n: 3,
      trust: [
        [1, 3],
        [2, 3],
      ],
    },
    output: 3,
  },
  {
    input: {
      n: 3,
      trust: [
        [1, 3],
        [2, 3],
        [3, 1],
      ],
    },
    output: -1,
  },
  {
    input: {
      n: 1,
      trust: [],
    },
    output: 1,
  },
])('input: n = $input.n, trust = $input.trust', ({ input: { n, trust }, output }) => {
  expect(findJudge(n, trust)).toEqual(output)
})