剑齿虎的尾巴

2023-09-09 11:57 清华大学深度学习

关注

美团笔试0909

前三题签到题，最后一题：
定义数组的权值为其任意两个元素的异或之和，求数组a的所有连续子数组的权值之和

我用的二维dp，只开辟一维数组（否则爆内存），python只过15%，超时了（限制2秒），麻烦大佬们帮忙看看要怎么优化

是不是求数组的两两异或和有比较快的求法呢？

全部评论

推荐最新楼层

牛客587997173号

中国科学技术大学人工智能

没有用dp，思路是a[i]与a[j]的出现次数是(i+1)*(n-j)，两个for循环也是15%

4 回复分享

发布于 2023-09-09 12:05 安徽

柳岸风残月_

雀魂学院 C++

2 回复分享

发布于 2023-09-09 13:23 河南

清华大学 C++

没做这套，但是看舍友做了。。考虑f(i)为结尾为i的答案，等于f(i-1) 1*a(i)^a(0) 2 * a(i)^a(1) ... (i-1) * a(i) ^ a(i-1)。所以我们想要个异或的前缀和，前缀和一般是能预处理出来的，但是这里带一个系数，如果a(k) （k<i）和 a(i)的某一位不相等，它会给k 1次贡献。所以你考虑前i-1个数每一个数在32位里的贡献，每个数k的贡献要乘以系数k 1。具体来说，设zeros[n][32] ones[n][32]为0，a[1]是3，那么ones[1][0] ones[1][1]分别加2，zeros[1][2-32]分别加2。a[i]的某位是0，就跟ones[i-1][那一位]去求，反之亦然。

1 回复分享

发布于 2023-09-09 13:06 北京

空大数据开发工程师

分享一个NlogN思路，线性遍历，按二进制统计已遍历元素的信息，即每个二进制位上总共出现几次1几次0，算新的元素对结果的贡献就只需要遍历每个二进制位上的信息（按位计算符合分配律），时间是logN，总共NlogN

1 回复分享

发布于 2023-09-09 12:22 北京

北京大学 C++

按位算，对于每一位都记录0和1的前缀贡献和和以及后缀贡献和

1 回复分享

发布于 2023-09-09 12:12 北京

华东师范大学算法工程师

第四题nlogn做法，算贡献就好了

1 回复分享

发布于 2023-09-09 12:03 上海

华南理工大学 C++

我C++也是15，O(n^2)，搞不懂啊搞不懂

1 回复分享

发布于 2023-09-09 12:02 广东

麦克斯翼虎

华南理工大学算法工程师

我用Hash Map辅助计算，超内存了。华✌，请教下，你第三题怎么A的？我用的贪心从1开始递增累加，但是没全通过测试用例

1 回复分享

发布于 2023-09-09 12:02 广东

University of California Los Angeles 算法工程师

请问有没有哪位伙伴可以私发一下差异值和权值那两道题的代码和完整思路吗，第一次笔试缺乏经验做得不好，想看看正解，找找思路上哪里有问题，非常感谢！🥺

点赞回复分享

发布于 2023-09-15 09:35 美国

门头沟学院 C++

哪位佬能贴下第二题。。。我死活16%。。。

点赞回复分享

发布于 2023-09-09 12:22 陕西

淘气的小刺猬拒绝996

清华大学推荐算法

同15tle，感觉得做个去重？

点赞回复分享

发布于 2023-09-09 12:11 北京

精神华科人

武汉大学运维工程师

java 选手也是过15，二维数组爆内存了，最后没时间了

点赞回复分享

发布于 2023-09-09 12:11 湖北

牛客648544274号

香港中文大学（深圳）量化分析

有无大佬讲一下第三题是什么思路，我咋整都一个没过

点赞回复分享

发布于 2023-09-09 12:10 广东

牛客996849079号

门头沟学院算法工程师

我也卡15 我记录了当前子串的前一个子串的值的感觉没法继续优化了啊

点赞回复分享

发布于 2023-09-09 12:07 广东

茅台学院 C++

01的那道题只a了92是少考虑了啥

点赞回复分享

发布于 2023-09-09 12:05 江苏

科大讯飞_算法工程师

C随便写了个O(n²)的，果然TLE了，卡20%，不过两两异或是有什么快速解吗？依稀记得异或貌似有一个定理？记不太清

点赞回复分享

发布于 2023-09-09 12:04 江苏

想上岸的小菜鸡

芜湖信息技术职业学院产品经理

团子这里大概要多少分才能进面呀

点赞回复分享

发布于 2023-09-09 12:04 浙江

复旦大学算法工程师

第四题一样过15 第三题有没有佬解答下只过了16.67

点赞回复分享

发布于 2023-09-09 12:04 上海

长日的假面

华中科技大学 C工程师

第三题怎么过兄弟们

点赞回复分享

发布于 2023-09-09 12:02 湖北

要暴富的小鱼干很苗条

贵州师范大学求是学院算法工程师

我也是先n^2复杂度，但只过了15%，憋了半小时写了个线性算法只过了75%...

点赞回复分享

发布于 2023-09-09 12:01 浙江

05-26 22:15

门头沟学院 Web前端

字节跳动飞书多维表格实习面经（三面挂）

一面：自我介绍实习主要做的啥事件循环 console.log('start'); setTimeout(() => { console.log('children2'); setTimeout(function() { console.log('children8'); }, 0) ; Promise.resolve().then(() => { console.log('children3'); }) }, 0); new Promise(function(resolve, reject) { console.log('children4'); setTimeout(functi...

查看25道真题和解析

点赞评论收藏

分享

05-29 17:11

江苏省宝应中学后端

2024年10月10日上海某百人小厂已OC

公司是一个百余人的小公司公司的主要业务不是很熟悉 但是据说的是技术比较花 啥都有先是在boss上让我看了一个页面 然后要用React写前端 Java写后端后端一共五个接口 花了三小时完成前端 因为没接触过React 特地去学了一下 花了一天完成了页面开发前后端成功交互代码发给了面试官 视频给面试官看了一下后 半小时后就约了电话面试开始提问1. 讲一下spring后端架构2. 怎么搭建crud后端框架 先干嘛 后干嘛3. 讲一下如果有个需求是登录的话 前端拿到的响应数据中的data里面是什么4. 前端如何校验登录状态是否过期5. 讲一下前端js和ts的区别 我看你前端写的是js 能不能尝试用ts...

查看18道真题和解析牛客算法校招 Java... 面试问题记录

点赞评论收藏

分享

04-08 10:36

已编辑

华南理工大学 C++

大伙面腾讯的时候有这个环节吗

  大伙面试的时候有这个环节吗，我担心被诈骗了

梁州壮士：背调，查简历造假的

点赞评论收藏

分享

04-22 15:13

已编辑

两周了，估计是凉了

HR劝我先签一个保底，我估计是没HC了  更新：录用评估未通过，终于不用痛苦的等待了

爱吃肉的伊登在写日记：不愧是华子的儿子一样出声

新凯来求职进展汇总

点赞评论收藏

分享

05-27 20:10

已编辑

门头沟学院产品经理

2025年6月毕业者，出列😭！

时间一转眼就过去了三年一切在我心里开得好皎洁现在倒计时也不剩几天开始的开始 我们都是孩子踏入校园之后，没想到时间节点都只能匆匆一眼2012、2015、2018、2022、2025对00生来说是毕业也曾是入学的日子但2025，要进入的是社会大学😭年长后的记性太差人生阶段好像只能划分 童年 大学 在人间😭回来吧！我愿少翘一次专业课，只为能在课堂多看她一堂😭回来吧！我再也不压力带我掉分的朋友，峡谷海岛我都陪你去闯😭回来吧！我能再忍一次打鼾的室友，外卖和泡面都只有和你一起吃才香😭我只想要拉住流年好好地说声再见立身回望没有儿时幻想的辉煌风光只有逐渐认清现实的自洽和解能注销得了的图书馆证注销不了...

ZywOo_求职版：真要打鼾舍友回来你又不乐意了

牛客激励计划好好告别我的学生时代

点赞评论收藏

分享

评论

3

11

全站热榜

更多

字节暑期补捞

热聊中

创作者周榜

更多

正在热议

更多

# 写给毕业5年后的自己 #

4032次浏览 93人参与

# 好好告别我的学生时代 #

41544次浏览 810人参与

# 华泰证券Fintech星战营 #

168183次浏览 191人参与

# 职场捅娄子大赛 #

317964次浏览 3251人参与

# 海信求职进展汇总 #

64924次浏览 359人参与

# 华为求职进展汇总 #

4643543次浏览 28244人参与

# 晒一下我的毕业照 #

31541次浏览 342人参与

# 毕业季等于分手季吗 #

12990次浏览 141人参与

# 如何缓解求职过程中的焦虑？ #

7276次浏览 95人参与

# 机械制造岗投递时间线 #

22220次浏览 341人参与

# 如果今天是你的last day，你会怎么度过？ #

22635次浏览 197人参与

# 当下环境，你会继续卷互联网，还是看其他行业机会 #

108220次浏览 781人参与

# 晒晒我司的端午福利 #

14822次浏览 99人参与

# HR问：你期望的薪资是多少？如何回答 #

39974次浏览 524人参与

# 记录实习开销 #

25056次浏览 181人参与

# 我想象的实习vs现实的实习 #

280253次浏览 2214人参与

# 上班苦还是上学苦呢？ #

222753次浏览 1329人参与

# 工作两年想退休了 #

119868次浏览 1120人参与

# 视觉/交互/设计百问百答 #

43178次浏览 427人参与

# 如果中了500万，你会离职吗？ #

81967次浏览 649人参与

# 实习生如何通过转正 #

84930次浏览 1326人参与

牛客网
牛客企业服务