蚂蚁算法实习2024.3.26笔试
不小心做了实习笔试,记录一下。选择题一直不太会,略过。
第一题题意:数字符串(长度n<20)只包含一些特定字符的回文子串。
做法:根据数据范围,直接二进制枚举。时间复杂度O(n * 2^n)。
第二题题意:。。模拟某个机器学习数据处理。。
做法:输入对写c++的不太友好,py3模拟一下。
第三题题意:给定一个01字符串(长度n<1e5),开始和结束位置为1,第一问,求从开始到结束位置最少跳几次,跳跃规则只能跳在1上,若上一次跳了x步,当前可以向前跳2x步或者1步,否则只能跳1步。第二问,当没有策略从起始位置跳到最后位置时,问最少把多少个0改为1能够使得第一问满足。
做法:常规动态规划。注意到数据范围n<1e5,对于2的幂次小于19。
所以对于第一问,记dp[i][j]表示当前位置i,表示能够向前跳2^i的跳到当前位置的最小跳跃次数,转移方式特判一下j为0的时候,dp[i][0] = min{dp[i-(1< 对于第二问,记dp[i][j]表示当前位置i,表示能够向前跳2^i的最小次数跳到当前位置最小需要填几次0。转移方程对于当前为1或者0分开考虑,也要特判j为0的情况。对于s[i] == 1时候,dp[i][0] = min{dp[i-(1<
1 回复 分享 发布于 2024-03-26 21:00 新加坡
点赞 回复 分享 发布于 2024-03-26 20:20 上海
点赞 回复 分享 发布于 2024-03-26 21:24 湖北
第一题题意:数字符串(长度n<20)只包含一些特定字符的回文子串。
做法:根据数据范围,直接二进制枚举。时间复杂度O(n * 2^n)。
第二题题意:。。模拟某个机器学习数据处理。。
做法:输入对写c++的不太友好,py3模拟一下。
第三题题意:给定一个01字符串(长度n<1e5),开始和结束位置为1,第一问,求从开始到结束位置最少跳几次,跳跃规则只能跳在1上,若上一次跳了x步,当前可以向前跳2x步或者1步,否则只能跳1步。第二问,当没有策略从起始位置跳到最后位置时,问最少把多少个0改为1能够使得第一问满足。
做法:常规动态规划。注意到数据范围n<1e5,对于2的幂次小于19。
所以对于第一问,记dp[i][j]表示当前位置i,表示能够向前跳2^i的跳到当前位置的最小跳跃次数,转移方式特判一下j为0的时候,dp[i][0] = min{dp[i-(1<
全部评论
二进制枚举可以的,第一题用回溯不知道怎么一直报错,可能是有些边界条件不对
对于s[i] == 1时候,dp[i][0] = min{dp[i-(1<<j)][j]},j不是0时为dp[i][j] = min{dp[i-(1<<j - 1)][j-1]}。对于s[i] == 0时候,dp[i][0] = min{dp[i-(1<<j)][j] + 1},j不是0时为dp[i][j] = min{dp[i-(1<<j - 1)][j-1] + 1}。
tql
相关推荐
点赞 评论 收藏
分享
01-17 10:48
南昌理工学院 Java 点赞 评论 收藏
分享


腾讯
| 校招
| 超多精选岗位
点赞 评论 收藏
分享
全站热榜
更多
创作者周榜
更多
正在热议
更多
# 面试被问“你的缺点是什么?”怎么答 #
5352次浏览 85人参与
# 租房找室友 #
7847次浏览 53人参与
# 水滴春招 #
14936次浏览 170人参与
# 25届秋招公司红黑榜 #
238124次浏览 988人参与
# 入职第四天,心情怎么样 #
10991次浏览 56人参与
# 简历无回复,你会继续海投还是优化再投? #
48526次浏览 560人参与
# 机械人选offer,最看重什么? #
69058次浏览 449人参与
# 牛友们的论文几号送审 #
16001次浏览 500人参与
# 软开人,你觉得应届生多少薪资才算合理? #
81338次浏览 496人参与
# 国企还是互联网,你怎么选? #
109105次浏览 852人参与
# 22届毕业,是读研还是拿外包offer先苟着 #
4639次浏览 27人参与
# 机械人,你的秋招第一份简历被谁挂了 #
125792次浏览 1925人参与
# 总结:哪家公司面试体验感最差 #
33256次浏览 169人参与
# 职场新人生存指南 #
198874次浏览 5499人参与
# 安利/避雷我的专业 #
62078次浏览 481人参与
# 读研or工作,哪个性价比更高? #
26035次浏览 356人参与
# 听劝,这个公司值得去吗 #
382308次浏览 1515人参与
# 参加完秋招的机械人,还参加春招吗? #
26699次浏览 275人参与
# 你觉得早上几点上班合适? #
61652次浏览 256人参与
# 如果重来一次你还会读研吗 #
155659次浏览 1705人参与
# 你们的毕业论文什么进度了 #
900510次浏览 8944人参与