昆明快速做網(wǎng)站海南網(wǎng)站制作
前綴和是什么:
前綴和指一個(gè)數(shù)組的某下標(biāo)之前的所有數(shù)組元素的和(包含其自身)。前綴和分為一維前綴和,以及二維前綴和。前綴和是一種重要的預(yù)處理,能夠降低算法的時(shí)間復(fù)雜度
說個(gè)人話就是比如有一個(gè)數(shù)組:
[1,2,3,4],然后我求得sum數(shù)組[1,3,6,10];
那我只要有了這個(gè)sum數(shù)組,我就可以在O(1)得時(shí)間內(nèi)求出區(qū)間和,
比如我想求interval[i,j]內(nèi)得區(qū)間和,我怎么辦,我直接那sum[j]-sum[i]就可以了。
ok了解了這個(gè)思想,我們也很容易想到:前綴和得作用或者說前綴和適合解決什么樣的題目呢:就是子數(shù)組,或者字字符串類似的題目:
下面上例題:先從簡(jiǎn)單的開始:
leetcode1732:找到最高海拔:
有一個(gè)自行車手打算進(jìn)行一場(chǎng)公路騎行,這條路線總共由?n + 1
?個(gè)不同海拔的點(diǎn)組成。自行車手從海拔為?0
?的點(diǎn)?0
?開始騎行。
給你一個(gè)長(zhǎng)度為?n
?的整數(shù)數(shù)組?gain
?,其中?gain[i]
?是點(diǎn)?i
?和點(diǎn)?i + 1
?的?凈海拔高度差(0 <= i < n
)。請(qǐng)你返回?最高點(diǎn)的海拔?。
有一個(gè)自行車手打算進(jìn)行一場(chǎng)公路騎行,這條路線總共由?n + 1
?個(gè)不同海拔的點(diǎn)組成。自行車手從海拔為?0
?的點(diǎn)?0
?開始騎行。
給你一個(gè)長(zhǎng)度為?n
?的整數(shù)數(shù)組?gain
?,其中?gain[i]
?是點(diǎn)?i
?和點(diǎn)?i + 1
?的?凈海拔高度差(0 <= i < n
)。請(qǐng)你返回?最高點(diǎn)的海拔?。
class Solution {public int largestAltitude(int[] gain) {int len = gain.length;int[] sum = new int[len+1];for(int i=1;i<=len;++i){sum[i] = gain[i-1]+sum[i-1];}int flag = Integer.MIN_VALUE;for(int i=0;i<=len;++i){if(sum[i]>flag){flag = sum[i];}}return flag;}
}
這道題也算是前綴和的一個(gè)入門,我們求出前綴和數(shù)組sum之后,遍歷sum找到最大值即可。
leetcode 1413 逐步求和得到正數(shù)的最小值:
給你一個(gè)整數(shù)數(shù)組?nums
?。你可以選定任意的?正數(shù)?startValue 作為初始值。
你需要從左到右遍歷?nums
?數(shù)組,并將 startValue 依次累加上?nums
?數(shù)組中的值。
請(qǐng)你在確保累加和始終大于等于 1 的前提下,選出一個(gè)最小的?正數(shù)?作為 startValue 。
輸入:nums = [-3,2,-3,4,2] 輸出:5 解釋:如果你選擇 startValue = 4,在第三次累加時(shí),和小于 1 。 累加求和startValue = 4 | startValue = 5 | nums ? (4 -3 ) = 1 | (5 -3 ) = 2 | -3(1 +2 ) = 3 | (2 +2 ) = 4 | 2(3 -3 ) = 0 | (4 -3 ) = 1 | -3(0 +4 ) = 4 | (1 +4 ) = 5 | 4(4 +2 ) = 6 | (5 +2 ) = 7 | 2
class Solution {public int minStartValue(int[] nums) {int len = nums.length;int[] sum = new int[len+1];for (int i = 1; i <=len; i++) {sum[i] = sum[i-1]+nums[i-1];}int flag = Integer.MAX_VALUE;for (int i = 1; i <=len ; i++) {if(sum[i]<flag){flag = sum[i];}}return flag<0?(flag*-1)+1:1;}
}
這道題就比上一道需要多分析一些東西,
首先題目要求一個(gè)最小的正整數(shù),所以我們肯定要根據(jù)這個(gè)數(shù)組的和來求。
leetcode 724:找數(shù)組的中心下標(biāo)
給你一個(gè)整數(shù)數(shù)組 nums ,請(qǐng)計(jì)算數(shù)組的 中心下標(biāo) 。
數(shù)組 中心下標(biāo) 是數(shù)組的一個(gè)下標(biāo),其左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。
如果中心下標(biāo)位于數(shù)組最左端,那么左側(cè)數(shù)之和視為 0 ,因?yàn)樵谙聵?biāo)的左側(cè)不存在元素。這一點(diǎn)對(duì)于中心下標(biāo)位于數(shù)組最右端同樣適用。
如果數(shù)組有多個(gè)中心下標(biāo),應(yīng)該返回 最靠近左邊 的那一個(gè)。如果數(shù)組不存在中心下標(biāo),返回 -1 。
那這道題目不是典型的前綴和嘛,我們要求這個(gè)所謂的中心下標(biāo),我們不就是這個(gè)中心下標(biāo)的左邊的區(qū)間和==右邊的區(qū)間和嘛
public int pivotIndex(int[] nums) {int len = nums.length;int i;int[] sum = new int[len + 1];sum[0] = 0;for (i = 0; i < len; ++i) {sum[i + 1] = sum[i] + nums[i];}for (i = 1; i < len+1; ++i) {if (sum[len] == (2 * sum[i - 1]) + nums[i-1]) {return i-1;}}return -1;}
當(dāng)我們算出來這個(gè)sum數(shù)組之后,我們只需要從左往右遍歷一下,然后根據(jù)數(shù)學(xué)公式就可以得出下標(biāo)的結(jié)果,
這里有一個(gè)注意點(diǎn):
就是你求sum數(shù)組的時(shí)候,你需要在sum[0]的位置墊一個(gè)0(這也是前綴和的固定套路),怎么理解呢
比如有一個(gè)數(shù)組:[1,0,0,0],那這個(gè)時(shí)候,1這個(gè)位置很明顯是中心坐標(biāo),如果你不墊個(gè)0在前面的話,公式就不成立
其實(shí)這種情況也可以作為一個(gè)特判(我認(rèn)為),也可以理解為一個(gè)前綴和的固定套路。
線性前綴和變形:
leetcode 238 除自身以外數(shù)組的乘積:
給你一個(gè)整數(shù)數(shù)組?nums
,返回?數(shù)組?answer
?,其中?answer[i]
?等于?nums
?中除?nums[i]
?之外其余各元素的乘積?。
題目數(shù)據(jù)?保證?數(shù)組?nums
之中任意元素的全部前綴元素和后綴的乘積都在??32 位?整數(shù)范圍內(nèi)。
請(qǐng)?不要使用除法,且在?O(n)
?時(shí)間復(fù)雜度內(nèi)完成此題。
輸入: nums =[1,2,3,4]
輸出:[24,12,8,6]
先寫一種比較容易想到的方法:
利用對(duì)應(yīng)索引的左側(cè)和右側(cè)(也可以叫前綴和后綴)的乘積來得出答案
舉個(gè)例子:[1,2,3,4]
我們先算出這個(gè)數(shù)組的前綴和數(shù)組和后綴和數(shù)組:
[1,2,6,24]? ?[24,24,12,4]
比如我們要求2這個(gè)下標(biāo)的除自身以外數(shù)組的乘積
我們就可以用前綴和數(shù)組的第一個(gè)元素1,和后綴和數(shù)組的倒二個(gè)元素12相乘,得出12。
class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;int[] left = new int[len];left[0] = nums[0];int[] right = new int[len];right[len-1] = nums[len-1];for(int i=1;i<len;++i){left[i] = nums[i]*left[i-1];}for(int i=len-2;i>=0;i--){right[i] = nums[i]*right[i+1];}int[] ans = new int[len];ans[0] = right[1];ans[len-1] = left[len-2];for(int i=1;i<len-1;++i){ans[i] = left[i-1]*right[i+1];}return ans;}
}
?再來一種難一點(diǎn)的方法:
思路就是:
先從上往下算對(duì)應(yīng)索引的左變得乘積,然后再倒上去算對(duì)應(yīng)所以右邊得乘積。
類似有點(diǎn)像上三角和下三角得感覺。
//假如nums為[1,2,3,4],那么answer的值分別為[(2,3,4),(1,3,4),(1,2,4),(1,2,3)]//如果吧i當(dāng)前值相乘的時(shí)候看做是1那么就有如下樣式// 1, 2, 3, 4 // 1, 1, 3, 4// 1, 2, 1, 4// 1, 2, 3, 1// 他的對(duì)角線1將他們分割成了兩個(gè)三角形,對(duì)于answer的元素,//我們可以先計(jì)算一個(gè)三角形每行的乘積,然后再去計(jì)算另外一個(gè)三角形每行的乘積,//然后各行相乘,就是answer每個(gè)對(duì)應(yīng)的元素
class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;int[] left = new int[len];left[0] = 1;for(int i=1;i<len;++i){left[i] = nums[i-1]*left[i-1];}int temp = 1;for(int i=len-1;i>=0;i--){left[i] = left[i]*temp;temp *= nums[i];}return left;}
}
?leetcode 1310:子數(shù)組異或查詢:
有一個(gè)正整數(shù)數(shù)組?arr
,現(xiàn)給你一個(gè)對(duì)應(yīng)的查詢數(shù)組?queries
,其中?queries[i] = [Li,?Ri]
。
對(duì)于每個(gè)查詢?i
,請(qǐng)你計(jì)算從?Li
?到?Ri
?的?XOR?值(即?arr[Li] xor arr[Li+1] xor ... xor arr[Ri]
)作為本次查詢的結(jié)果。
并返回一個(gè)包含給定查詢?queries
?所有結(jié)果的數(shù)組。
輸入:arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]] 輸出:[2,7,14,8] 解釋: 數(shù)組中元素的二進(jìn)制表示形式是: 1 = 0001 3 = 0011 4 = 0100 8 = 1000 查詢的 XOR 值為: [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8
這道題其實(shí)蠻簡(jiǎn)單,不知道為什么力扣設(shè)置成中等題
這道題有一個(gè)小的注意點(diǎn),這道題的前綴和數(shù)組的第一個(gè)元素應(yīng)該是多少?
這就要去考慮異或的性質(zhì)了。
- 兩個(gè)數(shù)異或,相同的位數(shù)等于0 ;0110 ^ 1100 = 1010
- 一個(gè)數(shù)與0異或,結(jié)果等于本身;
- 一個(gè)數(shù)異或本身,結(jié)果為0;
- 綜上,可得第四條性質(zhì): a ^ b ^ b = a;
所以由異或性質(zhì)得出,前綴和數(shù)組的第一個(gè)數(shù)應(yīng)該是0。
class Solution {public int[] xorQueries(int[] arr, int[][] queries) {int[] xor = new int[arr.length+1];for (int i = 1; i <= arr.length; i++) {xor[i] = xor[i-1] ^ arr[i-1];}int[] ans = new int[queries.length];for (int i = 0; i < queries.length; i++) {ans[i] = xor[queries[i][1]+1] ^ xor[queries[i][0]];}return ans;}
}
leetcode 1829:每個(gè)查詢的最大異或值:
給你一個(gè)?有序?數(shù)組?nums
?,它由?n
?個(gè)非負(fù)整數(shù)組成,同時(shí)給你一個(gè)整數(shù)?maximumBit
?。你需要執(zhí)行以下查詢?n
?次:
- 找到一個(gè)非負(fù)整數(shù)?
k <
2的maximumBit次方?,使得?nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k
?的結(jié)果?最大化?。k
?是第?i
?個(gè)查詢的答案。 - 從當(dāng)前數(shù)組?
nums
?刪除?最后?一個(gè)元素。
請(qǐng)你返回一個(gè)數(shù)組?answer
?,其中?answer[i]
是第?i
?個(gè)查詢的結(jié)果。
輸入:nums = [0,1,1,3], maximumBit = 2 輸出:[0,3,2,3] 解釋:查詢的答案如下: 第一個(gè)查詢:nums = [0,1,1,3],k = 0,因?yàn)?0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。 第二個(gè)查詢:nums = [0,1,1],k = 3,因?yàn)?0 XOR 1 XOR 1 XOR 3 = 3 。 第三個(gè)查詢:nums = [0,1],k = 2,因?yàn)?0 XOR 1 XOR 2 = 3 。 第四個(gè)查詢:nums = [0],k = 3,因?yàn)?0 XOR 3 = 3 。
這道題和上一道題差不多,都是異或類型的前綴和,
這一題需要多考慮的一個(gè)條件就是這個(gè)k的大小,題目說k小于2的maximumBit次方,我們由異或的性質(zhì)可以知道,我們要想最后的結(jié)果盡可能大,我們希望我們異或的對(duì)象的1盡可能的多。
知道這個(gè)條件之后,這題就很簡(jiǎn)單了,我們只需要把我們累異或的結(jié)果都和這個(gè)最大值進(jìn)行異或就行。
class Solution {public int[] getMaximumXor(int[] nums, int maximumBit) {int flag = (1 << maximumBit) - 1;int[] ans = new int[nums.length];int k = 0;for(int i=0;i<nums.length;i++){k ^= nums[i];ans[nums.length-1-i] = flag ^ k;}return ans;}
}
線性前綴和統(tǒng)計(jì):
leetcode 523:連續(xù)的子數(shù)組和:
給你一個(gè)整數(shù)數(shù)組?nums
?和一個(gè)整數(shù)?k
?,編寫一個(gè)函數(shù)來判斷該數(shù)組是否含有同時(shí)滿足下述條件的連續(xù)子數(shù)組:
- 子數(shù)組大小?至少為 2?,且
- 子數(shù)組元素總和為?
k
?的倍數(shù)。
如果存在,返回?true
?;否則,返回?false
?。
如果存在一個(gè)整數(shù)?n
?,令整數(shù)?x
?符合?x = n * k
?,則稱?x
?是?k
?的一個(gè)倍數(shù)。0
?始終視為?k
?的一個(gè)倍數(shù)
輸入:nums = [23,2,4,6,7], k = 6 輸出:true 解釋:[2,4] 是一個(gè)大小為 2 的子數(shù)組,并且和為 6 。
先貼一個(gè)我一開始寫的超時(shí)解法:
class Solution {public boolean checkSubarraySum(int[] nums, int k) {int[] sum = new int[nums.length+1];int i,j;if(nums.length==1){return false;}if(nums.length==2){int temp = nums[0]+nums[1];return temp%k==0?true:false;}for(i=1;i<=nums.length;++i){sum[i] += nums[i-1] + sum[i-1];}for(i=0;i< nums.length-1;++i){for(j=(i+2);j<= nums.length;++j){if((sum[j]-sum[i])%k==0){return true;}}}return false;}
}
很明顯這是一個(gè)n方的解法。
下面貼正確解法:
首先在做這個(gè)題目之前,我們需要去明白一個(gè)數(shù)學(xué)關(guān)系:
預(yù)處理前綴和數(shù)組 sum,方便快速求得某一段區(qū)間的和。然后假定 [i,j] 是我們的目標(biāo)區(qū)間,那么有:
sum[j]?sum[i?1]=n?ksum[j] - sum[i - 1] = n * k
sum[j]?sum[i?1]=n?k
經(jīng)過簡(jiǎn)單的變形可得:
sum[j]/k? -? sum[i-1]/k? =? n
要使得兩者除 k 相減為整數(shù),需要滿足 sum[j] 和 sum[i?1]對(duì) k取余相同。
(這個(gè)就是我看題解看到的數(shù)學(xué)關(guān)系)下面是證明:
知道了這一層數(shù)學(xué)關(guān)系之后,我們的思路就變成了:
先開一個(gè)哈希表。
我們從前綴和數(shù)組i=2的情況開始遍歷,我們把sum[i-2]%k的這個(gè)余數(shù)存在哈希表中,
我們每次遍歷一個(gè)元素,就去查這個(gè)哈希表中是否有和我們這個(gè)余數(shù)相同的數(shù)。
這其實(shí)和經(jīng)典題目?jī)蓴?shù)之和有點(diǎn)像了。
class Solution {public boolean checkSubarraySum(int[] nums, int k) {int len = nums.length;int[] sum = new int[len+1];Set<Integer> table = new HashSet<>();for(int i=1;i<=len;++i){sum[i] += sum[i-1] + nums[i-1];}int flag = 0;for(int i=2;i<=len;++i){flag = sum[i-2]%k;table.add(flag);if(table.contains(sum[i]%k)){return true;}}return false;}
}
leetcode 1508:子數(shù)組和排序后的區(qū)間和:
給你一個(gè)數(shù)組?nums
?,它包含?n
?個(gè)正整數(shù)。你需要計(jì)算所有非空連續(xù)子數(shù)組的和,并將它們按升序排序,得到一個(gè)新的包含?n * (n + 1) / 2
?個(gè)數(shù)字的數(shù)組。
請(qǐng)你返回在新數(shù)組中下標(biāo)為?left
?到?right
?(下標(biāo)從 1 開始)的所有數(shù)字和(包括左右端點(diǎn))。由于答案可能很大,請(qǐng)你將它對(duì) 10^9 + 7 取模后返回。
輸入:nums = [1,2,3,4], n = 4, left = 1, right = 5 輸出:13 解釋:所有的子數(shù)組和為 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。將它們升序排序后,我們得到新的數(shù)組 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下標(biāo)從 le = 1 到 ri = 5 的和為 1 + 2 + 3 + 3 + 4 = 13 。
這題其實(shí)沒有什么技巧,就是一道前綴和的模擬題,我們先求一下前綴和數(shù)組,然后開一個(gè)長(zhǎng)度為n * (n + 1) / 2
?個(gè)數(shù)字的數(shù)組,對(duì)前綴和數(shù)組遍歷,把每個(gè)子數(shù)組的和給求出來,然后排序,最后輸出即可。
class Solution {int mod = 1000000007;public int rangeSum(int[] nums, int n, int left, int right) {int[] sum = new int[n+1];int i,j;for(i=1;i<=n;++i){sum[i] = sum[i-1] + nums[i-1];}int[] ans = new int[(n*(n+1))/2];int index = 0;for(i=1;i<=n;++i){for(j=i;j<=n;++j){ans[index++] = sum[j] - sum[i-1];}}Arrays.sort(ans);int result = 0;for(i=left-1;i<right;++i){result += ans[i];result = result%mod;}return result;}
}
這里說一個(gè)小坑:
就是最后這個(gè)result數(shù)據(jù)的處理:
我一開始是
Arrays.sort(ans);int result = 0;for(i=left-1;i<right;++i){result += ans[i]%mod;}return result;
這樣寫有什么問題呢,那個(gè)ans[i]會(huì)先做取余操作,然后再 + ,就會(huì)導(dǎo)致后面的結(jié)果溢出。
改成 result = (result + ans[i] )%mod 和 result += ans[i];? result = result%mod;都行。
leetcode 1423:可連續(xù)的最大點(diǎn)數(shù)
幾張卡牌?排成一行,每張卡牌都有一個(gè)對(duì)應(yīng)的點(diǎn)數(shù)。點(diǎn)數(shù)由整數(shù)數(shù)組?cardPoints
?給出。
每次行動(dòng),你可以從行的開頭或者末尾拿一張卡牌,最終你必須正好拿?k
?張卡牌。
你的點(diǎn)數(shù)就是你拿到手中的所有卡牌的點(diǎn)數(shù)之和。
給你一個(gè)整數(shù)數(shù)組?cardPoints
?和整數(shù)?k
,請(qǐng)你返回可以獲得的最大點(diǎn)數(shù)。
輸入:cardPoints = [1,2,3,4,5,6,1], k = 3 輸出:12 解釋:第一次行動(dòng),不管拿哪張牌,你的點(diǎn)數(shù)總是 1 。但是,先拿最右邊的卡牌將會(huì)最大化你的可獲得點(diǎn)數(shù)。最優(yōu)策略是拿右邊的三張牌,最終點(diǎn)數(shù)為 1 + 6 + 5 = 12 。
思路:
這題應(yīng)該怎么想呢?或者說我們?cè)趺赐熬Y和那個(gè)方面想呢?
我們知道前綴和解決的是連續(xù)子數(shù)組或者子字符串的問題,我們?cè)倏催@個(gè)題目,題目說我們抽牌可以從前面抽,也可以從后面抽,那這個(gè)數(shù)組就不一定是連續(xù)的了,
這個(gè)時(shí)候我們就需要逆向思維一下。
我們想要抽出來的牌最大,那就是剩下的牌最小,我們抽牌的數(shù)組不一定連續(xù),不過剩下來的數(shù)組一定是連續(xù)的,所以我們的思路就是去求剩下來的牌的最小值。
具體來說:
我們要抽k張牌,就是要剩下(len-k)張牌,所以我們可以維護(hù)一個(gè)(len-k)張牌的滑動(dòng)窗口。
我們一開始直接把這個(gè)滑動(dòng)窗口填滿,然后再開始遍歷這個(gè)數(shù)組,不斷更新這個(gè)連續(xù)子數(shù)組的最小值即可。
這里說一個(gè)題外話,為什么要先填滿滑動(dòng)窗口,其實(shí)我一開始的做法不是先填滿,是遍歷完了(len-k)個(gè)元素之后再遍歷剩下的元素,不過我感覺這樣下標(biāo)處理起來好麻煩。
class Solution {public int maxScore(int[] cardPoints, int k) {int len = cardPoints.length;int[] sum = new int[len+1];int i,cur = 0,min = Integer.MAX_VALUE;int flag = len-k;for(i=1;i<=len;++i){sum[i] = cardPoints[i-1] + sum[i-1];}for(i=0;i<flag;++i){cur += cardPoints[i];}for(i=flag;i<=len;++i){cur = Math.min(cur,sum[i]-sum[i-flag]);}return sum[len]-cur;}
}
leetcode 1685:有序數(shù)值中差絕對(duì)值之和:
給你一個(gè)?非遞減?有序整數(shù)數(shù)組?nums
?。
請(qǐng)你建立并返回一個(gè)整數(shù)數(shù)組?result
,它跟?nums
?長(zhǎng)度相同,且result[i]
?等于?nums[i]
?與數(shù)組中所有其他元素差的絕對(duì)值之和。
換句話說,?result[i]
?等于?sum(|nums[i]-nums[j]|)
?,其中?0 <= j < nums.length
?且?j != i
?(下標(biāo)從 0 開始)。
輸入:nums = [2,3,5] 輸出:[4,3,5] 解釋:假設(shè)數(shù)組下標(biāo)從 0 開始,那么 result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4, result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3, result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
思路:
根據(jù)這個(gè)例子很容易想到我們可以一種解法:
比如我們要找nums[i]==3這個(gè)情況下的result,我們可以用nums[i]*len - sum[len-1],
代碼:
class Solution {public int[] getSumAbsoluteDifferences(int[] nums) {int sum = 0;int i;for(i=0;i< nums.length;++i){sum += nums[i];}int[] result = new int[nums.length];for(i=0;i< nums.length;++i){result[i] = Math.abs((nums[i]* nums.length)-sum);}return result;}
}
我們很快就會(huì)發(fā)現(xiàn)是錯(cuò)誤的,因?yàn)檫@題算的是絕對(duì)值,
按原來的算法,我們用nums[i]*len - sum[len-1] 得出:3*3-10然后取絕對(duì)值,
這樣算出來的值是1,不過答案是3,問題就是3-2是>0的,而3-5是<,分開取絕對(duì)值的和是3,而我們直接把這兩個(gè)數(shù)合在一起算了。
解決辦法是:
我們觀察到這個(gè)數(shù)組是有序的,所以我們可以分段進(jìn)行求,并且利用前綴和數(shù)組進(jìn)行優(yōu)化,
class Solution {public int[] getSumAbsoluteDifferences(int[] nums) {int[] sum = new int[nums.length];int len = nums.length;int i,j;sum[0] = nums[0];for(i=1;i< nums.length;++i){sum[i] = sum[i-1] + nums[i];}int[] result = new int[len];for(i=0;i<len;++i){result[i] = ((i+1)*nums[i]-sum[i]) + (sum[len-1]-sum[i]-(len-i-1)*nums[i]);}return result;}
}
leetcode 2155:分組得分最高的所有下標(biāo):
給你一個(gè)下標(biāo)從?0?開始的二進(jìn)制數(shù)組?nums
?,數(shù)組長(zhǎng)度為?n
?。nums
?可以按下標(biāo)?i
(?0 <= i <= n
?)拆分成兩個(gè)數(shù)組(可能為空):numsleft
?和?numsright
?。
numsleft
?包含?nums
?中從下標(biāo)?0
?到?i - 1
?的所有元素(包括?0
?和?i - 1
?),而?numsright
?包含?nums
?中從下標(biāo)?i
?到?n - 1
?的所有元素(包括?i
?和?n - 1
?)。- 如果?
i == 0
?,numsleft
?為?空?,而?numsright
?將包含?nums
?中的所有元素。 - 如果?
i == n
?,numsleft
?將包含?nums
?中的所有元素,而?numsright
?為?空?。
下標(biāo)?i
?的?分組得分?為?numsleft
?中?0
?的個(gè)數(shù)和?numsright
?中?1
?的個(gè)數(shù)之?和?。
返回?分組得分 最高?的?所有不同下標(biāo)?。你可以按?任意順序?返回答案。
輸入:nums = [0,0,1,0] 輸出:[2,4] 解釋:按下標(biāo)分組 - 0 :numsleft 為 [] 。numsright 為 [0,0,1,0] 。得分為 0 + 1 = 1 。 - 1 :numsleft 為 [0] 。numsright 為 [0,1,0] 。得分為 1 + 1 = 2 。 - 2 :numsleft 為 [0,0] 。numsright 為 [1,0] 。得分為 2 + 1 = 3 。 - 3 :numsleft 為 [0,0,1] 。numsright 為 [0] 。得分為 2 + 0 = 2 。 - 4 :numsleft 為 [0,0,1,0] 。numsright 為 [] 。得分為 3 + 0 = 3 。 下標(biāo) 2 和 4 都可以得到最高的分組得分 3 。 注意,答案 [4,2] 也被視為正確答案。
思路:
我一開始想的思路是:求出前綴和數(shù)組,因?yàn)檫@個(gè)數(shù)組中只有0和1,所以,我們只要有了前綴和數(shù)組,我們可以通過下標(biāo)的關(guān)系很快得出0和1的個(gè)數(shù),也就是這個(gè)時(shí)候的分?jǐn)?shù)。
class Solution {public List<Integer> maxScoreIndices(int[] nums) {int len = nums.length;int[] sum = new int[len+1];for(int i=1;i<=len;++i){sum[i] = sum[i-1] + nums[i-1];}List<Integer> ans = new ArrayList<>();int score = -1;ans.add(score);int temp = 0;for(int i=0;i<=len;++i){temp = Math.abs(sum[i]-(i+1)) + sum[len] - sum[i];if(temp>score){ans.clear();ans.add(i);score = temp;} else if (temp==score) {ans.add(i);}}return ans;}
}
更好的思路:
這里其實(shí)可以利用到一點(diǎn)貪心的想法,我們要想讓這個(gè)分?jǐn)?shù)盡可能大,其實(shí)就讓左半邊盡可能有多的0。
class Solution {public List<Integer> maxScoreIndices(int[] nums) {int len = nums.length;int maxscore = 0;int preSum = 0;List<Integer> ans = new ArrayList<>();ans.add(0);for(int i=0;i<len;++i){if(nums[i]==0){preSum++;if(preSum>maxscore){ans.clear();ans.add(i+1);maxscore = preSum;} else if (preSum==maxscore) {ans.add(i+1);}}else preSum--;}return ans;}
}
?這里有一個(gè)小細(xì)節(jié)就是我們要在列表之前先墊一個(gè)0,我們可以想象:[1,1]這個(gè)數(shù)組,里面沒有一個(gè)0,如果我們不墊這個(gè)0,答案就什么都沒有。
leetcode 2222 選擇建筑的方案數(shù):
給你一個(gè)下標(biāo)從?0?開始的二進(jìn)制字符串?s
?,它表示一條街沿途的建筑類型,其中:
s[i] = '0'
?表示第?i
?棟建筑是一棟辦公樓,s[i] = '1'
?表示第?i
?棟建筑是一間餐廳。
作為市政廳的官員,你需要隨機(jī)?選擇?3 棟建筑。然而,為了確保多樣性,選出來的 3 棟建筑?相鄰?的兩棟不能是同一類型。
- 比方說,給你?
s = "001101"
?,我們不能選擇第?1
?,3
?和?5
?棟建筑,因?yàn)榈玫降淖有蛄惺?"011"
?,有相鄰兩棟建筑是同一類型,所以?不合?題意。
請(qǐng)你返回可以選擇 3 棟建筑的?有效方案數(shù)?。
輸入:s = "001101" 輸出:6 解釋: 以下下標(biāo)集合是合法的: - [0,2,4] ,從 "001101" 得到 "010" - [0,3,4] ,從 "001101" 得到 "010" - [1,2,4] ,從 "001101" 得到 "010" - [1,3,4] ,從 "001101" 得到 "010" - [2,4,5] ,從 "001101" 得到 "101" - [3,4,5] ,從 "001101" 得到 "101" 沒有別的合法選擇,所以總共有 6 種方法。
思路:
這題和之前的前綴和題目有些不同,這道題更多是用了前綴和的思想。
對(duì)任意一個(gè)位置,以它為中心構(gòu)建合法相鄰建筑的數(shù)量,分兩種情況討論:
該位置左側(cè)1的數(shù)量*該位置右側(cè)1的數(shù)量 (若該位置為0 )。這樣可以構(gòu)成101。
該位置左側(cè)0的數(shù)量*該位置右側(cè)0的數(shù)量 (若該位置為1 )。這樣可以構(gòu)成010。
一般前綴和得前綴和數(shù)組求得是某一個(gè)位置元素前面得和。
這道題求的是某一個(gè)位置前面1或者0的數(shù)量。
?具體算法思路:
- 先從右往左遍歷一次數(shù)組,算出對(duì)應(yīng)位置右側(cè)0或者1的數(shù)量(這個(gè)位置如果是0,就算1的數(shù)量,相反也一樣)
- 再從左往右遍歷一次數(shù)組,算出對(duì)應(yīng)位置的方案數(shù)(因?yàn)槲覀冞@個(gè)時(shí)候已經(jīng)有右側(cè)對(duì)應(yīng)的0和1的數(shù)量,這個(gè)時(shí)候的zeroCount和oneCount分別對(duì)應(yīng)左側(cè)的0和1的數(shù)量,我們直接相乘即可得出這個(gè)位置上的方案數(shù))
class Solution {public long numberOfWays(String s) {int len = s.length();int[] count = new int[len];char[] str = s.toCharArray();long ans = 0;int i;int oneCount = 0;int zeroCount = 0;//從右往左遍歷,統(tǒng)計(jì)每個(gè)位置右側(cè)0或者1的數(shù)量for(i=len-1;i>=0;i--){if(str[i]=='0'){count[i] = oneCount;}else count[i] = zeroCount;oneCount += str[i]=='1'?1:0;zeroCount += str[i]=='0'?1:0;}oneCount = 0; zeroCount = 0;//從左往右遍歷,根據(jù)count數(shù)組算出每個(gè)位置對(duì)應(yīng)的方案數(shù)for(i=0;i<len;++i){if(str[i]=='0'){count[i] *= oneCount;}else count[i] *= zeroCount;oneCount += str[i]=='1'?1:0;zeroCount += str[i]=='0'?1:0;ans += count[i];}return ans;}
}
線性前綴和+哈希表:
在做這個(gè)專題的題目之前,我覺得得先復(fù)習(xí)一下經(jīng)典的一道題目:兩數(shù)之和:
class Solution {public int[] twoSum(int[] nums, int target) {Map <Integer,Integer> table = new HashMap<>();table.put(nums[0],0);for(int i=1;i<nums.length;++i){if(table.containsKey(target-nums[i])){int[] ans = new int[2];ans[0] = table.get(target-nums[i]);ans[1] = i;return ans;}table.put(nums[i],i);}return new int[2];}
}
我感覺在做前綴和和哈希表的題目中總是有兩數(shù)之和這道題目的影子
兩數(shù)之和這道題用了哈希表求在一個(gè)集合中是否有我們需要的目標(biāo)值。
而在做前綴和的題目中用哈希表更像是在集合中找我們需要的區(qū)間段。
因?yàn)槲覀冎?#xff0c;前綴和就是用來解決子數(shù)組的問題?
下面上例題:
leetcode 930. 和相同的二元子數(shù)組:
給你一個(gè)二元數(shù)組?nums
?,和一個(gè)整數(shù)?goal
?,請(qǐng)你統(tǒng)計(jì)并返回有多少個(gè)和為?goal
?的?非空?子數(shù)組。
子數(shù)組?是數(shù)組的一段連續(xù)部分。
輸入:nums = [1,0,1,0,1], goal = 2 輸出:4 解釋: 有 4 個(gè)滿足題目要求的子數(shù)組:[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
class Solution {public int numSubarraysWithSum(int[] nums, int t) {int len = nums.length;Map<Integer,Integer> map = new HashMap<>();map.put(0,1);int[] sum = new int[len+1];int i,j;int ans = 0;for(i=1;i<=len;++i){sum[i] = sum[i-1] + nums[i-1];}for(i=0;i<len;++i){int tar = sum[i+1] - t;if(map.containsKey(tar)){ans += map.get(tar);}map.put(sum[i+1],map.getOrDefault(sum[i+1],0)+1);}return ans;}
}
?兩數(shù)之和中的哈希表存儲(chǔ)的是:數(shù)組的值和索引
而這道題存儲(chǔ)的是:前綴和數(shù)組的值和出現(xiàn)的次數(shù)
leetcode560: 和為K的子數(shù)組:
class Solution {public int subarraySum(int[] nums, int k) {if (nums.length == 0) {return 0;}HashMap<Integer,Integer> map = new HashMap<>();//細(xì)節(jié),這里需要預(yù)存前綴和為 0 的情況,會(huì)漏掉前幾位就滿足的情況//例如輸入[1,1,0],k = 2 如果沒有這行代碼,則會(huì)返回0,漏掉了1+1=2,和1+1+0=2的情況//輸入:[3,1,1,0] k = 2時(shí)則不會(huì)漏掉//因?yàn)閜resum[3] - presum[0]表示前面 3 位的和,所以需要map.put(0,1),墊下底map.put(0, 1);int count = 0;int presum = 0;for (int x : nums) {presum += x;//當(dāng)前前綴和已知,判斷是否含有 presum - k的前綴和,那么我們就知道某一區(qū)間的和為 k 了。if (map.containsKey(presum - k)) {count += map.get(presum - k);//獲取次數(shù)}//更新map.put(presum,map.getOrDefault(presum,0) + 1);}return count;}
}
?這道題就和上一道幾乎一模一樣,哈希表的存儲(chǔ)的都是前綴和數(shù)組的值和出現(xiàn)的次數(shù)。
leetcode 1248:統(tǒng)計(jì)優(yōu)美子數(shù)組:?
給你一個(gè)整數(shù)數(shù)組?nums
?和一個(gè)整數(shù)?k
。如果某個(gè)連續(xù)子數(shù)組中恰好有?k
?個(gè)奇數(shù)數(shù)字,我們就認(rèn)為這個(gè)子數(shù)組是「優(yōu)美子數(shù)組」。
請(qǐng)返回這個(gè)數(shù)組中?「優(yōu)美子數(shù)組」?的數(shù)目。
輸入:nums = [1,1,2,1,1], k = 3 輸出:2 解釋:包含 3 個(gè)奇數(shù)的子數(shù)組是 [1,1,2,1] 和 [1,2,1,1] 。
這道題其實(shí)沒有用到前綴和數(shù)組,不過用到了前綴和的思想。
前綴和數(shù)組表示數(shù)組下標(biāo)之前的數(shù)組元素的和
這道題用了前綴和的思想,我們不是去統(tǒng)計(jì)數(shù)組元素的和
而是統(tǒng)計(jì)數(shù)組下標(biāo)之前的奇數(shù)數(shù)字的個(gè)數(shù)。
做完這道題之后,我感覺對(duì)前綴和思想的理解深入了一點(diǎn),之前有一道題,leetcode2222也用了前綴和的思想,這道題統(tǒng)計(jì)的是數(shù)組下標(biāo)之前0或者1元素的個(gè)數(shù)。那個(gè)時(shí)候理解起來好別扭,可能是對(duì)這個(gè)前綴和數(shù)組的理解不對(duì),認(rèn)為做這種題目都需要去求這個(gè)前綴和數(shù)組。
?
class Solution {public int numberOfSubarrays(int[] nums, int k) {int len = nums.length;HashMap<Integer,Integer> map = new HashMap<>();//哈希表記錄的是前綴區(qū)間中的奇數(shù)個(gè)數(shù)map.put(0,1);int ans = 0;int oddnum = 0;int i,j;for(i=0;i<len;++i){oddnum += nums[i] & 1;if(map.containsKey(oddnum-k)){ans += map.get(oddnum-k);}map.put(oddnum,map.getOrDefault(oddnum,0)+1);}return ans;}
}
?leetcode 974:和可被K整除的子數(shù)組:
給定一個(gè)整數(shù)數(shù)組?nums
?和一個(gè)整數(shù)?k
?,返回其中元素之和可被?k
?整除的(連續(xù)、非空)?子數(shù)組?的數(shù)目。
子數(shù)組?是數(shù)組的?連續(xù)?部分。
輸入:nums = [4,5,0,-2,-3,1], k = 5 輸出:7 解釋: 有 7 個(gè)子數(shù)組滿足其元素之和可被 k = 5 整除: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
其實(shí)寫了三個(gè)題目了,已經(jīng)就是有感覺了,這道題和前幾道題有什么不同呢?特別是和為K的子數(shù)組,
在和為K的子數(shù)組中,我們的判斷條件是:是否含有sum[i] - k的前綴和
而在這一題中,我們的判斷條件是:是否含有sum[i] %k相同的前綴和。
知道了這一點(diǎn)之后,這題就和之前的題目差不多了。
class Solution {public int subarraysDivByK(int[] nums, int k) {int len = nums.length;HashMap<Integer,Integer> map = new HashMap<>();map.put(0,1);int i,j;int ans = 0;int[] sum = new int[len+1];for(i=1;i<=len;++i){sum[i] = sum[i-1] + nums[i-1];}for(i=0;i<len;++i){int key = (sum[i+1] % k + k) % k;if(map.containsKey(key)){ans += map.get(key);}map.put(key,map.getOrDefault(key,0)+1);}return ans;}
}
?注意點(diǎn):
我們看到上面代碼中有一段代碼是這樣的
int key = (presum % K + K) % K;
這是為什么呢?不能直接用 presum % k 嗎?這是因?yàn)楫?dāng)我們 presum 為負(fù)數(shù)時(shí),需要對(duì)其糾正。糾正前(-1) %2 = (-1),糾正之后 ( (-1) % 2 + 2) % 2=1 保存在哈希表中的則為 1.則不會(huì)漏掉部分情況,例如輸入為 [-1,2,9],K = 2如果不對(duì)其糾正則會(huì)漏掉區(qū)間 [2] 此時(shí) 2 % 2 = 0,符合條件,但是不會(huì)被計(jì)數(shù)。
我覺得這個(gè)取余的方法也可以記下來,用來處理一些碰到負(fù)數(shù)取余的情況。
差分:
差分可以看成前綴和的逆運(yùn)算
詳細(xì)差分算法理解看這個(gè)博客:前綴和與差分 圖文并茂 超詳細(xì)整理(全網(wǎng)最通俗易懂)-CSDN博客
我們稍微對(duì)比一下前綴和和差分的例子,來理解一下這兩個(gè)概念:
前綴和的作用很清楚了:
如果我們要求一個(gè)數(shù)組中某一段區(qū)間的數(shù)組和,我們用前綴和就可以在O(1)的時(shí)間內(nèi)查找出來。
而差分呢?
我們想象一個(gè)場(chǎng)景:我們有一個(gè)數(shù)組,我們要在規(guī)定的區(qū)間 [l,r] 這個(gè)區(qū)間內(nèi)+c ,我們同樣得遍歷,如果我們需要做n次這樣的操作,那時(shí)間復(fù)雜度就很高了。
所以差分?jǐn)?shù)組就是用來解決這個(gè)問題的。
對(duì) c[l]+=v:由于差分是前綴和的逆向過程,這個(gè)操作對(duì)于將來的查詢而言,帶來的影響是對(duì)于所有的下標(biāo)大于等于 l?的位置都增加了值 v;
對(duì) c[r+1]?=v:由于我們期望只對(duì) [l,r] 產(chǎn)生影響,因此需要對(duì)下標(biāo)大于 r 的位置進(jìn)行減值操作,從而抵消“影響”。
?最后我們?cè)儆们熬Y和的運(yùn)算來輸出結(jié)果即可。
leetcode 1109 航班預(yù)定統(tǒng)計(jì):
這里有?n
?個(gè)航班,它們分別從?1
?到?n
?進(jìn)行編號(hào)。
有一份航班預(yù)訂表?bookings
?,表中第?i
?條預(yù)訂記錄?bookings[i] = [firsti, lasti, seatsi]
?意味著在從?firsti
?到?lasti
?(包含?firsti
?和?lasti
?)的?每個(gè)航班?上預(yù)訂了?seatsi
?個(gè)座位。
請(qǐng)你返回一個(gè)長(zhǎng)度為?n
?的數(shù)組?answer
,里面的元素是每個(gè)航班預(yù)定的座位總數(shù)。
輸入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 輸出:[10,55,45,25,25] 解釋: 航班編號(hào) 1 2 3 4 5 預(yù)訂記錄 1 : 10 10 預(yù)訂記錄 2 : 20 20 預(yù)訂記錄 3 : 25 25 25 25 總座位數(shù): 10 55 45 25 25 因此,answer = [10,55,45,25,25]
這道題就是典型的差分題,
我們遍歷bookings數(shù)組,對(duì)數(shù)組中[l,r]區(qū)間加上對(duì)應(yīng)的位置。
在(r,len)再減去對(duì)應(yīng)的位置,達(dá)到平衡。
最后求出前綴和。
class Solution {public int[] corpFlightBookings(int[][] bs, int n) {int[] diff = new int[n+2];for(int[] b:bs){diff[b[0]] += b[2];diff[b[1]+1] -= b[2];}int[] ans = new int[n];ans[0] = diff[1];for(int i=1;i<n;++i){ans[i] = ans[i-1]+diff[i+1];}return ans;}
}