十月份中上旬华为精英OD C++开发 机考题新鲜出炉

1.整数对最小和

【输入描述】

输入两行整形数组array1，array2，每行首个数字为数组大小size(0<size<=100);

0<array1[i]<=1000;

0<array2[i]<=1000,

接下来一行为正整数k；

0<k<=array1.size()*array2.size();

【输出描述】

输出满足要求的的最小和。

【示例】

【输入】

3 1 1 4

3 1 2 3

2

【输出】

4

【解释】

array1[0]和array2[0]是一对，array1[1]与array2[0]是一对

所以1+1+1+1=4

【我的解答思路】

构造一个二维数组存放可能的数组对和，再将每个元素写入数组并排序，取需要的前k个求和即为整数对最小和。

我觉得思路应该是没有什么大问题，但是我只通过了百分之二十左右，不知道是什么细节造成了问题，还请路过的大佬指点。

2.数组二叉树

【题目描述】

二叉树也可以用数组来存储，给定一个数，树的根节点的值存储在下标1，对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2*N和2*N+1，并且我们用值-1代表一个节点为空。

给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。

【输入描述】

输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。注意第一个元素即为根节点的值，及数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略啦。输入的树最多为7层

【输出描述】

输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个。

【示例】

【输入】

3 5 7 -1 -1 2 4

【输出】

3 7 2

【我的解题思路】

通过字符串string s读入整行数组，定义一个string ss存储过滤空格的树，定义一个string s_sort去除根节点之后存储过滤空格的树，利用快排函数取第一个元素转成整形为最小叶节点，在ss字符串中利用find函数找出下标+1即为最小叶子节点存储的下标，然后依次/2，得出所有下标（即叶子节点到根节点的路径），逆向输出对应下标-1的ss元素（注意空格）。

思路上应该也没有问题。但是因为我一开始考试时网络断了，没法修复，当时心想凉啦，也比较释然啦，我就开始淡定地把题目都抄下来啦。刚抄完第三题最后一个字的时候，网络又自动恢复正常啦，没有非常惊喜，反而恐慌，所以就很匆忙啦。前两道题都是思路完整的，但是具体实现时总有细节问题，关键就是不知道错在哪一步啦，本地VS试用也到期啦，没办法调试，耗了很久均无果，最后被迫提交啦

3.二叉树遍历

【题目描述】

根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为：左子树，根节点，右子树

【输入描述】

由大小写字母、左右大括号、逗号组成的字符串

1.字母代表一个节点值，左右括号内包含该节点的子节点

2.左右子节点使用逗号分隔，逗号前为空则表示左子节点为空，没有逗号则表示右子节点为空

3.二叉树节点数最大不超过100

注：输入字符串格式是正确的，无需考虑格式错误情况

【输出描述】

输出一个字符串，为二叉树中序遍历各节点值的拼接结果

【示例】

【输入】

a{b{d,e{g,h{ ,i}}},c{f}}

【输出】

dbgehiafc

【我的解题思路】

这道题考试时间内没来得及思考。

总而言之，还是自己水平有限，还得多刷题，还是手太生啦。欢迎牛油们一起交流，一起进步。老阿姨要加油哎。干饭去啦~