华为笔试0911

华为笔试0911，有史以来最简单的一次笔试。一小时不到，写完了。吐槽一下华为笔试的那个编辑器和页面真的窜稀。样例不能复制，要一个一个手打，那个编译器也没有代码提示，也没有一些基础的早相是找相同或者之类的功能写代码，只能一个一个戳，不知道的还以为是在txt上写。
三道题都挺简单的，甚至我觉得可能第一道题难度还稍微大一点，容易被误导。
第一题丢垃圾，给定一个n×m的矩阵，用二代表着为空，用一代表着有一个小区，用零代表着有一个垃圾站。然后还有个负数代表着是有个障碍物。问，每个小区丢垃圾所需要的步数的和最小值为多少？利用bfs，开始把所有的垃圾场压进队列当中，然后正常bfs找每个位置上下左右相邻的位置，首先判断这个位置是不是空旷的，能不能到达，曾经有没有到达？如果判断到当前位置是小区，那么就把总答案加上当前的步数即可。利用bfs的特性，可以保证每个小区到垃圾场的位置一定都是最近的。
第二题堆箱子，给定n个箱子，最大1000个，然后给出每个箱子的长宽高，求从上往下堆箱子给下面的箱子长宽高都要大于上面的箱子，留在符合条件下面搭建出来的箱子，最高总高度。那其实就是简单的dp，甚至连dp都说不上。首先，对所有箱子进行一次排序，把它们按照高度排序。（不排序只过25%的可以判断一下是不是这个原因）。然后遍历每一个箱子，对于每一个箱子，找这个箱子上面的所有箱子都比他长宽高都小的，如果前面的某一个箱子假设为j比现在箱子小。dp（now）＝max(dp(now),dp(j)+high(now)).这样就可以得到一前箱子为底可以搭出的最高的高度，一路往下最后一可以找到所有箱子的最高高度。
第三题是一个覆盖dp题，其实实际跟第二题是类似的，给定最多n为一万个站点，在有最多m为十万个方案，个方案有一个lr和val.代表着这个方案，需要l站点一直到r站点里面的所有站点，并且可以带来VAL个收益.问，现在给出所有方案，最多能够赚多少钱？实际也跟第二题类似，有点贪心的味道。先把每一个方案按照他的r进行排序（为什么按照r排序这是一个贪心的思想，我很难解释得清自己举两个例子捋一下可能就懂了）。把它们放到一个队列里面，排好序，不停的拿出头部方案，就是当前最左边的方案。然后遍历每一个站点。两种情况第一种就是头部的方案，他的r的位置也大于当前的位置