2023-03-25 20:49 已编辑 浙江大学 算法工程师 发布于北京
关注
3.25招行卡中心笔试 求指教
150分钟，16道单选题，2道编程题
第一题小红打boss，思路很简单遍历1-a就行，但是超时只过了60%多，明明是O(n)的复杂度
第二题01连续子串，用的回溯，测试用例也过了，但是只过了25%，超时
求ac大佬指点一下思路
第二题我的思路
以8 2 3 10111000为例，先找出切除的可能性[2, 3, 4, 6, 8]，切了之后判断另一半是否符合a/b倍数，进一步缩小到[2, 6, 8]的范围，即① 前2个一组 ② 前6个一组 ③ 前8个一组，三种情况，判断每种情况能不能再切分，如果不能再分了就计算全部改成0/1的次数，这就是回溯了。
第一题小红打boss，思路很简单遍历1-a就行，但是超时只过了60%多，明明是O(n)的复杂度
第二题01连续子串，用的回溯，测试用例也过了，但是只过了25%，超时
求ac大佬指点一下思路
第二题我的思路
以8 2 3 10111000为例，先找出切除的可能性[2, 3, 4, 6, 8]，切了之后判断另一半是否符合a/b倍数，进一步缩小到[2, 6, 8]的范围，即① 前2个一组 ② 前6个一组 ③ 前8个一组，三种情况，判断每种情况能不能再切分，如果不能再分了就计算全部改成0/1的次数，这就是回溯了。
全部评论
人才池是我家
东南大学 Java
T2确实难想，从后往前看，dp[n][0]表示以0结尾且前面都满足条件的最小代价，dp[n]可以由dp[n-ka]转移而来，但是其实dp[n-a]的计算也会包含前面的k，所以只需要dp[n][0]=max(dp[n-a][0]+dp[n-a][1])+diff(n-a,n)，diff表示区间内的非0数量，这个可以用前缀和维护，也就是把这段a长度都变为0,然后就像我上面说的dp[n-a][0]也会继续考虑前面a个0的情况所以这么转移没问题。接着就是dp[n][1]=max(dp[n-b][0],dp[n-b][1])+(b-diff(n-b,n))，不存在的地方存-1
monster121
字节跳动_后端开发
第一题找公因子比，100%了，第二题没有思路
S.I.R
门头沟学院 Java
第一题暴力列所有的因子比较过了，第二题同没有思路。。
牛客34973094号
华南理工大学 后端
我暴力列因数超时了 不知道为什么
你这个代码我看不懂
门头沟学院 Java
请问有面试消息了吗，怎么我还一直显示笔试中
摩力塔先辈
门头沟学院 后端
和lz一样63%，o(n)估计不行，当时没想到遍历1到根号n和根号n到n
dwtttttt
东南大学 前端工程师
第一题找boss的公因子就行了，第二题不会，return -1过了5%🤣
相关推荐
快手公司福利 941人发布 07-25 11:12
重庆大学 C++ 飞花断音：华为需要学历不高，但是很能干事儿，能吃苦也没怨言，愿意无偿加班，最好上有老下有小，不是独生子女，家庭条件不好，家在外地租房住，生活成本高，不会轻易跳槽，并且愿意接受低工资的奴仆任劳任怨地给任总的女儿买大别墅住
点赞 评论 收藏
分享
06-18 15:30
吉林化工学院 Java 程序员小白条：主要没亮点，项目也是网上的，平平无奇，那只能海投了，奖项总得有一些，然后就是现在最好是前后端都会，自己能做项目并且运维的，要么找星球项目改改，要么找个开源项目改改，自己能拓展功能才是主要的，跟做效率很低很低
点赞 评论 收藏
分享
点赞 评论 收藏
分享