携程笔试9.7

贴一个t4的做法：维护前缀和，遇到0加一，遇到1减一。对于每一个左端点来说，合法的右端点是这个区间的前缀和值都大于等于左端点的前缀和值。因此考虑记录每一个位置的前缀和值，查询时二分找到左端点的第一个小于左端点的前缀和值的位置，减一下就得到对应的区间对答案的贡献。时间复杂度O(nlogn)。
全部评论
这个 s = " " + s 学到了
1
送花 回复
分享
发布于 2023-09-07 23:49 北京
我直接把前缀数组所有项加起来就过了，没二分查找
点赞
送花 回复
分享
发布于 2023-09-08 13:45 江西
滴滴
校招火热招聘中
官网直投
请教一下：`查询时二分找到左端点的第一个小于左端点的前缀和值的位置` 前缀和数组不是升序数组，是怎么通过二分找到的？
点赞
送花 回复
分享
发布于 2023-09-10 21:03 上海

相关推荐

头像 头像
许愿wangye
04-25 20:54
已编辑
重庆邮电大学 计算机类
点赞 评论 收藏
转发
头像
R1skk
04-22 16:04
携程_Java开发实习生(实习员工)
点赞 评论 收藏
转发
头像
求个offer11
04-26 10:41
武汉理工大学 计算机类
点赞 评论 收藏
转发
头像
大摆哥
05-06 21:12
西南大学 计算机类
点赞 评论 收藏
转发
头像
奔跑的卡西莫多
05-07 16:22
门头沟学院 电子信息类
点赞 评论 收藏
转发
6 10 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
745016次浏览 11905人参与
# 你的工作大概什么时候入职？ #
2378次浏览 31人参与
# 海康威视求职进展汇总 #
93920次浏览 1129人参与
# 百度工作体验 #
23678次浏览 243人参与
# 2022届毕业生现状 #
320173次浏览 4434人参与
# 今年形式下双非本找得到工作吗 #
7280次浏览 157人参与
# 你的秋招进行到哪一步了 #
358222次浏览 6308人参与
# 产品实习，你更倾向大公司or小公司 #
37252次浏览 577人参与
# 非技术岗是怎么找实习的 #
75598次浏览 1413人参与
# 比亚迪求职进展汇总 #
166518次浏览 1234人参与
# 你觉得比亚迪今年还有春招吗？ #
46009次浏览 331人参与
# 学历对求职的影响 #
132980次浏览 1510人参与
# 面试等了一周没回复，还有戏吗 #
41066次浏览 501人参与
# 浅聊一下我实习的辛苦费 #
82295次浏览 769人参与
# 0offer是寒冬太冷还是我太菜 #
416836次浏览 4833人参与
# 铜五铁六真的存在吗？ #
28889次浏览 301人参与
# 考研失败就一定是坏事吗？ #
20434次浏览 215人参与
# 通信硬件人笔面经互助 #
114479次浏览 2283人参与
# 荣耀求职进展汇总 #
66289次浏览 669人参与
# Offer比较，你最看重什么？ #
51277次浏览 492人参与
牛客网
牛客企业服务