2021年华为OD笔试总结（20200621）

难度一星题1：最小合并数

输入一组整数，要求输出由输入整数中最多3个整数按任意顺序合并（拼接）成最小整数。数组大小n<100，每个输入数据的范围0<x<10000，输入数组包含的整数可能小于3个。输入输出示例：

输入：

51,2,34,58,116

输出：

23451

这题主要考察数理逻辑，如果把输入整数转换为字符串拼接然后转换为整数稍微麻烦一点。这里直接根据题目条件中数据范围0<x<10000，将输入整数中最小的3个全部对其到10000位，直接整数比较就行，但是这样引入了一个边角情况的处理需要留意

Java解法：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int cur = 0, cnt = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        PriorityQueue<Integer> res = new PriorityQueue<>(3);
        Scanner sc = new Scanner(System.in);
        String getLine = sc.nextLine();
        String[] fields = getLine.split(",\\s*");
        for (String num: fields) {
            ++cnt;
            cur = Integer.parseInt(num);
            minQueue.offer(cur);    // java优先队列默认从小到大排序
        }

        if (cnt > 3) {
            cnt = 3;
        }
        int shift, alignedVal;
        while (cnt > 0) {
            cur = minQueue.poll();
            alignedVal = cur;
            shift = 0;
            while (alignedVal < 10000) {    //把输入的每个整数都对齐到5位数
                alignedVal *= 10;
                ++shift;
            }
            // 可能存在58和580这样的数据对齐后是同一个数，这种情况要求58对齐后更小，
            // 所以都减去乘以10的次数
            alignedVal -= shift;
            map.put(alignedVal, cur);    // 这儿数据量不大，直接使用哈希保存对应关系比较省事
            res.offer(alignedVal);
            --cnt;
        }

        Integer val;
        while((val = res.poll()) != null) {
            System.out.printf("%d", map.get(val));
        }
        System.out.println();
    }
}

难度一星题2：统计数据宽度取模后最多的有效数

定义一种数据宽度某一模数a的取模运算，并且取模结果小于数值c时，把该数计做有效数，否则计做无效数。例如a=4, c=3时，对269628502的宽度取模，269628502 % 4 = 0x10123456 % 4 = (0x10+0x12+0x34+0x56) % 4 = 0，取模结果0<4，所以269628502计为有效数。那么，现在要求对输入的一组数据的宽度取模后，需要统计出相同结果最多的有效数个数并输出。输入数据中，读取第一个数作为模数a，第二个数作为有效数判断条件c。输入输出示例：

输入：

3,4,9,1899,2004399,20128,1,0,987642,1588,626

统计取模结果后的每个有效数为[1,2, 3, 2, 1, 1, 3, 2, 2]，结果相同的有效数最多的是2，个数为4，所以输出：

4

这个题目在原文中的描述有点复杂，但是要求的工作却很简单。当时没有通过一个case，不确定是否有审题正确，只想提醒大家碰到这种啰嗦的问题描述还是静下心要好好审题

难度二星题1：书本的最大堆叠高度

这里有一堆不同高度和宽度的图书，需要你按从大到小的循序把它们水平堆叠到一起，意即堆叠时要求上层的图书的高度和宽度都不超过下层的图书，而且不能将书本旋转，输入中每一对数分别对应书本的高度和宽度，要求输出书本最大堆叠高度。输入输出示例：

输入：

27,18 32,24 20,28 31,20 26,19

输出：

3

这个题目其实是NC91.最长递增子序列稍微包装了一下，当时就往动态规划的方向怎么也想不通，考完一下就想起来了(⊙﹏⊙)。所以考试还是要保持冷静，同时我太菜了

Java解法：

package com.company;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int height, width;
        edge book;
        PriorityQueue<edge> bookx = new PriorityQueue<edge>(new Comparator<edge>() {
            public int compare(edge a, edge b) {
                if (a.x == b.x) {       // compare中两数相等时要求返回0
                    if (a.y == b.y) {
                        return 0;
                    } else {
                        return b.y - a.y;   // 图书的高相等时，需要把较宽的书放在下面
                    }
                } else {
                    return b.x - a.x;
                }
            }
        });
        Scanner sc = new Scanner(System.in);
        String inputLine = sc.nextLine();
        String[] fields = inputLine.split(" ");
        for (String length: fields) {
            height = Integer.parseInt(length.split(",")[0]);
            width = Integer.parseInt(length.split(",")[1]);
            book = new edge(height, width);
            bookx.offer(book);
        }

        int decreaseMax = 0, bookNum = bookx.size();
        int[] decreaseWidth = new int[bookNum];
        int[] widthIndex = new int[bookNum];
        edge res;
        res = bookx.poll();
        decreaseWidth[0] = res.y;
        widthIndex[decreaseMax] = 0;
        ++decreaseMax;
        while((res = bookx.poll()) != null) {   // 使用poll方法才可以从优先队列中取到有序的数据
            if (res.y <= decreaseWidth[decreaseMax-1]) {    // 高度和宽度相同的图书可以堆叠
                decreaseWidth[decreaseMax] = res.y;
                widthIndex[decreaseMax] = decreaseMax;
                ++decreaseMax;
            } else {
                for (int i=0; i<decreaseMax; ++i) {
                    if (res.y >= decreaseWidth[i]) {    // 注意等号
                        decreaseWidth[i] = res.y;
                        widthIndex[decreaseMax] = i;
                        break;
                    }
                }
            }
        }
        System.out.printf("%d\n", decreaseMax);
    }

    private static class edge {
        int x;
        int y;

        public edge(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

总结

整体看来华为的OD考试难度比往年有所加大（没错，我已经不是第一次考了），我这3题在题库中都不能找到原题。而且改编的题目描述可能没那么容易一眼看出解决方案，所以再次强调冷静认真审题非常重要。这里老生常谈的解题技巧我就不罗嗦了，主要说一下个人的考试感悟。
首先这次对于我巨坑的一点是，所有的输入数据都要从控制台接收，而我刚从C语言切到Java刷题，对于Java格式化输入的方法不太熟悉。幸亏有例题的解答给出了接收输入的方式，但是，更坑的是示例的while(sc.hasNext())和nextInt用法是错误的，因为1.hasNext等方法读取到回车后仍期望读取到EOF造成阻塞；2.nextInt等方法不会扫描整数后的空格，而next方***扫描子串前后的空格，所以获取字符流中的整数时要使用skip方法来跳过中间的一些空格（或者其他分隔符）。
第二点，牛客的机试编辑器真的不太好用，不知道为什么我切出浏览器再切回的时候，编辑模式就变成了覆盖输入，不过还好机试允许在自己的IDE中调试代码问题不大。
最后也是最重要的一点，既然现在允许我们在IDE中调试代码，我们在解答时候特别容易忘记一些边角情况的处理。考试前一定要会熟练使用IDE调试代码，要相信计算机永远是对的。在运行异常和一些case通不过的时候，不要觉得自己单单紧盯着代码就能分析出毛病在哪里，而是该考虑在哪儿多加一个断点，或者有没有其他不能按预期很好处理的输入数据情况没有照顾到。