网站建设培训公司排名,黄梅戏网页制作素材,公司商标图案大全,广东建设网站目录 一.前缀和
1.前缀和介绍 2.编程中的前缀和
二.一维数组的动态和
1.题目描述
2.问题分析
3.代码实现
三.除自身以外数组的乘积
1.题目描述
2.问题分析
3.代码实现
四.和为 K 的子数组
1.题目描述
2.问题分析
3.代码实现
五.形成两个异或相等数组的三元组数目…目录 一.前缀和
1.前缀和介绍 2.编程中的前缀和
二.一维数组的动态和
1.题目描述
2.问题分析
3.代码实现
三.除自身以外数组的乘积
1.题目描述
2.问题分析
3.代码实现
四.和为 K 的子数组
1.题目描述
2.问题分析
3.代码实现
五.形成两个异或相等数组的三元组数目
1.题目描述
2.问题分析
3.代码实现 一.前缀和
1.前缀和介绍
前缀和,顾名思义,就是前n项相加之和,和我们高中时候学习的数列中的一个含义
例如一个等差数组n,那他的前n项和
也可知道- 2.编程中的前缀和
对于一个数组nums,也可以很容易求出它的前缀和数组 public int[] prefix(int[] nums) {int[] prefix new int[nums.length];prefix[0] nums[0];for (int i 1; i nums.length; i) {prefix[i] prefix[i - 1] nums[i];}return prefix;}
prefix数组的含义是: prefix[i]的值为nums数组从0到i的元素之和
其实我们这里的前缀和并不仅仅局限于前几项的和,之后我们还会涉及到乘法前缀和(后缀和),异或前缀和等等......并且还会存在后缀和的情况
二.一维数组的动态和
1.题目描述 给你一个数组 nums 。数组「动态和」的计算公式为runningSum[i] sum(nums[0]…nums[i]) 。 请返回 nums 的动态和。 力扣:力扣
2.问题分析
这道题就是一道典型的前缀和题目,没什么特别之处,数组的动态和计算公式就是前缀和的含义,可以直接写出代码求解
3.代码实现 public int[] runningSum(int[] nums) {int[] prefix new int[nums.length];prefix[0] nums[0];for (int i 1; i nums.length; i) {prefix[i] prefix[i - 1] nums[i];}return prefix;}
三.除自身以外数组的乘积
1.题目描述 给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除法且在 O(n) 时间复杂度内完成此题。 力扣:力扣
2.问题分析
这个问题说的很明白,不能用除法来进行,我们的第一想法是使用乘法前缀和来进行计算,但是考虑到不能使用除法和数组中可能存在0,所以这样是不能够满足题意和解答问题的.
因此我们不妨再来设置一个数组,这个数组用来存储乘法后缀和,我们计算res[i]的时候就可以它的前缀和乘以它的后缀和,这样它的结果就可以求出来了
设置前缀和数组left[i]含义为:从nums数组的第0到第i-1项的叠乘所获得的结果
设置后缀和数组right[i]含义为:从nums数组的第i1到最后一项项的叠乘所获得的结果
最后结果数组res[i]left[i]*right[i]
3.代码实现 public int[] productExceptSelf(int[] nums) {int[] left new int[nums.length];//left[i]:从0-i-1项相乘int[] right new int[nums.length];//right[i]:从i1到最后一项相乘left[0] 1;right[nums.length - 1] 1;for (int i 1; i nums.length; i) {left[i] left[i - 1] * nums[i - 1];}for (int j nums.length - 2; j 0; --j) {right[j] right[j 1] * nums[j 1];}int[] res new int[nums.length];for (int i 0; i nums.length; i) {res[i] left[i] * right[i];}return res;}
四.和为 K 的子数组
1.题目描述 给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的连续子数组的个数 。 力扣:力扣
2.问题分析
这一题我们不妨先暴力思考一下,暴力就是把它的所有子数组的和全部求出来,然后和k进行判断,最后统计出等于k的子数组的数量,至少也进行两层for循环,代码如下: public int subarraySum(int[] nums, int k) {int count 0;for (int end 0; end nums.length; end) {int sum 0;for (int start end; start 0; --start) {sum nums[start];if (sum k) {count;}}}return count; } 相当于外层循环确定end,内层循环确定开始的位置start的位置
其实我们可以用一个哈希表进行优化,因为它的前缀和每次都是叠加的,其实只要统计它的每个前缀和的次数,然后prefix-k就是它从0到start的前缀和,此时start1到end的位置就是和为k的子数组,同时map哈希表刚开始的时候还要添加key0,value1的键值对,因为当prefix刚好为k的时候,prefix-k0,表示从0到end的子数组符合条件
3.代码实现 public int subarraySum(int[] nums, int k) {HashMapInteger, Integer map new HashMap();map.put(0, 1);//此时是从0到i的前缀和int prefix 0, count 0;for (int end 0; end nums.length; end ) {prefix nums[end];if (map.containsKey(prefix - k)) {count map.get(prefix - k);}map.put(prefix, map.getOrDefault(prefix, 0) 1);}return count; }
五.形成两个异或相等数组的三元组数目
1.题目描述 给你一个整数数组 arr 。 现需要从数组中取三个下标 i、j 和 k 其中 (0 i j k arr.length) 。 a 和 b 定义如下 a arr[i] ^ arr[i 1] ^ ... ^ arr[j - 1]b arr[j] ^ arr[j 1] ^ ... ^ arr[k]注意^ 表示 按位异或 操作。 请返回能够令 a b 成立的三元组 (i, j , k) 的数目。 力扣:力扣
2.问题分析
首先我们想的就是需要暴力遍历i,j和k这三个值,这一题是异或前缀和,首先我们把它的异或前缀和数组求解出来,然后用异或前缀和来表达a和b,
前缀和数组prefixArr[i]的含义:nums从0到i-1的异或前缀 aprefixArr[j]^prefixArr[i] bprefixArr[k1]^prefixArr[j] ab 即 prefixArr[k1]prefixArr[i] 知道这个之后,我们就可以使用暴力的方法求解出满足条件的三元组的数量了
3.代码实现 public int countTriplets(int[] arr) {int[] prefixArr new int[arr.length 1];for (int i 1; i arr.length; i) {prefixArr[i] prefixArr[i - 1] ^ arr[i - 1];}System.out.println(Arrays.toString(prefixArr));int count 0;for (int i 0; i arr.length - 2; i) {for (int j i 1; j arr.length - 1; j) {for (int k j 1; k arr.length; k) {if (prefixArr[k 1] prefixArr[i])count;}}}return count;}
