携程9.18笔试

第一题 水仙花数 直接a了
第二题 忘了也比较简单
第三题 位运算+贪心,最多异或和一次(不会证明),遍历数组,如果在该为上为1,则是n(总数) - cnt(该为上1的个数),如果是0则是cnt,乘以power(2,x)也就是该位的2次幂(基于异或的特性),总时间复杂度为O(nlogn)。
第四题 二维dp,反转的区间对左右两侧没影响,只要考虑[l,r]区间的逆序对数量,我本来想用O(n^3)水一下分的,没想到直接过了。正的算一遍dp[l][r]区间中的逆序对,反着在算一变,直接遍历区间总的减去正的区间加上反的区间,求最小值就过了。可以优化时间复杂度,我当时懒得写了,就直接暴力n^3水过去了。
用了一个小时a了,感觉还行
全部评论
第三题怎么看出来的最多异或和一次?
1 回复 分享
发布于 09-18 21:32 四川
可以给我看一下第二题代码吗,我有点呆了,我测试用例三个都是对的,提交百分之0通过自己都笑了
点赞 回复 分享
发布于 09-18 21:47 湖北
我也是O(n^3)只过了9%
点赞 回复 分享
发布于 09-18 21:31 四川
点赞 回复 分享
发布于 09-18 21:09 北京

相关推荐

09-18 16:36
已编辑
门头沟学院 Java
八股战士第一次倒在八股文上1. 实习没做多少东西就不问了2. 项目拷打3. 雪花算法如何实现的,有什么问题4. RabbitMQ如何保证消息顺序性,不丢失,不重复,不堆积5. BitMap统计活跃度,稀疏和稠密都是相同的长度该如何解决,我猜了个用图的那种稀疏矩阵方式,面试官说了个RoaringBitMap,没听说过6. 如何破坏双亲委派机制,答了重写loadclass和spi机制还问还有呢,实在不知道了7. 泛型的类型擦除和多态冲突为什么?怎么解决?8. 异常体系9. ioc和aop,aop实现方式,jdk和cglib谁的性能更高10. 复杂度O(nlogn)的排序算法11. 快排什么时候会退化12. 为什么比较型算法的时间复杂度最低是O(nlogn),好不容易在他的提示下联想到想到了排序组合有N!种,二叉树高度h的节点是2^h,所以h的高度最低是nlogn,然后还要追问我为什么这样,为什么是二叉,真服了二叉是他说的,确实不知道13. 最小生成树的两种方式14. prim算法是贪心实现的,为什么可以保证全局最优15. kruskal算法实现原理?是如何判断两个顶点不在同一个连通分量里的16. 并查集如何实现的17. 路径压缩是如何实现的18. DCL实现方式,如何实现禁止指令重排序的19. n个元素按顺序进栈,出栈有多少种情况?使用动规实现,写出状态转移方程20. 无反问
点赞 评论 收藏
分享
评论
8
6
分享

创作者周榜

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