成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

370. Range Addition

bluesky / 2328人閱讀

摘要：題目鏈接這道題暴力法是可以的，每次把所有在到之間的值都更新一遍，不過(guò)題目要求要，所以其實(shí)每次更新只能用的時(shí)間。如果結(jié)束的地方就在末尾，那就不更新。

370. Range Addition

題目鏈接：https://leetcode.com/problems...

這道題暴力法是可以的，每次把所有在start到end之間的值都更新一遍，不過(guò)題目要求要O(k+n)，所以其實(shí)每次更新只能用constant的時(shí)間。有點(diǎn)像prefix sum的意思，每次只更新第一個(gè)值，最后把值加起來(lái)，最后怎么確定結(jié)束的地方呢？沒(méi)法知道在哪結(jié)束，但是可能讓結(jié)束之后的地方恢復(fù)原來(lái)的值，所以要在[end+1]的方法更新成負(fù)值，這樣結(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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66629.html

相關(guān)文章

  • 370. Range Addition

    摘要：題目解法這題與算法無(wú)關(guān)，是個(gè)數(shù)學(xué)題。思想是把所有需要相加的值存在第一個(gè)數(shù)，然后把這個(gè)范圍的最后一位的下一位減去這個(gè)這樣我所以這個(gè)范圍在求最終值的時(shí)候，都可以加上這個(gè)，而后面的數(shù)就不會(huì)加上。 題目：Assume you have an array of length n initialized with all 0s and are given k update operations. ...

    shuibo 評(píng)論0 收藏0

  • [LintCode/LeetCode] Range Addition

    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...

    endless_road 評(píng)論0 收藏0

  • Java實(shí)現(xiàn)通過(guò)日語(yǔ)元音ae的發(fā)音曲線(xiàn)分類(lèi)9個(gè)發(fā)音者

    摘要：需要對(duì)個(gè)人的日語(yǔ)元音的發(fā)音分析，然后根據(jù)分析確定名發(fā)音者。九個(gè)發(fā)音者發(fā)出兩個(gè)日本元音先后。其中每塊數(shù)據(jù)中包含的行數(shù)為到不等，每行代表著發(fā)音者的一個(gè)時(shí)間幀。 業(yè)務(wù)理解（Business Understanding） 該業(yè)務(wù)是分類(lèi)問(wèn)題。需要對(duì)9個(gè)人的日語(yǔ)元音ae的發(fā)音分析，然后根據(jù)分析確定9名發(fā)音者。ae.train文件是訓(xùn)練數(shù)據(jù)集，ae.test文件是用來(lái)測(cè)試訓(xùn)練效果的，size_ae...

    lncwwn 評(píng)論0 收藏0

  • 【開(kāi)發(fā)語(yǔ)言】PHP、Java、C語(yǔ)言的編譯執(zhí)行過(guò)程

    摘要：效率比較低，依賴(lài)解釋器，跨平臺(tái)性好語(yǔ)言編譯執(zhí)行過(guò)程下面都是鳥(niǎo)哥博客的內(nèi)容深入理解原理之引擎對(duì)這個(gè)文件進(jìn)行詞法分析，語(yǔ)法分析，編譯成，然后執(zhí)行。 編譯型語(yǔ)言和解釋型語(yǔ)言 從PHP，Java和C語(yǔ)言的編譯執(zhí)行過(guò)程可以先解釋下編譯型語(yǔ)言和解釋型語(yǔ)言。 編譯型語(yǔ)言 程序在執(zhí)行之前需要一個(gè)專(zhuān)門(mén)的編譯過(guò)程，把程序編譯成為機(jī)器語(yǔ)言的文件，運(yùn)行時(shí)不需要重新翻譯，直接使用編譯的結(jié)果就行了。程序執(zhí)行效率高...

    gnehc 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<