数组移位和求和

Question

帮忙解决这个问题，或者给我算法名：

给定一个长度为N的一维数组，随机填充数字，所有数字都是2的幂。可以对数组执行两种操作：左移和右移。左（右）移时，将两个并排的相同数相加；一个新值被放置在左（右）单元格中。数组中右侧（左）的值向左（右）移动一个位置。 [1,4,16,8,8,2,1] > left > [1,4,16,16,2,1] > right > [1,4,32,2,1]。查找将导致最小数组长度的移位序列。

Answer 1

所描述的偏移似乎是 happening in the 2048 game 的概括，但仅在一个维度上，并且没有任何零。我认为该算法没有名称，但转换在 2048 游戏的上下文中通常被称为 "tile merging"。

首先注意左移和右移的效果没有区别。两者给出相同的结果。

您可以使用一个索引遍历数组，并跟踪另一个二级索引，只要两个值的 "merge" 发生，该二级索引就不会增加。相反，二级索引将在每次合并后移回，只要合并可以发生，然后它将与主索引一起再次增加。当没有合并发生时，主索引处的值只是复制到辅助索引。

代码如下所示：

function collapse(arr) {
    let j = 0;
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] === arr[j]) {
            do {
                arr[j] *= 2;
                j--;
            } while (j >= 0 && arr[j] === arr[j+1]);
            j++;
        } else {
            j++;
            arr[j] = arr[i];
        }
    }
    // clip the array, throw away anything beyond index j:
    arr.length = j+1;
    return arr;
}

// Example
let arr = [1,4,16,8,8,2,1];
console.log(collapse(arr));

这里函数 return 是结果数组，但如果你只需要它的长度，你可以 return j+1 代替。

数组移位和求和

array shift and sum

javascript

arrays

algorithm

shift