1681.最小不兼容性.md

1681.最小不兼容性

/*
 * @lc app=leetcode.cn id=1681 lang=typescript
 *
 * [1681] 最小不兼容性
 */

// @lc code=start
function minimumIncompatibility(nums: number[], k: number): number {}

// @lc code=end

解法 1: 记忆化搜索

function minimumIncompatibility(nums: number[], k: number): number {
  const n = nums.length
  if (n % k !== 0) return -1
  nums.sort((a, b) => a - b)
  const cnt: number[] = [],
    size = n / k,
    dif: number[] = []
  for (let i = 1; i < 1 << n; i++) {
    const set = new Set<number>()
    let min = Infinity,
      max = -1,
      a = 0
    for (let j = 0; j < n; j++) {
      if (i & (1 << j)) {
        a++
        min = Math.min(min, nums[j])
        max = Math.max(max, nums[j])
        set.add(nums[j])
      }
    }
    cnt[i] = a
    if (a === set.size && a === size) {
      dif[i] = max - min
    }
  }
  const cache: number[][] = Array.from({ length: n }, () => [])
  const dfs = (i: number, state: number) => {
    if (i === n) {
      if (!state) return 0
      return Infinity
    }
    if (cnt[state] === size) return dif[state] ?? Infinity
    if (!state) return Infinity
    if (cache[i][state] !== undefined) return cache[i][state]
    let res = Infinity
    for (let j = state; j; j = state & (j - 1)) {
      if (cnt[j] !== size || dif[j] === undefined) continue
      res = Math.min(res, dif[j] + dfs(i + 1, state - j))
    }
    cache[i][state] = res
    return res
  }
  const res = dfs(0, (1 << n) - 1)
  if (res === Infinity) return -1
  return res
}

Case

test.each([
  { input: { nums: [1], k: 1 }, output: 0 },
  { input: { nums: [1, 2, 1, 4], k: 2 }, output: 4 },
  { input: { nums: [6, 3, 8, 1, 3, 1, 2, 2], k: 4 }, output: 6 },
  { input: { nums: [5, 3, 3, 6, 3, 3], k: 3 }, output: -1 },
])('input: nums = $input.nums, k = $input.k', ({ input: { nums, k }, output }) => {
  expect(minimumIncompatibility(nums, k)).toEqual(output)
})