蚂蚁算法实习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
相关推荐
![](https://static.nowcoder.com/fe/file/oss/icon_job.png)
点赞 评论 收藏
分享
点赞 评论 收藏
分享
全站热榜
更多
创作者周榜
更多
正在热议
更多
# 大疆今年的机械笔试难吗? #
34471次浏览 406人参与
# 影石Insta360求职进展汇总 #
105931次浏览 936人参与
# 文科生还参加今年的春招吗 #
1712次浏览 20人参与
# 大疆的机械笔试比去年难吗 #
63333次浏览 575人参与
# 选择和努力,哪个更重要? #
36481次浏览 395人参与
# 24届市场营销薪资爆料 #
9010次浏览 62人参与
# 一人推荐一个值得去的通信/硬件公司 #
160251次浏览 1729人参与
# 如果公司降薪,你会跳槽吗? #
42606次浏览 325人参与
# 提前批的机械人,你们都有面试了吗 #
86152次浏览 929人参与
# 产品实习,你更倾向大公司or小公司 #
128708次浏览 1710人参与
# 产品薪资爆料 #
96700次浏览 814人参与
# 春招启动,你开始投递了吗? #
45282次浏览 435人参与
# 秋招前后对offer的期望对比 #
221713次浏览 1648人参与
# 大学四年该怎么过,才不算浪费时间? #
3314次浏览 32人参与
# 华为工作体验 #
149690次浏览 1052人参与
# 职场上哪些事情令人讨厌 #
12723次浏览 57人参与
# 机械人,你的第一份感谢信是谁给的 #
19864次浏览 257人参与
# 和牛牛一起刷真题 #
104922次浏览 2067人参与
# 你觉得机械有必要实习吗 #
33543次浏览 318人参与
# 2022毕业的你对23届的寄语 #
35060次浏览 533人参与