中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

昆明快速做網(wǎng)站海南網(wǎng)站制作

昆明快速做網(wǎng)站,海南網(wǎng)站制作,高毅資產(chǎn)網(wǎng)站誰做的,辦辦網(wǎng)登陸前綴和是什么: 前綴和指一個(gè)數(shù)組的某下標(biāo)之前的所有數(shù)組元素的和(包含其自身)。前綴和分為一維前綴和,以及二維前綴和。前綴和是一種重要的預(yù)處理,能夠降低算法的時(shí)間復(fù)雜度 說個(gè)人話就是比如有一個(gè)數(shù)組: …

前綴和是什么:


前綴和指一個(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ì)了。

  1. 兩個(gè)數(shù)異或,相同的位數(shù)等于0 ;0110 ^ 1100 = 1010
  2. 一個(gè)數(shù)與0異或,結(jié)果等于本身;
  3. 一個(gè)數(shù)異或本身,結(jié)果為0;
  4. 綜上,可得第四條性質(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?次:

  1. 找到一個(gè)非負(fù)整數(shù)?k < 2的maximumBit次方?,使得?nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k?的結(jié)果?最大化?。k?是第?i?個(gè)查詢的答案。
  2. 從當(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;}
}

http://www.risenshineclean.com/news/22062.html

相關(guān)文章:

  • 網(wǎng)站服務(wù)器租用價(jià)格表怎么從網(wǎng)上找國(guó)外客戶
  • 藍(lán)色網(wǎng)站素材搜索引擎推廣案例
  • 企業(yè)logo設(shè)計(jì)app搜狗seo怎么做
  • 做淘寶要用到哪些網(wǎng)站中國(guó)優(yōu)化網(wǎng)
  • asp網(wǎng)站圖片怎樣建立自己網(wǎng)站
  • 神州順利辦深一做網(wǎng)站百度搜索排行seo
  • 網(wǎng)絡(luò)營(yíng)銷資訊網(wǎng)站重慶網(wǎng)站推廣聯(lián)系方式
  • 網(wǎng)站怎么做白色字蘇州吳中區(qū)seo關(guān)鍵詞優(yōu)化排名
  • 網(wǎng)站怎樣做seo成功營(yíng)銷案例分享
  • 昆明網(wǎng)站做項(xiàng)目推廣平臺(tái)有哪些
  • 新手站長(zhǎng)如何購買虛擬主機(jī)做網(wǎng)站seo對(duì)各類網(wǎng)站的作用
  • 哪個(gè)網(wǎng)站可以懸賞做圖宣傳推廣的十種方式
  • 國(guó)內(nèi)環(huán)保行業(yè)網(wǎng)站開發(fā)seo獨(dú)立站
  • 自己做的網(wǎng)站主頁打開速度上海百度分公司電話
  • 裝飾裝修網(wǎng)站建設(shè)方案做網(wǎng)絡(luò)銷售如何找客戶
  • crm辦公系統(tǒng)武漢關(guān)鍵詞seo
  • 建設(shè)網(wǎng)站學(xué)什么條件網(wǎng)站運(yùn)營(yíng)和維護(hù)
  • 無法訪問WordPress二級(jí)馮耀宗seo
  • 那家專門做特賣的網(wǎng)站權(quán)威seo技術(shù)
  • 免費(fèi)網(wǎng)站空間可訪問小網(wǎng)站怎么搜關(guān)鍵詞
  • 做網(wǎng)站引流的最佳方法四川自助seo建站
  • 企業(yè)網(wǎng)站推廣的收獲與啟示軟件開發(fā)培訓(xùn)學(xué)校
  • 中國(guó)企業(yè)招聘網(wǎng)seo外鏈技巧
  • w網(wǎng)站開發(fā)文獻(xiàn)百度投訴中心在線申訴
  • 紹興優(yōu)秀做網(wǎng)站的蘇州網(wǎng)站維護(hù)
  • it行業(yè)做網(wǎng)站一個(gè)月多少錢中國(guó)推廣網(wǎng)站
  • 用ecshop的網(wǎng)站西地那非片能延時(shí)多久有副作用嗎
  • 網(wǎng)站推廣方案途徑網(wǎng)站設(shè)計(jì)公司怎么樣
  • ubuntu apache php mysql wordpress某個(gè)網(wǎng)站seo分析實(shí)例
  • 網(wǎng)頁設(shè)計(jì)站點(diǎn)規(guī)劃蘇州seo營(yíng)銷