携程笔试

今天这场最后一题怎么做啊？花一小时写个归并，结果只过了 4.45%
题目只给一个样例，自己造的数据也都过了，太奇怪了😅
全部评论
写了复杂度n^3的，自己试样例都没问题结果9%
2 回复 分享
发布于 09-18 20:58 浙江
这么难
点赞 回复 分享
发布于 昨天 11:05 北京
dp可以做，存一下每个区间大于和小于的数字数量
点赞 回复 分享
发布于 09-18 21:58 陕西
我一看n≤2000，诶卧槽，直接用二维前缀和，空间换时间，n＾2的时间复杂度
点赞 回复 分享
发布于 09-18 21:55 河南
可以用离散化加树状数组优化时间到O(n^2 logn)，但是感觉这样偏竞赛的做法了
点赞 回复 分享
发布于 09-18 21:28 四川
能不能存每个区间的逆序数和顺序数，然后翻转就是总数减去逆序数加上顺序数，遍历一遍求最小值，感觉是n方
点赞 回复 分享
发布于 09-18 21:25 湖北
我的想法是找到连续递减最长的子数组，记录下标然后反转之后输出这个对，但是最后时间不够来不及验证了，而且不知道会不会超时
点赞 回复 分享
发布于 09-18 21:15 新加坡
直接输出n-1也是4.45%
点赞 回复 分享
发布于 09-18 21:14 北京
过了30%+，不是很懂为什么是答案错误
点赞 回复 分享
发布于 09-18 21:11 天津
第三题就过了10 纯暴力
点赞 回复 分享
发布于 09-18 21:06 安徽
应该是动规吧，但是我超时，只过了20多
点赞 回复 分享
发布于 09-18 21:06 吉林
我最后一题也4.45
点赞 回复 分享
发布于 09-18 21:02 浙江

相关推荐

09-18 20:41
百度_Java
点赞 评论 收藏
分享
09-18 20:35
门头沟学院 后端工程师
点赞 评论 收藏
分享
09-18 20:51
华南农业大学 Java
携程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了，感觉还行
投递携程等公司10个岗位
点赞 评论 收藏
分享
09-18 20:40
门头沟学院 推荐算法
点赞 评论 收藏
分享
昨天 16:31
提瓦特小学 前端工程师
点赞 评论 收藏
分享
评论
1
2
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 从顶到拉给所有面过的公司评分 #
47592次浏览 300人参与
# 产品薪资爆料 #
131345次浏览 840人参与
# 宣讲会你有哪些意向不到的收获 #
6599次浏览 44人参与
# 签约/解约注意事项 #
723281次浏览 4108人参与
# 聊聊这家公司值得去吗 #
584136次浏览 3828人参与
# 小厂实习有必要去吗 #
56909次浏览 289人参与
# 水滴求职进展汇总 #
6558次浏览 34人参与
# 你怎么评价今年的春招？ #
131253次浏览 1369人参与
# 机械制造岗投递时间线 #
28403次浏览 372人参与
# 十一假期一定要干的事 #
18508次浏览 145人参与
# 你的国庆怎么过 #
27806次浏览 254人参与
# 为了求职，我做过的疯狂伪装 #
21676次浏览 463人参与
# 晒晒你的中秋福利 #
19287次浏览 137人参与
# 工作压力大怎么缓解 #
108157次浏览 1072人参与
# 你收到美的的感谢信了吗 #
43393次浏览 233人参与
# bilibili求职进展汇总 #
102059次浏览 872人参与
# 职场破冰，你们都聊什么？ #
12181次浏览 99人参与
# 顺丰求职进展汇总 #
57050次浏览 290人参与
# 你面试被问到过哪些不会的问题？ #
41354次浏览 1117人参与
# 秋招的嫡长offer #
56669次浏览 464人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务