使所有元素彼此相等的最小步骤

Question

详细内容如下：

例如: [1,1,2,4] (init) -> gen1 [2,1,2,4] -> gen2 [4,1,2,4] -> gen3 [4,2,2,4 ] -> gen4 [4,4,2,4] -> gen5（无变化） -> gen6 [4,4,4,4]

每一代：
奇数步长：+1 或零
偶数步长：+2 或零

为了使所有 ele 彼此相等，我们需要至少 6 个 gen（示例）。写一个算法来解决这个问题。

这是其中一条评论，我感到很困惑。

我们希望用 1 和 2 交替贪婪地填充每个槽（奇数代和偶数代），直到它跨越总差值。
换句话说，我们需要相同数量的 1 和 2。 如果我们需要 n 个 1 和 n 个 2，则 1 n + 2 n =total_difference 或 n =total_difference / 3。 所以我们需要2n代。 此外，如果 Total_diff - 3n == 1 或，我们还需要 1 代 如果total_diff - 3*n == 2，我们还需要2代。 总差是 i 0 到 len(arr) - 1 的 (max(arr) - arr[i]) 之和。

我们希望用 1 和 2 交替贪婪地填充每个槽（奇数代和偶数代），直到它跨越总差值。

我明白了：
换句话说，我们需要相等数量的 1 和 2。

我不明白：
如果我们需要 n 个 1 和 n 个 2，则 1 n + 2 n =total_difference 或 n =total_difference / 3。

我明白了
所以我们需要2n代。

我不明白
此外，如果 Total_diff - 3n == 1 或，我们还需要 1 代 如果 Total_diff - 3*n == 2，我们还需要 2 代。

我不明白

// Here is one of solutions from comments and looks like working based on the comment above.
// * g: [1, 2, 2, 4]
const ans = (arr) => {
    const eachCycleVal = 1 + 2; /*cycle contains decreasing 1 followed by 2*/
    const maxVal = Math.max(...arr);
    let totalCycles = 0;
    for (let i = 0; i < arr.length; i++) {
        arr[i] = maxVal - arr[i];
        arr[i] = Math.ceil(arr[i] / eachCycleVal);
        totalCycles += arr[i];
    }
    return 2 * totalCycles;
}

const arr = [1, 2, 2, 4]; // 6
const out = ans(arr);
console.log(out)

原文来自https://leetcode.com/discuss/interview-question/5798402/Amazon-OA-questions

Answer 1

您可以使用以下公式计算周期：

s = sum over all items
n = number of items        
d = n * 4 - s                  // missing sum
c = floor(d / 3) * 2 + d % 2

c

是基于

1 2 1 2 1 2

等系列，并且从一开始就有两对的总和为三。要获得这些对，请将所有

1

和

2

对除以三（取整数值）并乘以 2。

最后加上剩余的值。如果是1，则加1，如果是

2

，则下一步无效，下一步需要在该项目中添加

2

。

Answer 2

这是我解决这个问题的尝试：

对于每一步的最大长度，进度始终采用此格式：

plus 1, plus 2, plus 1, plus 2,...

每组 2 个步骤：

(plus 1, plus 2), (plus 1, plus2), ...

如果我们将 2 个步骤视为一个步骤，那就是

(plus 3), (plus 3), ..., (last 2 steps to reach the goal)

所以我们只需要找到最后2步（最后

plus 3

） 只有3种情况：

• 最后 2 个步骤是

  plus 1, plus 2

  => 需要 0 个额外步骤
• 最后 2 个步骤是

  plus 1, plus 0

  => 需要 1 个额外步骤
• 最后 2 个步骤是

  plus 0, plus 2

  => 需要 2 个额外步骤

function minDifference(arr) {
    const max = Math.max(...arr)
    const totalDiff = arr.reduce((acc, next) => acc += max - next, 0)
    switch (totalDiff % 3) {
        case 0:
            return 2 * (totalDiff / 3)
        case 1:
            return 2 * Math.floor(totalDiff / 3) + 1
        case 2:
            return 2 * Math.floor(totalDiff / 3) + 2
    }
}
const arr1 = [1, 1, 2, 4] //6
const arr2 = [2, 2, 4] //3
const arr3 = [1, 2, 4] //4
console.log(minDifference(arr1))
console.log(minDifference(arr2))
console.log(minDifference(arr3))