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通不过的时候，不要觉得自己单单紧盯着代码就能分析出毛病在哪里，而是该考虑在哪儿多加一个断点，或者有没有其他不能按预期很好处理的输入数据情况没有照顾到。
京公网安备 11010502036488号