美团笔试0909 异或和题思路分享

比较幸运今早思路很清晰,很顺地a出了最后这道题。
我的思路是用一个二维数组cnt[32][2]保存在当前位置之前,每个二进制位置上0和1的贡献,用一个数组dp[i]保存数组arr[0]到arr[i]中所有子数组的异或和。val[i]保存的是2的i次方。
每次遍历到一个数arr[i],根据之前各个位置上0和1的贡献,计算出dp[i]。dp[i]的计算主要分两部分,一部分是包括当前数字arr[i]的所有计算,公式为dp[i] += val[k] * cnt[k][!cur],k是当前数字二进制表示的第k位,cur是这个位置上的数(0或1),这个过程需要遍历数字arr[i]的每一个二进制位;另一部分是不包括当前数字arr[i]的计算,这部分直接dp[i] += dp[i-1]。计算完dp[i]后,需要更新一下cnt数组,当前数字二进制第k位上是0,那么cnt[k][0] += i + 1,如果是1同理,这个过程就是计算当前数字对后面计算的一个贡献。最后的结果就是求dp数组的和。我在整个过程中为了避免溢出使用的都是long long,还有注意求余。
手机码字,如有错误,欢迎提出
全部评论
不包括当前数字arr[i]的计算是啥意思呀,没太懂
点赞 回复 分享
发布于 2023-09-11 12:32 浙江
tql浙大✌🏻
点赞 回复 分享
发布于 2023-09-09 16:15 北京
最后那个cnt[k][0]+=i+1是什么意思呀
点赞 回复 分享
发布于 2023-09-09 13:31 湖南
佬啊!牛逼!
点赞 回复 分享
发布于 2023-09-09 13:21 湖南

相关推荐

01-17 18:15
已编辑
门头沟学院 前端工程师
从上午约我面试然后他迟到,然后中午发消息打电话给我说重约面试时间,我就该意识到。【管理不规范,只是这家公司最小的问题】他妈一个不是技术的人来给我技术面。。。连vvue什么?连react是什么?连普通的HTTP请求是什么?这些东西都不懂的人来给我做技术面,我真的。。。。他妈浪费我40分钟。。一天面了三场,这家公司属实牛逼。不停的问我说上班下班时间谁来派任务公司在哪个区发展怎么样,公司的管理模式什么样,培养机制怎么样带教负责什么。如果出bug了谁来负责。我真的求你了别闹了。我答了15分钟,我已经很不想回答了。然后他就问了我一些很招笑的面试问题。问我前端框架架构设计怎么设计,Websocket可以实现SSE吗??最后还要我硬说,为什么我们公司没转正?为什么?为什么?我说我怎么知道。。这是领导决定,又不是我决定,他说让我分析一下。。。我真的草了,这个人是来搞我的吗?我最后问我说这个没有技术面,他说他就是技术面虽然我今天面的另外两家也很逆天。一个人不停的吹牛,自己100人的公司是全国前几,吹牛了一个小时。我中途几次想跑,真的是底下玩手机在听他那吹牛。。然后最后来了句说,我承诺的东西要实现哦,不然的话,公司会追责的,我我请问我承诺了什么?从头到尾也没有说让我承诺什么。而且我只是作为一个小小的前端卡拉咪,应届生。我要承担什么??好崩溃。。好崩溃的,一天面了三场。两家1000-9999的公司。面试官问的都很傻逼,甚至有些东西我问他估计都答不出来。。 我这是在干嘛呀?浪费我一天的时间,我的奶奶。。我本来是抱着说我很菜,我要面试中发现自己的问题,现在来看他妈的这三场面试,面试本身就是问题。。
点赞 评论 收藏
分享
评论
8
11
分享

创作者周榜

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