3.31 腾讯笔试 第四题

求大佬们讲一下第四题,分段异或和的那一道
全部评论
用异或交换律的性质,x^y = z 等价于 x^z = y,然后类似前缀和维护一个从前往后异或的数组,然后用交换律的性质可以在O(1)时间里很快的找到某个区间所有元素的异或和,然后就记忆化搜索
1 回复 分享
发布于 2024-03-31 22:44 广东
动态规划,dp[i][j]表示前i个数分j段的最大异或和
1 回复 分享
发布于 2024-03-31 22:26 江苏
public static void getMax(int[] nums,int k){ int len=nums.length; long[] preXor=new long[len]; preXor[0]=nums[0]; for (int i = 1; i < len; i++) { preXor[i]^=nums[i]; } //dp[i][j] 表示 分为 i 段 时 以 j为结尾的 最大异或和 long[][] dp = new long[k + 1][len]; dp[1]=preXor; for (int i = 2; i <=k ; i++) { for (int j = i-1; j < len; j++) { long val=0; for (int l = j-1; l >=0 ; l--) { /* 多了一个数字 j , 这个数字必然在 分段的最后一段中 ,最后一段分多长呢? 只能遍历 preXor[j]^preXor[l] 再 加 前面的数字 分为 i-1段 时的最大值 */ val=Math.max(val,dp[i-1][l]+(preXor[j]^preXor[l])); } dp[i][j]=val; } } System.out.println(dp[k][len-1]); }
点赞 回复 分享
发布于 2024-04-03 15:50 湖北

相关推荐

找到实习了&nbsp;给了150一天&nbsp;但是说是低代码&nbsp;值得去吗
码农索隆:是在没实习,可去,待个一两周,不行就润呗
点赞 评论 收藏
分享
05-25 10:45
门头沟学院 Java
Frank_zhan...:没实习一个项目肯定不够,可以再做一个轮子,技术栈再补一个mq,微服务,整体再换个简历模板,暑期尽量再找一个日常实习
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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