我抽到的华为 OD 机试算法不难，但是没过，可惜了

华为 OD 机试，4 道算法题，两道 100 分一道 200 分，时间 150 分钟，按通过测试用例比例给分（但是我以为按步骤给分 Orz ）

第一题：

题

两个从小到大排序的正整数数组 A[] B[]，要求输出满足以下条件

A[i] <= B[j]
只输出满足条件最近的 B[j]
按照 A 的顺序输出

例如

A：1 ，2 ，3

B：3 ，5 ，6 ，8

要输出

1 ，3

2 ，5

3 ，6

解

用了双层 for 循环，但是通过测试用例 90%，本题得分 90

第二题

题

正整数数组 A[]，正整数 magicNumber ，要求输出间隔 magicNumber 以内的相同数字的第一个 index ，否则输出 -1

例如

A：3 ，2 ，4 ，3 ，5

当 magicNumber = 3 时输出 0

当 magicNumber = 2 时输出 -1

解

也是双层循环，但内层我死磕用的 while ，竟然没做出来（太不应该了）。。。鉴于时间不足以及我以为按步骤给分，就直接提交了。本题得分 0

第三题

题

m 个摇摇车，n 个小朋友分别有编号，小朋友玩摇摇车可以用 1233 表示（题目就这么描述的）。小朋友可以排队等着玩，或者直接离开。但是如果离开的时候没玩过就不开心+1. 要求输出不开心的小朋友个数

例如

1 辆摇摇车，3 个小朋友

当数字为 112233 时，不开心为 0

当数字为 121233 时，2 在等待 1 后也玩上了，所以不开心为 0

当数字为 122313 时，由于 2 没等玩上就离开、3 玩上了（ 1 已经玩完了）所以不开心为 1

解

起初创建了几个 Class 写的时候发现没必要，最后用了两个 Set 解决。本题通过，得分 200

最后得分 90+0+200=290 ，没达到 300 推荐分，惜败（当然我菜是原罪，尤其第二题竟然没完成？！）。

继续找工作中。。。

leewangyang

2023-08-16 16:05:35 +08:00

第一题，如果两层循环外层是 A 内层是 B 的，如果 B 的 index 不会重置，而是单调增。可以 O(B)，再好一点就是 B 可以用二分查找去找。在 B 远大于 A 的时候，更优。
第二题，直接用个 map 存这个数字上一次出现位置，然后遍历依次加进去，如果出现重复，判断是不是小于距离，是就结束，不是就覆盖。用 hash 的 map ，一遍走完出结果。O(n)
第三题应该是第一个数字表示排队，第二个表示离开吧，按 op 说可以用 set 吧，进 set 和出 set 的时候任意时候 set 里面数量小于车数就是坐上了。