摘要:題目鏈接這道題暴力法是可以的,每次把所有在到之間的值都更新一遍,不過題目要求要,所以其實每次更新只能用的時間。如果結(jié)束的地方就在末尾,那就不更新。
370. Range Addition
題目鏈接:https://leetcode.com/problems...
這道題暴力法是可以的,每次把所有在start到end之間的值都更新一遍,不過題目要求要O(k+n),所以其實每次更新只能用constant的時間。有點像prefix sum的意思,每次只更新第一個值,最后把值加起來,最后怎么確定結(jié)束的地方呢?沒法知道在哪結(jié)束,但是可能讓結(jié)束之后的地方恢復(fù)原來的值,所以要在[end+1]的方法更新成負值,這樣結(jié)束之后就抵消了。如果結(jié)束的地方就在array末尾,那就不更新。
public class Solution { public int[] getModifiedArray(int length, int[][] updates) { int[] result = new int[length]; // only update start and end + 1 for(int[] update : updates) { result[update[0]] += update[2]; if(update[1] < length - 1) result[update[1] + 1] -= update[2]; } // calculate prefix sum int prefix = 0; for(int i = 0; i < result.length; i++) { result[i] += prefix; prefix = result[i]; } return result; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66629.html
摘要:題目解法這題與算法無關(guān),是個數(shù)學(xué)題。思想是把所有需要相加的值存在第一個數(shù),然后把這個范圍的最后一位的下一位減去這個這樣我所以這個范圍在求最終值的時候,都可以加上這個,而后面的數(shù)就不會加上。 題目:Assume you have an array of length n initialized with all 0s and are given k update operations. ...
Problem Assume you have an array of length n initialized with all 0s and are given k update operations. Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each el...
摘要:需要對個人的日語元音的發(fā)音分析,然后根據(jù)分析確定名發(fā)音者。九個發(fā)音者發(fā)出兩個日本元音先后。其中每塊數(shù)據(jù)中包含的行數(shù)為到不等,每行代表著發(fā)音者的一個時間幀。 業(yè)務(wù)理解(Business Understanding) 該業(yè)務(wù)是分類問題。需要對9個人的日語元音ae的發(fā)音分析,然后根據(jù)分析確定9名發(fā)音者。ae.train文件是訓(xùn)練數(shù)據(jù)集,ae.test文件是用來測試訓(xùn)練效果的,size_ae...
摘要:效率比較低,依賴解釋器,跨平臺性好語言編譯執(zhí)行過程下面都是鳥哥博客的內(nèi)容深入理解原理之引擎對這個文件進行詞法分析,語法分析,編譯成,然后執(zhí)行。 編譯型語言和解釋型語言 從PHP,Java和C語言的編譯執(zhí)行過程可以先解釋下編譯型語言和解釋型語言。 編譯型語言 程序在執(zhí)行之前需要一個專門的編譯過程,把程序編譯成為機器語言的文件,運行時不需要重新翻譯,直接使用編譯的結(jié)果就行了。程序執(zhí)行效率高...
閱讀 4133·2021-11-22 13:52
閱讀 2500·2021-11-22 13:52
閱讀 3672·2021-11-19 09:59
閱讀 1173·2021-11-17 09:33
閱讀 2435·2019-08-30 10:53
閱讀 1191·2019-08-29 17:28
閱讀 1297·2019-08-29 17:03
閱讀 3087·2019-08-26 11:31