携程笔试

今天这场最后一题怎么做啊？花一小时写个归并，结果只过了 4.45%
题目只给一个样例，自己造的数据也都过了，太奇怪了😅
全部评论
写了复杂度n^3的，自己试样例都没问题结果9%
2 回复 分享
发布于 09-18 20:58 浙江
这么难
点赞 回复 分享
发布于 09-19 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
门头沟学院 推荐算法
点赞 评论 收藏
分享
头像 会员标识
09-19 16:57
中南大学 算法工程师
点赞 评论 收藏
分享
评论
1
2
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 从顶到拉给所有面过的公司评分 #
49949次浏览 307人参与
# 小厂实习有必要去吗 #
57434次浏览 290人参与
# 宣讲会你有哪些意向不到的收获 #
7291次浏览 44人参与
# 产品薪资爆料 #
131729次浏览 840人参与
# 你面试被问到过哪些不会的问题？ #
43597次浏览 1151人参与
# 签约/解约注意事项 #
723716次浏览 4108人参与
# 水滴求职进展汇总 #
6906次浏览 35人参与
# 机械制造岗投递时间线 #
28717次浏览 372人参与
# 你怎么评价今年的春招？ #
131587次浏览 1369人参与
# 十一假期一定要干的事 #
18886次浏览 145人参与
# 你的国庆怎么过 #
28180次浏览 255人参与
# 你收到美的的感谢信了吗 #
43696次浏览 233人参与
# 为了求职，我做过的疯狂伪装 #
22457次浏览 479人参与
# 晒晒你的中秋福利 #
19754次浏览 141人参与
# 工作压力大怎么缓解 #
108522次浏览 1072人参与
# 顺丰求职进展汇总 #
57333次浏览 291人参与
# bilibili求职进展汇总 #
103333次浏览 876人参与
# 聊聊这家公司值得去吗 #
586037次浏览 3834人参与
# 职场破冰，你们都聊什么？ #
12626次浏览 99人参与
# 秋招的嫡长offer #
59344次浏览 483人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务