通过重复删除第一个和中间、第一个和最后一个或中间和最后一个元素来清空数组的最小成本-解网

问：

这个问题是在一次采访中问我的，我无法想出最佳解决方案。

问题

给定一个偶数大小的数组，我们可以对数组执行任何操作，直到数组变为空，使总成本最小。

操作：

删除第一个和最后一个元素 => 成本将是 GCD（first， last）

删除第一个和中间元素 => 成本将是 GCD（第一个，中间）

删除中间和最后一个元素 => 成本将是 gcd（middle， last）

注意：

在偶数大小的数组中，有两个中间元素。因此，将第二个中间元素视为中间元素。
gcd（x，y）代表 x 和 y 之间的最大公约数

例：

输入：[2， 4， 8， 6]

输出： 4

解释：

在第一个操作中，删除第一个和中间元素，cost = gcd（2,8） = 2
在第二个操作中，删除 4 和 6，cost = gcd（4,6） = 2
总成本 = 2+2 = 4

数组算法与语言无关

function gcd(x, y){
  while(y)
    [x, y] = [y, x % y];
  return x;
}

function f(A){
  const memo = {};
  const n = A.length;
  const mid = n / 2;
  
  function g(l0, l1, r0, r1){
    const key = String([l0, l1, r0, r1]);

    if (memo.hasOwnProperty(key))
      return memo[key];
    
    const len_l = l1 - l0 + 1;
    const len_r = r1 - r0 + 1;

    if (len_l + len_r == 2){
      if (len_r && len_l)
        return gcd(A[l0], A[r0]);
      else if (len_l)
        return gcd(A[l0], A[l0 + 1]);
      else
        return gcd(A[r0], A[r0 + 1]);
    }

    let a = A[l0];
    let b = A[r1];

    const outer = gcd(a, b) + g(l0 + 1, l1, r0, r1 - 1);

    if (len_r >= len_l)
      var mid = r0 + (len_l + len_r) / 2 - len_l;
    else
      var mid = l0 + (len_l + len_r) / 2;

    b = A[mid];
    
    const _l1 = l1 - (mid == l1 ? 1 : 0);
    const _r0 = r0 + (mid == r0 ? 1 : 0);

    const left = gcd(a, b) + g(l0 + 1, _l1, _r0, r1);

    a = A[r1];

    const right = gcd(b, a) + g(l0, _l1, _r0, r1 - 1);

    return memo[key] = Math.min(outer, left, right);
  }
  
  return g(0, mid - 1, mid, n - 1);
}

let A = [2, 4, 8, 6];
console.log(JSON.stringify(A));
console.log(f(A));

A = [8,5,21,10,25,9]
console.log(JSON.stringify(A));
console.log(f(A));

const n = 200;
A = [];

for (let i=0; i<n; i++)
  A.push(i + 1);

console.log(JSON.stringify(A));
console.log(f(A));

通过重复删除第一个和中间、第一个和最后一个或中间和最后一个元素来清空数组的最小成本

Minimum cost to empty an array by repeatedly removing first and middle, first and last, or middle and last elements

问题

评论

评论