2023-09-10 16:00 门头沟学院 C++
关注
阿里云秋招笔试题解分享0910
上午lc周赛T4不会做，已经不知道是第几次连lc都做不出了，对水平下滑怀疑人生，一开始看错题，想了十多分钟没法下手，心态崩了。。。还好先做完T2T3后回来再看发现看错题了。。第一题看成把不优秀的变优秀了
T1:1-n的排列p，pos[p[i]]=i , 给出一个长度为m的优秀数组a ，优秀的定义是pos[a[i]]<pos[a[i+1]]<=pos[a[i]]+d
要让优秀变成不优秀，要么让相邻两个交叉，要么让相邻两个超过d，取min就行了
也就是枚举for(i=2;i<=m;i++) smin(ans,pos[a[i]]-pos[a[i-1]]),smin(ans,d-(pos[a[i]]-pos[a[i-1]]-1))，复杂度O(n)
T2:有长度为n的数组a，每次操作使得a[i]+=i ，问最少多少次使得a数组严格递增
可以知道一次操作对于每个a[i]+=i,a[i-1]+=i-1，就让他们差距了1 ,那答案就是相邻两个差距最大的，需要追的最久的
所以for(int i=2;i<=n;i++) ans=max(ans,a[i-1]-a[i]+1) 复杂度O(n),当然二分答案也行，加个log
T3: 有x个a，y个b，不能超过k个连续相同的字母，问字典序最大的一个，构造不出输出-1
考虑不可行的情况，就是x>(y+1)*k || y>(x+1)*k
接下来构造分为3个阶段，假设k=3
第一阶段 bbbabbba.... 因为我们肯定希望b能尽可能放前面，而连续不超过k个就是这样
第二阶段 bbbabbba... bbaab
第三阶段 bbbabbba... bbaab aaabaaabaaa
首先考虑第三阶段，此时x=(y+1)*k ，只能连续放k个a以后放个b，然后最后也是k个a结束
然后考虑第二阶段，发现想要放第3个b但是放不了就放了a，由于此时我们再放一个b，就会导致a会超过k个
所以需要放一些a然后放一个b后进入第三阶段，因为第三阶段是无可奈何的阶段，但我们此时还是想要把1个b尽可能提前
那么第二阶段进入第三阶段的条件就是当x=(y+1-1)*k时，此时可以把一个b放这里，然后后面只能按第三阶段的方法构造了。
#阿里##阿里云##笔试#
T1:1-n的排列p，pos[p[i]]=i , 给出一个长度为m的优秀数组a ，优秀的定义是pos[a[i]]<pos[a[i+1]]<=pos[a[i]]+d
要让优秀变成不优秀，要么让相邻两个交叉，要么让相邻两个超过d，取min就行了
也就是枚举for(i=2;i<=m;i++) smin(ans,pos[a[i]]-pos[a[i-1]]),smin(ans,d-(pos[a[i]]-pos[a[i-1]]-1))，复杂度O(n)
T2:有长度为n的数组a，每次操作使得a[i]+=i ，问最少多少次使得a数组严格递增
可以知道一次操作对于每个a[i]+=i,a[i-1]+=i-1，就让他们差距了1 ,那答案就是相邻两个差距最大的，需要追的最久的
所以for(int i=2;i<=n;i++) ans=max(ans,a[i-1]-a[i]+1) 复杂度O(n),当然二分答案也行，加个log
T3: 有x个a，y个b，不能超过k个连续相同的字母，问字典序最大的一个，构造不出输出-1
考虑不可行的情况，就是x>(y+1)*k || y>(x+1)*k
接下来构造分为3个阶段，假设k=3
第一阶段 bbbabbba.... 因为我们肯定希望b能尽可能放前面，而连续不超过k个就是这样
第二阶段 bbbabbba... bbaab
第三阶段 bbbabbba... bbaab aaabaaabaaa
首先考虑第三阶段，此时x=(y+1)*k ，只能连续放k个a以后放个b，然后最后也是k个a结束
然后考虑第二阶段，发现想要放第3个b但是放不了就放了a，由于此时我们再放一个b，就会导致a会超过k个
所以需要放一些a然后放一个b后进入第三阶段，因为第三阶段是无可奈何的阶段，但我们此时还是想要把1个b尽可能提前
那么第二阶段进入第三阶段的条件就是当x=(y+1-1)*k时，此时可以把一个b放这里，然后后面只能按第三阶段的方法构造了。
#阿里##阿里云##笔试#
全部评论
前端实习fox
门头沟学院 前端工程师
哥字节能转正不
别动我的指针
门头沟学院 研发工程师
大佬T3写的有点乱，能不能编辑一下？我也是贪心做的，没做出来，太菜了
奔是波霸
电子科技大学 Java
大佬牛
binarycopycode 楼主
楼主 门头沟学院 C++
怎么重发一遍还是少一句，牛客什么辣鸡 , pos[a[i]]<pos[a[i+1]]<=pos[a[i]]+d
相关推荐
查看11道真题和解析