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的次数，这就是回溯了。
全部评论
monster121
字节跳动_后端开发
第一题找公因子比，100%了，第二题没有思路
人才池是我家
美团_后端开发(准入职员工)
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
S.I.R
门头沟学院 Java
第一题暴力列所有的因子比较过了，第二题同没有思路。。
dwtttttt
东南大学 前端工程师
第一题找boss的公因子就行了，第二题不会，return -1过了5%🤣
摩力塔先辈
门头沟学院 后端
和lz一样63%，o(n)估计不行，当时没想到遍历1到根号n和根号n到n
你这个代码我看不懂
门头沟学院 Java
请问有面试消息了吗，怎么我还一直显示笔试中
牛客34973094号
华南理工大学 后端
我暴力列因数超时了 不知道为什么
相关推荐
点赞 评论 收藏
分享
2024-11-10 22:06
上海震旦职业学院 前端工程师 
点赞 评论 收藏
分享
查看14道真题和解析