1601.最多可达成的换楼请求数目.md

1601.最多可达成的换楼请求数目

/*
 * @lc app=leetcode.cn id=1601 lang=typescript
 *
 * [1601] 最多可达成的换楼请求数目
 */

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

解法 1: 枚举

function maximumRequests(n: number, requests: number[][]): number {
  const m = requests.length
  const check = (state: number) => {
    const builds: number[] = new Array(n).fill(0)
    let res = 0
    for (let i = 0; i <= m; i++) {
      if (state & (1 << i)) {
        res++
        const [x, y] = requests[i]
        builds[x]--
        builds[y]++
      }
    }
    return builds.every(num => num === 0) ? res : -1
  }
  let res = 0
  for (let i = 0; i < 1 << m; i++) {
    res = Math.max(res, check(i))
  }
  return res
}

Case

test.each([
  {
    input: {
      n: 5,
      requests: [
        [0, 1],
        [1, 0],
        [0, 1],
        [1, 2],
        [2, 0],
        [3, 4],
      ],
    },
    output: 5,
  },
  {
    input: {
      n: 3,
      requests: [
        [0, 0],
        [1, 2],
        [2, 1],
      ],
    },
    output: 3,
  },
  {
    input: {
      n: 4,
      requests: [
        [0, 3],
        [3, 1],
        [1, 2],
        [2, 0],
      ],
    },
    output: 4,
  },
])('input: n = $input.n, requests = $input.requests', ({ input: { n, requests }, output }) => {
  expect(maximumRequests(n, requests)).toEqual(output)
})