阿里笔试419 45minAK题解

写了大概45min 感觉挺水的~
第一题写了20min 第二题写了10min 第三题写了15min 
T1 给定一个序列,问有多少个区间的众数次数>=k
sol:考虑two-pointer。枚举左端点,寻找最小的右端点是的众数次数>=k
推导后发现需要支持以下功能
1.增加某一个数的出现次数
2.减少某一个数的出现次数
3.查询众数的出现次数(即出现次数最多的数字的出现次数)
这些功能可以抽象化可以理解为维护一个集合,支持单点修改,支持查询最大值
因此考虑使用堆来实现,具体实现过程类似dijkstra找最短节点的过程。
T2 题意大概就是模拟一个消消乐的过程
sol:bfs暴力模拟消除的过程,而下落的过程可以逐行维护每一列的高度来模拟实现。
T3 求所有长度为n的字符串有多少个长度为3的回文子串
考虑动态规划
考虑一个字符串的最后两个字符的形式,要么是"aa",要么是“ab”。
不妨记
"aa"结尾的字符串的数量为x[n],记这些字符串的权值和为fx[n]。
记"ab"结尾的字符串的数量为y[n],记这些字符串的权值和为fy[n]。

"aa"有两种转移方式——>"aaa",“aab”
其中"aaa"有1种方式。
其中"aab"有25种方式,指的是填与"a"不同的25个字符。

"ab"有三种转移方式——>"aba",“abb”,"abc"
其中"aba"有1种方式。
其中"abb"有1种方式。
其中"abc"有24种方式,指的是填与"a"不同的25个字符。

这里简单写一下dp的转移方程
x[n]=x[n-1]+y[n-1]
fx[n]=x[n-1]+fx[n-1]+y[n-1]
y[n]=25x[n-1]+25y[n-1]
fy[n]=25fx[n-1]+y[n-1]+25fy[n-1]
直接暴力dp复杂度为O(n)
考虑使用矩阵快速幂优化(类似快速求斐波那契数列)
即可做到O(logn)
全部评论
第三题,直接(n-2)*26^(n-1),特判n<3,快速幂即可
2 回复 分享
发布于 2023-04-19 22:29 湖北
我先膜了
2 回复 分享
发布于 2023-04-19 21:53 甘肃
太猛了吧、
1 回复 分享
发布于 2023-04-20 15:38 香港
阿里数字供应链部门刚开始春招,欢迎同学踊跃报表。查看个人首页帖子 查看部门介绍和扫码线上投递简历。 https://www.nowcoder.com/discuss/472422701500485632
点赞 回复 分享
发布于 2023-04-20 15:18 浙江
这就是神仙卧槽
点赞 回复 分享
发布于 2023-04-19 21:49 辽宁

相关推荐

昨天 16:40
已编辑
门头沟学院 C++
26学院本太难了,很多公司机筛就给我刷了。机会都难拿到如果是简历存在问题也欢迎拷打————————————————————分割线——————————————————————2026.3.4更新:发完贴之后,时不时投递又收到了不少的笔试/面试邀请。主要是之前投递简历出去之后基本上都是沉默状态,年后好转了不少timeline:2026.01.21&nbsp;文远知行笔试,半年多没刷算法题&nbsp;-&gt;挂&nbsp;(后续HR说春招可以重新安排笔试)2026.2.4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;小鹏汇天&nbsp;技术一面,第二周收到结果&nbsp;-&gt;挂2026.2.12&nbsp;&nbsp;&nbsp;大众Cariad代招&nbsp;技术二面&nbsp;-&gt;Offer2026.2.28&nbsp;&nbsp;&nbsp;多益网络技术面试,由于风评太差,一直在犹豫要不要接面试&nbsp;-&gt;推迟-----------分割线-----------2026.3&nbsp;月前的某一天,临时去电网报名了二批计算机岗位的笔试2026.3.6&nbsp;从上家公司实习离职,氛围最好的一家公司,leader&nbsp;说可以帮忙转正,但是流程太长,而且我们部门据说只有一个&nbsp;hc,更想要研究生,我很有可能是会被签外包公司在这里干活,就离职了。2026.3.9&nbsp;入职新公司,大众Cariad&nbsp;以外部公司的身份进组,项目组签了三年,后续三年应该都可以在这里呆,不知道有没有希望原地跳槽。2026.3.10&nbsp;电网考试居然说我通过资格审查了,短信约我去参加资格审查,请假一天,买了&nbsp;12&nbsp;号晚上的机票回成都2026.3.15&nbsp;参加国家电网计算机类笔试2026.3.17&nbsp;电网出成绩了,感觉很低。觉得已经🈚️了2026.3.18&nbsp;收到电网面试通知,通知&nbsp;3.22-3.25&nbsp;这个时间去面试,我的岗位只招&nbsp;1&nbsp;个人。据说面试只有&nbsp;2-3&nbsp;人,不知道能不能成功----------分割线-----------2026.3.21&nbsp;电网面试结束,感觉回答的还勉勉强强,大概是2个岗位分别招1个人,一共11人面试,实际来了9人2026.3.27&nbsp;出面试成绩,满分100分,早上10:20左右发现面试成绩46,我震惊了,没截图,后面过了十分钟重新看发现面试成绩给我改成58了。但同样震惊。朋友问我是不是把面试官打了,哈哈
点赞 评论 收藏
分享
03-04 07:14
门头沟学院 C++
黑皮白袜臭脚体育生:老板:都给工作机会了还想要工资,哪来这么多好事
点赞 评论 收藏
分享
评论
10
35
分享

创作者周榜

更多
正在热议
更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务