网易笔试题--c++开发

1.给定一个字符串,输出以它作为开头的最短回文串,如noon输出noon,noo输出noon
2.给定一些物品和价值(数组),每样东西有三种操作:分给A,分给B,扔掉,在A与B分得的物品总价值相等的情况下,最少需要扔掉多少价值的东西?如[30,20,50,20],最少扔掉20,因为为A,B各分50, 20扔掉
3.有一堆排队的人,给定他们排队以及购买东西的时间,每个人可以单独购买东西,也可以与下一位一起购买,商店要等最后一个人买完后打烊,求商店最早打烊的时间。
样例:两个人,分别需要花20和25时间购买东西,如果一起买的话是40,所以最早结束的时间为40.
4.有一堆教授在一起讨论学术成果(n个),给出他们之间的认可关系,如1认可2,3认可4。规定,如果1认可2, 2认可3,则认为1认可3。求这些教授之中有多少对相互认可?输出对数即可。
-----------感觉做得不是特别好,有没有小伙伴来说说每道题的思路?

#网易##笔试题目#
全部评论
分东西这题其实是个经典dp,叫做双子塔,可以自己查一下;然后排队买东西也是dp,显然dp[j] = min(b[j]+dp[j-2], dp[j-1]+a[j]);教授互相认可是求强连通(求环),大小为x的环可以产生x(x-1)/2的关系,这个比较难。
3 回复 分享
发布于 2020-08-08 21:59
推荐一下自己,里面有前3道题的ac代码,第一题暴力,第二题dfs+剪枝,第三题dp. https://www.nowcoder.com/discuss/471012?source_id=profile_create&channel=1009
3 回复 分享
发布于 2020-08-08 17:19
第一题,把字符串拆成非回文串+回文串(回文串要尽量大),一个头指针从头开始向后滑动,如果判断出后面的子串是回文串就直接跳出。最后输出就是非回文+回文+非回文。 第二题,暴力DFS,每一个物理要么拿给1要么拿给2要么扔了,动态更新结果 第三题,DP,主要是后面转化为时间很麻烦 第四题,我用的是拓扑排序找闭环,自己写的有点问题没做出来
点赞 回复 分享
发布于 2020-08-08 21:45
借楼问下第三题,两个人分别花20和25分钟买东西,如果在一起买,不应该是25分钟可以买完吗?当时只顾做第二题,第三题就没看。。。
点赞 回复 分享
发布于 2020-08-08 20:50
第一题应该是MANACHER算法的变种  太恶心了   其他不知道了...
点赞 回复 分享
发布于 2020-08-08 17:12
第一题在牛客网做过 思路是把字符串a翻转成b 题目就变成了b在a里的第一个匹配字串(不然奇数偶数个还要分情况讨论 很麻烦) 第二题直接暴力搜索,对于每个物品只有3种选择 给a,给b,扔了 一共3^15种 肯定来得及 第三题dp[n]代表前面n个人最少一共要花多久 显然他为dp[n-1]+最后一个人花的时间 和dp[n-2]+最后两个人一起买花的时间 里的较小值 第四题没做出来,目测要用链表或者散列表 我不熟练 用矩阵数组只过了40%
点赞 回复 分享
发布于 2020-08-08 17:09

相关推荐

04-21 11:22
已编辑
中华女子学院 UE4
点赞 评论 收藏
分享
评论
2
6
分享

创作者周榜

更多
牛客网
牛客企业服务