20230829得物笔试AK代码

属于经典题型,动态规划、贪心,给的纯白板,自己写

一、 是否存在长度为x的回文子串

二、n栋楼总高度m,每栋楼之间高度差不超过1,求第x栋楼的最高高度

场景题:类似于LCR 033. 字母异位词分组

  1. A和B有相同K个收藏品认为爱好相似
  2. 具有传递性,即AB、AC相似则BC相似。
  3. 求爱好相似的用户(为一个群组),使用伪代码,并描述数据结构和时间复杂度

我的做法(并查集):对每个用户,判断是否和已在群组的用户相似,若相似则加入该用户所在群组

时间复杂度不确定,求讨论

  1. 对每个用户A,判断是否和已在群组的用户B相似
  2. 首先是循环获取两个用户A、B,两层循环就已经是O(n2)
  3. 判断两个用户是否相似
  4. 使用set存储用户的藏品
  5. 计算两个用户相同藏品数量O(n)
  6. 若相似,将A加入B用户所在群组
  7. 并查集union的时间复杂度是多少?
全部评论
并查集的复杂度主要在于findParent,尽量往平衡树去设置A,B的父子关系,查找和合并复杂度都在O(h)或者说O(logn)
1 回复 分享
发布于 2023-08-29 13:16 浙江
第一题一直卡91
点赞 回复 分享
发布于 2023-08-29 13:27 广东
第一题哪儿要得了这么复杂?
点赞 回复 分享
发布于 2023-08-29 13:31 浙江
太强啦大佬❤️❤️
点赞 回复 分享
发布于 2023-08-29 14:20 广东
老哥,第二题你的这种写法挺巧妙的,应该属于什么算法?不能算是贪心吧?
点赞 回复 分享
发布于 2023-08-29 14:56 江苏
第一题遍历所有长为x的子串判断是否为回文串,但是一直55%不知道哪里有问题
点赞 回复 分享
发布于 2023-08-29 15:33 浙江
大佬,能不能解释一下为什么第二题的for循环里,第一次就要-3啊(如果不考虑到边上的情况)
点赞 回复 分享
发布于 2023-08-29 17:21 上海
第二题的这个思路好巧,我今天用二分,想了半天才把公式推导明白
点赞 回复 分享
发布于 2023-08-30 18:27 辽宁

相关推荐

02-22 20:28
重庆大学 Java
程序员牛肉:首先不要焦虑,你肯定是有希望的。 首先我觉得你得好好想一想自己想要什么。找不到开发岗就一定是失败的吗?那开发岗的35岁危机怎么说?因此无论是找工作还是考公我觉得你都需要慎重的想一想。但你一定要避开这样一个误区:“我是因为找不到工作所以不得不选择考公”。 千万不要这么想。你这个学历挺好的了,因此你投后端岗肯定是有面试机会的。有多少人简历写的再牛逼,直接连机筛简历都过不去有啥用?因此你先保持自信一点。 以你现在的水平的话,其实如果想要找到暑期实习就两个月:一个月做项目+深挖,并且不断的背八股。只要自己辛苦一点,五月份之前肯定是可以找到暑期实习的,你有点太过于高看大家之间的技术差距了。不要焦虑不要焦虑。 除此之外说回你这个简历内容的话,基本可以全丢了。如果想做后端,先踏踏实实做两个项目再说+背八股再说。如果想考公,那就直接备战考公。 但是但是就像我前面说的:你考公的理由可以是因为想追求稳定,想追求轻松。但唯独不能是因为觉得自己找不到工作。不能这么小瞧自己和自己的学历。
点赞 评论 收藏
分享
评论
10
43
分享

创作者周榜

更多
牛客网
牛客企业服务