积木搭建问题

有一些积木,长度各不相同,每层可以使用一个或者两个拼接搭建,问最高可以搭建几层(要求每层长度一样,否则为0)
例1:[6,3,3,6] 最高可以搭建3层,每层长度为6
例2:[6,3,1,6] 最高可以搭建0层,因为每层的长度无法一致

解题思路

1. 要想层数尽量大,那么就要保证,一块所占一层的数量要多
2. 其他两块拼接的一定是最大和最小的组合,否则一定不能满足所有层数长度一致
3. 拼接的数量一定为偶数,否则不能满足所有层数一致

代码实现

// 求出拼接状态下最大层数
const superposition = (ary, max) => {
    const len = ary.length;
    if (len === 0) {
        return 0;
    }
    // 既然是拼接,那么数量一定是偶数,否则不能满足长度一致
    if (len % 2 !== 0) {
        return -1
    };
    let step = 0
    for (let i = 0; i < len / 2; i++) {
         // 如果其中有一对拼接不能和最大值相等,则不能满足长度一致
        if (ary[i] + ary[len - 1 - i] !== max) {
            step = -1;
            break;
        }
        step += 1;
    };
    return step;
}


const fn = (ary) => {
    ary.sort((a, b) => a - b)
    const len = ary.length;
    const max = ary[len - 1];
    const excludeMaxAry = ary.filter(item => item !== max);
    const maxLen = len - excludeMaxAry.length;
    const step = superposition(ary, ary[0] + max);
    const excludeMaxStep = superposition(excludeMaxAry, max) === -1 ? -1 : superposition(excludeMaxAry, max)  + maxLen;
    if (step === -1 && excludeMaxStep === -1) {
        return 0;
    }
    return step > excludeMaxStep  ? step : excludeMaxStep ;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容