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的次数,这就是回溯了。
全部评论
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
3 回复 分享
发布于 2023-03-25 22:58 江苏
第一题找公因子比,100%了,第二题没有思路
3 回复 分享
发布于 2023-03-25 20:37 北京
第一题暴力列所有的因子比较过了,第二题同没有思路。。
1 回复 分享
发布于 2023-03-25 20:39 陕西
我暴力列因数超时了 不知道为什么
点赞 回复 分享
发布于 2023-04-09 22:58 广东
请问有面试消息了吗,怎么我还一直显示笔试中
点赞 回复 分享
发布于 2023-04-03 11:28 湖南
和lz一样63%,o(n)估计不行,当时没想到遍历1到根号n和根号n到n
点赞 回复 分享
发布于 2023-03-26 09:17 北京
第一题找boss的公因子就行了,第二题不会,return -1过了5%🤣
点赞 回复 分享
发布于 2023-03-25 23:41 上海

相关推荐

面试官全程关摄像头1.自我介绍一下2.React和Vue哪个更熟悉一点3.你在之前那段实习经历中有没有什么技术性的突破(我只是实习了44天工作28天,我把我能说的都说了)4.你封装的哪个表单组件支不支持动态传值5.自己在实习阶段Vue3项目封装过hook吗6.hook有什么作用7.Vue2和Vue3的响应式区别(我说一个是proxy是拦截所有的底层操作,Object.defineProperty本身就是一个底层操作,有些东西拦截不了,比如数组的一些操作还有等等,面试官就说实在要拦截能不能拦截????我心想肯定不行呀,他的底层机制就不允许吧)8.pinia和vuex的区别(这个回答不出来是我太久没用了)9.pinia和zustand的区别,怎么选(直接给我干懵了)(我说react能用pinia吗  他说要用的话也可以)10.渲染一万条数据,怎么解决页面卡顿问题(我说分页、监听滚轮动态加载,纯数据展示好像还可以用canvas画)(估计是没说虚拟表单,感觉不满意)11.type和interface的区别12.ts的泛型有哪些作用(我就说了一个结构相同但是类型不同的时候可以用,比如请求响应的接口,每次的data不同,这里能用一个泛型,他问我还有什么)13.你项目用的是React,如果让你再写一遍你会选择什么14.pnpm、npm、yarn的区别15.dependencies和devdependencies的区别总而言之太久没面试了,上一段实习的面试js问了很多。结果这次js一点没问,网络方面也没考,表现得很一般,但是知道自己的问题了  好好准备,等待明天的影石360和周四的腾讯了  加油!!!
解zj:大三的第一段面试居然是这样的结局
查看15道真题和解析
点赞 评论 收藏
分享
评论
1
15
分享

创作者周榜

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