Java之前缀和算法

今天药忘吃喽~ 2024-03-26 12:20 50阅读 0赞

**目录**

一.前缀和

1.前缀和介绍

2.编程中的前缀和

二.一维数组的动态和

1.题目描述

2.问题分析

3.代码实现

三.除自身以外数组的乘积

1.题目描述

2.问题分析

3.代码实现

四.和为 K 的子数组

1.题目描述

2.问题分析

3.代码实现

五.形成两个异或相等数组的三元组数目

1.题目描述

2.问题分析

3.代码实现

六.统计共同度过的日子数

1.题目描述

2.问题分析

3.代码实现

--------------------

## 一.前缀和 ##

### 1.前缀和介绍 ###

前缀和,顾名思义,就是前n项相加之和,和我们高中时候学习的数列中的![S\_\{n\}][S_n]一个含义

例如一个等差数组![a\_\{n\}][a_n]=n,那他的前n项和![S\_\{n\}][S_n]=![\\frac\{n\*(n+1)\}\{2\}][frac_n_n_1_2]

也可知道![S\_\{n\}][S_n]\-![S\_\{n-1\}][S_n-1]=![a\_\{n\}][a_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` 的动态和。

力扣:[力扣][Link 1]

### 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)` 时间复杂度内完成此题。

力扣:[力扣][Link 2]

### 2.问题分析 ###

这个问题说的很明白,不能用除法来进行,我们的第一想法是使用**乘法前缀和**来进行计算,但是考虑到不能使用除法和数组中可能存在0,所以这样是不能够满足题意和解答问题的.

因此我们不妨再来设置一个数组,这个数组用来存储**乘法后缀和**,我们计算res\[i\]的时候就可以它的前缀和乘以它的后缀和,这样它的结果就可以求出来了

设置**前缀和数组left\[i\]**含义为:从nums数组的第0到第i-1项的叠乘所获得的结果

设置**后缀和数组right\[i\]**含义为:从nums数组的第i+1到最后一项项的叠乘所获得的结果

最后结果数组**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]:从i+1到最后一项相乘
            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`的连续子数组的个数* 。

力扣:[力扣][Link 3]

### 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;  
    
        }

![e363108ef9e048f29b38f0fb48800f56.png][]

相当于外层循环确定end,内层循环确定开始的位置start的位置

其实我们可以用一个哈希表进行优化,因为它的前缀和每次都是叠加的,其实只要统计它的每个前缀和的次数,然后prefix-k就是它从0到start的前缀和,此时start+1到end的位置就是和为k的子数组,同时map哈希表刚开始的时候还要添加key=0,value=1的键值对,因为当prefix刚好为k的时候,prefix-k=0,表示从0到end的子数组符合条件

### 3.代码实现 ###

public int subarraySum(int[] nums, int k) {
            HashMap<Integer, 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`) 的数目。

力扣:[力扣][Link 4]

### 2.问题分析 ###

首先我们想的就是需要暴力遍历i,j和k这三个值,这一题是**异或前缀和,**首先我们把它的异或前缀和数组求解出来,然后用异或前缀和来表达a和b,

前缀和数组prefixArr\[i\]的含义:nums从0到i-1的异或前缀

> a=prefixArr\[j\]^prefixArr\[i\]
> 
> b=prefixArr\[k+1\]^prefixArr\[j\]
> 
> a==b 即 prefixArr\[k+1\]==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;
    
           
    
        }

## 六.统计共同度过的日子数 ##

### 1.题目描述 ###

> Alice 和 Bob 计划分别去罗马开会。
> 
> 给你四个字符串 `arriveAlice` ，`leaveAlice` ，`arriveBob` 和 `leaveBob` 。Alice 会在日期 `arriveAlice` 到 `leaveAlice` 之间在城市里（**日期为闭区间**），而 Bob 在日期 `arriveBob` 到 `leaveBob` 之间在城市里（**日期为闭区间**）。每个字符串都包含 5 个字符，格式为 `"MM-DD"` ，对应着一个日期的月和日。
> 
> 请你返回 Alice和 Bob 同时在罗马的天数。
> 
> 你可以假设所有日期都在 **同一个** 自然年，而且 **不是** 闰年。每个月份的天数分别为：`[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]` 。

力扣:[力扣][Link 5]

### 2.问题分析 ###

这题的可以转换为到达和离开在一年中多少天的问题,然后我们可以根据第i月前一共有多少前构建前缀和数组来对这个问题进行求解.

### 3.代码实现 ###

public int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {
            int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
            int[] prefixSum = new int[13];//prefixSum[i]表示i月份及之前一共多少天
            for (int i = 0; i < prefixSum.length-1; ++i) {
                prefixSum[i + 1] = prefixSum[i] + days[i];
            }
            int alice1 = calculateDayOfYear(arriveAlice, prefixSum);
            int alice2 = calculateDayOfYear(leaveAlice, prefixSum);
            int bob1 = calculateDayOfYear(arriveBob, prefixSum);
            int bob2 = calculateDayOfYear(leaveBob, prefixSum);
    
            return Math.max(0, Math.min(bob2, alice2) - Math.max(alice1, bob1)+1);
    
        }
    
        public int calculateDayOfYear(String day, int[] prefixSum) {
            int month = Integer.parseInt(day.substring(0, 2));
            int date = Integer.parseInt(day.substring(3));
            return prefixSum[month - 1] + date;
        }

## 七.比较字符串最小字母出现频次 ##

### 1.题目描述 ###

> 定义一个函数 `f(s)`，统计 `s` 中**（按字典序比较）最小字母的出现频次** ，其中 `s` 是一个非空字符串。
> 
> 例如，若 `s = "dcce"`，那么 `f(s) = 2`，因为字典序最小字母是 `"c"`，它出现了 2 次。
> 
> 现在，给你两个字符串数组待查表 `queries` 和词汇表 `words` 。对于每次查询 `queries[i]` ，需统计 `words` 中满足 `f(queries[i])` < `f(W)` 的 **词的数目** ，`W` 表示词汇表 `words` 中的每个词。
> 
> 请你返回一个整数数组 `answer` 作为答案，其中每个 `answer[i]` 是第 `i` 次查询的结果。
> 
> **提示：**
> 
>  *  `1 <= queries.length <= 2000`
>  *  `1 <= words.length <= 2000`
>  *  `1 <= queries[i].length, words[i].length <= 10`
>  *  `queries[i][j]`、`words[i][j]` 都由小写英文字母组成

力扣: [力扣][Link 6]

### 2.问题分析 ###

后缀和,首先我们先写出一个方法用来计算出一个单词的最小字母出现的频次(这个方法很简单,可以自行实现,也可以直接看我的代码实现).然后因为数据范围我知道每个单词的长度不超过10,因此最小单词出现的频次最大为10.因此我们可以设置一个count数组(长度先设置为11,也就是说最大下标为10)用来记录words的最小字母出现频次的次数**.count\[i\]的含义是:words字符串数组中最小字母频次为i出现的频次为count\[i\]**,然后根据题目意思,我们需要找的是 `f(queries[i])` < `f(W)` 的 **词的数目,**因此如果使用暴力就是每次遍历到(i为count数组的下标)f(i)>f(queries\[i\])的下标,然后将此包括之后的count数组的值相加起来,这样有点麻烦,因此我们可以设置一个后缀和数组,我们只需要计算出f(queries\[i\]),然后count\[f(queries\[i\])+1\]就是我们最终答案了**.count\[i\]后缀和数组的含义:表示最小字母频次大于等于i的次数之和为count\[i\]**;但是这个时候还会出现一个问题,当f(queries\[i\])为10的时候,这个时候是count\[f(queries\[i\])+1\],这个时候一定不会有满足条件的值,结果恒为0.但是我们设置的count数组的长度为11,最大下标为10.会出现索引越界的情况,因此我们不妨将数组长度设置为12.这样可以满足题意,也可以很好的解决这个错误.

拓展,如果题目修改一下,需要求的是`f(queries[i])` > `f(W)` ,这个时候可以前缀和数组来解决,也不会出现我们最后说的问题了.

### 3.代码实现 ###

public int[] numSmallerByFrequency(String[] queries, String[] words) {
            int[] count = new int[12];
            for (String s : words) {
                count[havaCount(s)]++;
            }
            for (int i = 9; i >= 1; i--) {
                count[i] += count[i + 1];
            }
            int[] res = new int[queries.length];
            for (int i = 0; i < queries.length; i++) {
                String s = queries[i];
                res[i] = count[havaCount(s) + 1];
            }
            return res;
    
    
        }
    
        public int havaCount(String s) {
            char c = 'z';
            int cnt = 0;
            for (int i = 0; i < s.length(); ++i) {
                if (s.charAt(i) < c) {
                    c = s.charAt(i);
                    cnt=1;
                }else if(c==s.charAt(i)){
                    cnt++;
                }
            }
    
            return cnt;
    
    
        }

## 八.最大或值 ##

### 1.题目描述 ###

> 给你一个下标从 **0** 开始长度为 `n` 的整数数组 `nums` 和一个整数 `k` 。每一次操作中，你可以选择一个数并将它乘 `2` 。
> 
> 你最多可以进行 `k` 次操作，请你返回`nums[0] | nums[1] | ... | nums[n - 1]` 的最大值。
> 
> `a | b` 表示两个整数 `a` 和 `b` 的 **按位或** 运算。

力扣:[力扣][Link 7]

### 2.问题分析 ###

前后缀分解(前缀和+后缀和)

我们先来思考这样一个问题:怎么样使用k次乘2的条件才可能让最后的结果最大,我们是把这个条件分散给多个值操作,还是给一个值进行操作,当然是个一个值进行操作,(二进制操作)这样乘2才可以使最高位的1尽可能的接近高位,但是具体给哪一个值所有的乘k操作我们是不确定的,因此我们需要进行暴力枚举,每次给nums\[i\]进行k次乘2操作,再进行nums\[i\]前面的值和后面值的或操作,然后记录最大值即可,但是每次nums\[i\]前和后面值的操作是繁琐的,因此我们可以使用前置或和后缀或数组,我们这样设置两个数组,前置或数组prefix\[i\]含义:nums数组中索引为0到i-1进行或操作的值,postfix\[i\]的含义:nums数组中索引为i+1到nums.length-1进行或操作的值,max = Math.max(max, prefix\[i\] | postfix\[i\] | (long)nums\[i\] << k);就可以找到最终的结果了

### 3.代码实现 ###

public long maximumOr(int[] nums, int k) {
            int n = nums.length;
            int[] prefix = new int[n];
            int[] postfix = new int[n];
            prefix[0] = 0;
            postfix[n - 1] = 0;
            for (int i = 1; i < n; ++i) {
                prefix[i] = nums[i - 1] | prefix[i - 1];
            }
            for (int i = n - 2; i >= 0; --i) {
                postfix[i] = nums[i + 1] | postfix[i + 1];
            }
            long max = 0;
    
            for (int i = 0; i < n; ++i) {
                max = Math.max(max, prefix[i] | postfix[i] | (long)nums[i] << k);
            }
    
            return max;
        }

[S_n]: https://latex.csdn.net/eq?S_%7Bn%7D
[a_n]: https://latex.csdn.net/eq?a_%7Bn%7D
[frac_n_n_1_2]: https://latex.csdn.net/eq?%5Cfrac%7Bn*%28n&plus;1%29%7D%7B2%7D
[S_n-1]: https://latex.csdn.net/eq?S_%7Bn-1%7D
[Link 1]: https://leetcode.cn/problems/running-sum-of-1d-array/description/
[Link 2]: https://leetcode.cn/problems/product-of-array-except-self/description/
[Link 3]: https://leetcode.cn/problems/subarray-sum-equals-k/
[e363108ef9e048f29b38f0fb48800f56.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/079c034dfe6e4beea83d210ae6a5eefc.png
[Link 4]: https://leetcode.cn/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/description/
[Link 5]: https://leetcode.cn/problems/count-days-spent-together/description/
[Link 6]: https://leetcode.cn/problems/compare-strings-by-frequency-of-the-smallest-character/description/
[Link 7]: https://leetcode.cn/problems/maximum-or/