商会信息平台网站建设方案,智能网站开发工具,网站建设的流程和内容,零基础学wordpress教学PPT前缀和概念 假设有数组 A[1,2,3,4,5,6,7] 为原数组#xff0c;有数组 B作为A的前缀和数组#xff0c;那么B[1,3,6,10,15,21,28]#xff1b;可以发现B[i] A[0]....A[i]#xff0c;即B[i]是数组A的前面i个数的总和。可以前缀和表示如下公式#xff1a; B[i]∑j0iA[j]B[i]\s…前缀和概念 假设有数组 A[1,2,3,4,5,6,7] 为原数组有数组 B作为A的前缀和数组那么B[1,3,6,10,15,21,28]可以发现B[i] A[0]....A[i]即B[i]是数组A的前面i个数的总和。可以前缀和表示如下公式 B[i]∑j0iA[j]B[i]\sum_{j0}^{i}{A[j]} B[i]j0∑iA[j] 因此有了前缀和数组可以简化我们算法就子区间和假设没有前缀和要求数组A区间[2,4]的总和我们需要从 i2 遍历 到 i4 时间复杂度为O(n)通过前缀和只需要计算 B[4]-B[1]即可因此可以将子区间和表示如下公式B[i,j]B[j]-B[i-1],ji 。但是上述子区间表示法在实际应用中会有问题即当求区间B[0,j]的时候会出现下标等于-1的情况因此一般在程序中写成如下 B[i,j]B[j]−B[i]A[i]B[i,j]B[j]-B[i]A[i] B[i,j]B[j]−B[i]A[i]
递推构造前缀和 可以使用递推式构造前缀和递推公式如下 B[i]B[i−1]A[i],B[0]A[0]B[i]B[i-1]A[i],B[0]A[0] B[i]B[i−1]A[i],B[0]A[0]
不仅仅是这些
这些直接求前缀数字和的题目是前缀和最简单的题型变换题型一般是记录前i个字符或者数组的状态当遍历后续的ik时求得前ik的状态然后比较两者之间的变化推出中间长度k子串的状态看看是否满足题目要求。这才是前缀和的灵魂前缀和一般和数组、子串、连续等关键字有关尤其是数组和字符串的问题求最长子串求数组满足条件的连续的最长长度通过题目练习总结尤其是最后两题
LeetCode 560. 和为 K 的子数组 public int subarraySum(int[] nums, int k) {int[] B new int[nums.length];B[0] nums[0];int count 0;for (int i 1; i nums.length; i) {B[i] B[i-1]nums[i];}for (int i 0; i nums.length; i) {for (int j i; j nums.length; j) {// 求i到j的前缀和包括i和jint sum B[j]-B[i]nums[i];if(sumk){count;}}}return count;}525. 连续数组 一般而言只用前缀和判断区间的复杂度为O(n2)因为遍历区间复杂度就是O(n2)因此往往使用哈希表来优化问题。前缀和哈希表 如下直接使用前缀和会导致超时这道题需要把0变成-1如果前i个数的和为-2前i7的和也是-2那么巧了那就意味着从i1到i7的和为0即1和-1的数量一样多。这就是前缀的灵魂。 public int findMaxLength(int[] nums) {int[] B new int[nums.length];B[0] nums[0];for (int i 1; i nums.length; i) {B[i] B[i-1]nums[i];}int res 0;for (int i 0; i nums.length; i) {for (int j i; j nums.length; j) {int sum B[j]-B[i]nums[i];if((j-i1)sum*2 sumres){res sum;}}}return res;}public int findMaxLength(int[] nums) {HashMapInteger, Integer map new HashMap();for (int i 0; i nums.length; i) {if(nums[i]0){nums[i] -1;}}int[] B new int[nums.length];B[0] nums[0];map.put(B[0],0);int maxx 0;for (int i 1; i nums.length; i) {B[i] B[i - 1] nums[i];if(!map.containsKey(B[i])){//只需要存第一个出现的值即可因为求最长的所以一定是第一个map.put(B[i],i);}else {//如果前面出现过int value (i-map.get(B[i]));maxx Math.max(value,maxx);}if(B[i]0){maxx Math.max(i1,maxx);}}return maxx;}1685. 有序数组中差绝对值之和 public int[] getSumAbsoluteDifferences(int[] nums) {//使用一个规律即数组是递增的即后一个数的和与前一个数的和之间的关系//关系是假设第i1个数比第i个数大k则i1之后的数会在sum(i)的基础上少// (n-i1)*k , 而i之前的数会在sum(i)的基础上多 (i-1)*kint n nums.length;int[] res new int[n];int sum 0;for (int i 0; i n; i) {sum(Math.abs(nums[i]-nums[0]))}res[0] sum;for (int i 1; i n; i) {int k nums[i]-nums[i-1];int a (i-1)*k;int b (n-i-1)*k;res[i] res[i-1]a-b;}return res;}1423. 可获得的最大点数
一开始秒想到动态规划但是超时正确思路是反过来找最小的剩下的连续序列。使用滑动窗口
public int maxscore(int[] cardPoints,int left,int right,int k){if(k1 leftright){int value Math.max(cardPoints[right],cardPoints[left]);map.put(leftrightk,value);return value;}int a 0;int b 0;if(map.containsKey((left1)right(k-1))){a map.get((left1)right(k-1))cardPoints[left];}else {a maxscore(cardPoints,left1,right,k-1)cardPoints[left];}if(map.containsKey(left(right-1)(k-1))){b map.get((left)(right-1)(k-1))cardPoints[right];}else {b maxscore(cardPoints,left,(right-1),k-1)cardPoints[right];}return Math.max(a,b);}public int maxScore(int[] cardPoints, int k) {//动态规划map new HashMap();return maxscore(cardPoints,0,cardPoints.length-1,k);}正确解法
public int maxScore(int[] cardPoints, int k) {int n cardPoints.length-k;int[] B new int[cardPoints.length];B[0] cardPoints[0];for (int i 1; i cardPoints.length; i) {B[i] B[i-1]cardPoints[i];}if(cardPoints.lengthk){return B[cardPoints.length-1];}int minn Integer.MAX_VALUE;for (int i 0; i k; i) {int sum B[in-1]-B[i]cardPoints[i];if(summinn){minn sum;}}return B[cardPoints.length-1]-minn;}1371. 每个元音包含偶数次的最长子字符串
525. 连续数组 为什么挂这两道题因为如果想到了这两道题的前缀和才是真的入门了首先说525题。这道题前面已经提过这道题需要把0变成-1如果前i个数的和为-2前i7的和也是-2那么巧了那就意味着从i1到i7的和为0即1和-1的数量一样多。这就是前缀的灵魂。那么换成1371要求五个字母出现都是偶数的最长子字符串的长度那么5个字符的奇偶状态就有32种因此同理在前i个字符如果是 ‘a’‘e’‘i’ ‘o’都是偶数u’是奇数而前i9个字符前三个是偶数后两个是奇数那么意味着什么意味着从i1到i9的子串中有奇数个 ‘o’ 。这只是一个例子所以需要使用前ik的状态与前i的状态对比才知道中间这k个字符是什么状态。因此前缀和并一定是前面数字之和也可以是状态的变化。通过后面ik的状态与i的状态推出中间的状态。这就是前缀和的灵魂。 class Solution {public int findTheLongestSubstring(String s) {int n s.length();int[] pos new int[1 5];Arrays.fill(pos, -1);int ans 0, status 0;pos[0] 0;for (int i 0; i n; i) {char ch s.charAt(i);if (ch a) {status ^ (1 0);} else if (ch e) {status ^ (1 1);} else if (ch i) {status ^ (1 2);} else if (ch o) {status ^ (1 3);} else if (ch u) {status ^ (1 4);}if (pos[status] 0) {ans Math.max(ans, i 1 - pos[status]);} else {pos[status] i 1;}}return ans;}
}
