1005.k-次取反后最大化的数组和.md

1005.k-次取反后最大化的数组和

/*
 * @lc app=leetcode.cn id=1005 lang=typescript
 *
 * [1005] K 次取反后最大化的数组和
 */

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

解法 1: 使用堆

function largestSumAfterKNegations(nums: number[], k: number): number {
  const heap = new Heap<number>((n1, n2) => n1 < n2)
  let sum = 0
  for (const num of nums) {
    sum += num
    heap.push(num)
  }
  for (let i = 0; i < k; i++) {
    let num = heap.pop()
    sum -= 2 * num
    heap.push(-num)
  }
  return sum
}
class Heap<T> {
  private _heap: T[] = []
  constructor(private _compare: (n1: T, n2: T) => boolean) {}
  private swap(i: number, j: number) {
    ;[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]
  }
  private _has(i: number) {
    return Object.prototype.hasOwnProperty.call(this._heap, i)
  }
  private compare(i: number, j: number) {
    return this._compare(this._heap[i], this._heap[j])
  }
  push(node: T) {
    this._heap.push(node)
    let cur = this._heap.length - 1
    let parent = (cur - 1) >> 1
    while (cur > 0 && this.compare(cur, parent)) {
      this.swap(cur, parent)
      ;[cur, parent] = [parent, (parent - 1) >> 1]
    }
  }
  pop() {
    let res = this._heap[0]
    this.swap(0, this._heap.length - 1)
    this._heap.pop()
    let cur = 0,
      left = 2 * cur + 1,
      right = 2 * cur + 2

    while (left < this._heap.length) {
      if (!this._has(right)) right = left
      if (this.compare(right, left)) [left, right] = [right, left]
      if (this.compare(cur, left)) break

      this.swap(cur, left)
      cur = left
      ;[left, right] = [2 * cur + 1, 2 * cur + 2]
    }
    return res
  }
}

解法 2: 双向链表

interface DListNode {
  val: number
  next: DListNode | null
  pre: DListNode | null
}
function largestSumAfterKNegations(nums: number[], k: number): number {
  const root: DListNode = { val: -Infinity, next: null, pre: null }
  const end: DListNode = { val: Infinity, next: null, pre: root }
  root.next = end
  let sum = 0
  const push = (node: DListNode) => {
    end.next = node
    node.pre = end
    while (node.pre && node.pre.val > node.val) {
      const pre: DListNode = node.pre
      const next: DListNode | null = node.next
      node.next = pre
      node.pre = pre.pre
      pre.pre!.next = node

      pre.next = next
      pre.pre = node
      next && (next.pre = pre)
    }
  }
  const pop = () => {
    const next = root.next!
    root.next = next.next
    next.pre = null
    next.next!.pre = root
    next.next = null
    return next
  }
  for (const num of nums) {
    sum += num
    push({ val: num, next: null, pre: null })
  }
  for (let i = 0; i < k; i++) {
    let tmp = pop()!
    sum -= 2 * tmp.val
    tmp.val = -tmp.val
    push(tmp)
  }
  return sum
}

解法 3: 桶排序

function largestSumAfterKNegations(nums: number[], k: number): number {
  let map = new Array(201).fill(0)
  let sum = 0
  for (const num of nums) {
    sum += num
    map[num + 100] += 1
  }
  for (let i = 0; i < map.length; i++) {
    if (!map[i]) continue
    if (i === 100) return sum
    if (i > 100) return sum - 2 * (k & 1 ? i - 100 : 0)

    if (k <= map[i]) return sum - 2 * k * (i - 100)
    sum -= 2 * map[i] * (i - 100)
    map[200 - i] = map[i]
    k -= map[i]
  }
}

Case

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