位或例题Java 暴力法和前缀异或法
2021/8/31 22:36:19
本文主要是介绍位或例题Java 暴力法和前缀异或法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
我写的垃圾暴力法:
public static int[] xorQueries(int[] arr, int[][] queries) { int i = queries.length; int []querr= new int[i]; int idx = 0; int num; for (int [] s : queries) { num = 0; for (int d= s[0];d<=s[1];d++){ num = arr[d]^num; } querr[idx] = num; idx++; } return querr; }
人家写的前缀异或法
public int[] xorQueries(int[] arr, int[][] queries) { int n = arr.length; int[] xors = new int[n + 1]; for (int i = 0; i < n; i++) { xors[i + 1] = xors[i] ^ arr[i]; } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; i++) { ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1]; } return ans; }
它的原理是创建一个长度为arr.length+1的数组,每个元素n存放的是arr[0]连续位或到arr[n-1],第一个元素定为0方便位或别的元素,0位或任何数=任何数,第2个元素存放的是arr[0]^arr[2-1],这样以此存放。
首先为什么长度是arr.length+1呢,因为第一个元素必须是0,所以多了一位,其次为什么第一个必须是0呢,因为0位或任何数是等于任何数本身,目的就是当二维数组是{0,3}这样的值时,我们应该在arr数组数0-3也就是4个连续位或过去,而这个4个位或刚好存放在我们的数组第四个元素上,因为第一个元素是0,所以我们让第一个元素位或第4个元素就返回了正确的值,也就是这个部分
xors[queries[i][0]] ^ xors[queries[i][1] + 1]; 此时queries[i][0]是二维数组的0 queries[i][1]是二维数组的3,所以要+1,时间复杂度对比显而易见。
这篇关于位或例题Java 暴力法和前缀异或法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求