7.20 支付宝笔试

感觉很诡异,不太像考算法,有种小学奥数题的感觉。1h,两道题。

1、给一个数组a,一个空数组b,从前往后每次取a中一个数放进b的头部,然后逆转b。输出最后的b。

比如a是 1 2 3 4
b就依次是 
1
1 2
2 1 3
3 1 2 4
最后输出
3 1 2 4。

模拟的话会超时,找规律一趟遍历ac。
规律:
先从后到前把索引为偶数的放进b,然后从前到后把索引为奇数的放进b。
如果是数组长度是奇数,就把b再翻转一次。
输出b。

2、一个数组,数组里元素表示高度(非负)。定义一个合并操作,就是连续的相同的高度会合并成一个。数组输入的时候先做一次合并,不计入结果。然后开始操作,每一轮执行这两步:
  (1)数组中最低非零高度为k,每一个高度降低k。
  (2)进行合并。
当数组长度为1并且这个值为0的时候结束。

输出降低高度的轮数,以及每一次合并后的数组长度。

比如1 3 9 9 7,输入成1 3 9 7
然后开始操作:
第1次:0 2 8 6
第2次:0 6 4
第3次:0 2 0
第4次:0
结束。输出:
4
4 3 3 1

用模拟的方法过了50%,想分析规律,觉得跟数组初始状态中的每一个数连续相同数字个数有关,考虑dp但是时间不够了。
#笔试题目##蚂蚁集团#
全部评论
🤣果然模拟有问题,谢谢楼主。第二题我也没写出来。😂
点赞 回复
分享
发布于 2021-07-20 20:47
感觉好像不是这么理解的,0是不算的,我记得有个用例, 输入: 4 0 1 0 0 输出:  1 1
点赞 回复
分享
发布于 2021-07-21 10:07
淘天集团
校招火热招聘中
官网直投
第二题应该就是用并查集做吧,再用个最小堆,然后每次pop,都查一下左右是不是小于等于当前pop的值,符合就合并(注意一次要把相同值的都pop出来),并查集大小就是每次操作之后的数组长度。 时间复杂度nlogn
点赞 回复
分享
发布于 2021-07-21 13:25

相关推荐

3 3 评论
分享
牛客网
牛客企业服务