通过重复删除第一个和中间的元素、第一个和最后一个元素、或者中间和最后一个元素，将数组清空的最小成本是多少？

Question

通过重复删除第一个和中间的元素、第一个和最后一个元素、或者中间和最后一个元素，将数组清空的最小成本是多少？

4

这个问题是在我的面试中问到的，我无法想出一个最优解。

问题

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

操作：

删除第一个和最后一个元素 => 成本将为gcd（第一个，最后一个）

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

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

注意：

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

例子：

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

输出：4

说明：

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

- sn-

假设一个数组大小为偶数，那么其中间的元素是什么？ - Yuri Ginsburg

好的，它只需要被定义。如果两个或三个数对有相等的“gcd”怎么办？ - Yuri Ginsburg

@YuriGinsburg 你可以选择其中任意一个。除非总成本最小，否则没有关系。 - sn-

你的算法在这种情况下使用什么策略？ - Yuri Ginsburg

2

您正在描述一种“贪心算法”。贪心算法很少是最优的。鉴于这个输入{2,1000,1000,5}，您能说服自己您的解决方案是最优的吗？ - n. m.

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

无论我们执行操作的顺序如何，列表的状态都可以用四个指针描述，这些指针描述了列表中剩余的、连续的两个部分。这些指针受到一组特定规则的限制，这些规则限制了可以实现哪些状态。我会开始使用四个指针组合，并进行具有记忆化状态的递归。

我们可以通过观察这两个连续的部分的长度只能相差0或2来进一步减少状态。稍后我会尝试更新这个答案。

JavaScript代码（对Python中的随机测试和暴力测试可在此处进行））。

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));