华为OD机试 - 书籍叠放 - 逻辑分析（Java 2023 B卷 200分）

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

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

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

一、题目描述

书籍的长、宽都是整数对应(l,w)。如果书 A 的长宽度都比 B 长宽大时，则允许将 B 排列放在 A 上面。现在有一组规格的书籍，书籍叠放时要求书籍不能做旋转，请计算最多能有多少个规格书籍能叠放在一起。

二、输入描述

输入：books = [[20,16],[15,11],[10,10],[9,10]]

说明：总共 4 本书籍，第一本长度为 20 宽度为 16;第二本书长度为 15 宽度为 11，依次类推，最后一本书长度为 9 宽度为 10。

三、输出描述

3

最多 3 个规格的书籍可以叠放到一起,从下到上依次为:[20,16],[15,11,[10,10]

四、解题思路

这是一道很典型的逻辑分析题，只要按照题目描述的意思走就可以了。

如果考试的时候，你抽到的200分的题是这道题的话，那么你足够幸运了~

1. 输入一组二位数组形式的字符串，[[20,16],[15,11],[10,10],[9,10]]；
2. 将输入字符串转为数组集合；
3. 左右依次对比，降序排序， [[20,16],[15,11],[10,10],[9,10]]；
4. 定义符合要求的数组集合okList；
5. 获取长宽最大的第一个数组firstArr；
6. 遍历余下的数组集合；
   • 获取下一个数组nextArr；
   • 通过第一个数组去寻找长宽都比第一个数组小的第二个数组
   • 将新加入的“下一个数组”置为“待比较的第一个数组”；
7. 输出符合要求的数组大小。

五、Java算法源码

public class OdTest {
    /**
     * 如果书 A 的长宽度都比 B 长宽大时，则允许将 B 排列放在 A 上面
     * [[20,16],[15,11],[10,10],[9,10]]
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        // [20,16] [15,11] [10,10] [9,10]
        String[] arr = input.substring(1,input.length()-1).replace("],","]],").split("],");
        // 将输入字符串转为数组集合
        List<Integer[]> arrList = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            Integer[] ints = Arrays.stream(arr[i].replace("[", "").replace("]", "").split(",")).mapToInt(Integer::parseInt).boxed().toArray(Integer[]::new);
            arrList.add(ints);
        }

        // 左右依次对比，降序排序 [[20,16],[15,11],[10,10],[9,10]]
        Collections.sort(arrList, new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                if(o1[0] > o2[0]){
                    return -1;
                }else if(o1[0] < o2[0]){
                    return 1;
                }else{
                    if(o1[1] > o2[1]){
                        return -1;
                    }else if(o1[1] <o2[1]){
                        return 1;
                    }else{
                        return 0;
                    }
                }
            }
        });

        // 符合要求的数组
        List<Integer[]> okList = new ArrayList<>();
        // 获取长宽最大的第一个数组
        Integer[] firstArr = arrList.get(0);
        okList.add(firstArr);
        // 遍历余下的数组集合
        for (int i = 1; i < arrList.size(); i++) {
            // 获取下一个数组
            Integer[] nextArr = arrList.get(i);
            // 通过第一个数组去寻找长宽都比第一个数组小的第二个数组
            if(firstArr[0] > nextArr[0] && firstArr[1] > nextArr[1] ){
                okList.add(nextArr);
                // 将新加入的“下一个数组”置为“待比较的第一个数组”
                firstArr = nextArr;
            }
        }

        // 输出符合要求的数组大小
        System.out.println(okList.size());
    }
}

六、效果展示

1、输入

[[20,16],[10,10],[9,10],[15,11],[15,12],[15,12],[9,9],[20,17]]

2、输出

4

3、说明

1. 输入[[20,16],[10,10],[9,10],[15,11],[15,12],[15,12],[9,9],[20,17]]；
2. 按照左右依次对比，降序排序，[[20,17],[20,16],[15,12],[15,12],[15,11],[10,10],[9,10],[9,9]]；
3. 通过第一个数组去寻找长宽都比第一个数组小的第二个数组，最终获得[[20,17],[15,12],[10,10],[9,9]]；
4. 输出符合要求的数组集合长度4。

🏆下一篇：华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法（Java 2023 B卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

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