华为OD机试 - 叠积木1 - 双指针（Java 2023 B卷 200分）

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有一堆长方体积木，它们的高度和宽度都相同，但长度不一。

小橙想把这堆积木叠成一面墙，墙的每层可以放一个积木，或将两个积木拼接起来，要求每层的长度相同。若必须用完这些积木，叠成的墙最多为多少层?如下是叠成的一面墙的图示，积木仅按宽和高所在的面进行拼接。

在这里插入图片描述

二、输入描述

输入为一行，为各个积木的长度，数字为正整数，并由空格分隔。积木的数量和长度都不超过5000。

三、输出描述

输出一个数字，为墙的最大层数，如果无法按要求叠成每层长度一致的墙，则输出-1。

1、输入

3 6 6 3

2、输出

3、说明

题目要求：
每层可以放一个积木，或将两个积木拼接起来，要求每层的长度相同。

可以组成3+3、6、6三层；
可以组成3+6、3+6两层；

输出最大层数3

四、解题思路

输入一行数字，空格隔开；
降序排列好点，因为一张积木，可能就是一层，正序遍历较为方便；
获取最大层数；
特殊处理
- 只有1块积木时，只能有1层；
- 只有2块积木时，当两块积木的长度相同，会有1层，否则只有1层；
定义积木的最大值即每层的最小长度min、定义两个积木的最大值就是每层的最大长度max；
从每层的最小长度遍历到每层的最大长度，求这些积木可以拼接成的最大层数；
- 定义双指针left、right；
- list从大到小排序；
- 一层只能有两个积木，最大值+最小值一定等于每层的长度，否则就无法拼接（每层的长度必须相等）；
- 再去掉一个积木一层的情况，两个积木一层时，最大值和最小值一定是配对存在的，到最后都配对完毕，才算成功；
- 获取匹配成功的最大层数；
输出最大层数。

五、Java算法源码

java">public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 降序排列好点，因为一张积木，可能就是一层，正序遍历较为方便
    List<Integer> list = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).boxed().sorted((a, b) -> b - a).collect(Collectors.toList());
    // 获取最大层数
    int layerMax = getMaxLayer(list);
    System.out.println(layerMax);
}

/**
 * 获取最大层数
 *
 * @param list 每块积木的长度，降序排列
 * @return 最大层数
 */
private static int getMaxLayer(List<Integer> list) {
    int n = list.size();
    // 只有1块积木时，只能有1层
    if (n == 1) {
        return 1;
    }

    // 只有2块积木时，当两块积木的长度相同，会有1层，否则只有1层
    if (n == 2) {
        if (list.get(0).equals(list.get(1))) {
            return 2;
        } else {
            return 1;
        }
    }

    /**
     * 一层只能有2个积木或1个积木
     *
     * 积木的最大值即每层的最小长度
     * 两个积木的最大值就是每层的最大长度
     */
    Integer min = list.get(0);
    Integer max = list.get(0) + list.get(1);
    int layerMax = 0;

    /**
     * 从每层的最小长度遍历到每层的最大长度，求这些积木可以拼接成的最大层数
     */
    for (int length = min; length < max; length++) {
        // 层数
        int layer = 0;
        // 左指针
        int left = 0;
        // 右指针
        int right = n - 1;

        // list从大到小排序
        while (left < n && list.get(left).equals(length)) {
            left++;
            layer++;
        }

        while (left < right) {
            // 一层只能有两个积木，最大值+最小值一定等于每层的长度，否则就无法拼接（每层的长度必须相等）
            if ((list.get(left) + list.get(right) != length)) {
                break;
            }
            left++;
            right--;
            layer++;
        }

        /**
         * 这里有点绕
         * 再去掉一个积木一层的情况，两个积木一层时，最大值和最小值一定是配对存在的，到最后都配对完毕，才算成功
         * 获取匹配成功的最大层数
         */
        if (left == right + 1 && layer > layerMax) {
            layerMax = layer;
        }
    }
    return layerMax;
}