1703.得到连续-k-个-1-的最少相邻交换次数.md

1703.得到连续-k-个-1-的最少相邻交换次数

/*
 * @lc app=leetcode.cn id=1703 lang=typescript
 *
 * [1703] 得到连续 K 个 1 的最少相邻交换次数
 */

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

解法 1: 滑动窗口+三分

function minMoves(nums: number[], k: number): number {
  const n = nums.length
  const cnt: number[] = [0],
    sum0: number[] = [0],
    sum1: number[] = [0]
  for (let i = 1; i <= n; i++) {
    cnt[i] = cnt[i - 1]
    sum1[i] = sum1[i - 1]
    sum0[i] = sum0[i - 1]
    if (nums[i - 1]) {
      cnt[i]++
      sum1[i] += i
    } else {
      sum0[i] += i
    }
  }
  const search = (left: number, right: number, t: number, type: number) => {
    let l = left,
      r = right
    let check: (m: number) => number
    if (type) {
      check = m => cnt[m] - cnt[left]
    } else {
      check = m => m - left - (cnt[m] - cnt[left])
    }
    while (l < r) {
      const m = (l + r) >> 1
      if (check(m) >= t) {
        r = m
      } else {
        l = m + 1
      }
    }
    return l
  }
  let res = Infinity
  for (let i = 1; i <= n - k + 1; i++) {
    const need = k - (cnt[i + k - 1] - cnt[i - 1])
    const calc = (a: number, b = need - a): number => {
      let left = 0,
        right = 0,
        m = search(i - 1, i + k - 1, a, 0)
      if (a) {
        const l = search(0, i - 1, cnt[i - 1] - a, 1)
        left = sum0[m] - sum0[i - 1] - (sum1[i - 1] - sum1[l])
      }
      if (b) {
        const r = search(i + k - 1, n, b, 1)
        right = sum1[r] - sum1[i + k - 1] - (sum0[i + k - 1] - sum0[m])
      }
      return left + right
    }
    let l = Math.max(0, need - (cnt[n] - cnt[i + k - 1])),
      r = Math.min(need, cnt[i - 1])
    while (l < r) {
      const d = Math.floor((r - l) / 3)
      if (d === 0) break
      const m1 = l + d,
        m2 = r - d
      const a = calc(m1),
        b = calc(m2)
      if (a <= b) {
        r = m2
      } else {
        l = m1
      }
    }
    for (let j = l; j <= r; j++) {
      let ans = calc(j)
      res = Math.min(res, ans)
    }
  }
  return res
}

Case

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