370. Range Addition

bluesky 發布于2019-08-14 17:25 / 2309人閱讀

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

370. Range Addition

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

這道題暴力法是可以的，每次把所有在start到end之間的值都更新一遍，不過題目要求要O(k+n)，所以其實每次更新只能用constant的時間。有點像prefix sum的意思，每次只更新第一個值，最后把值加起來，最后怎么確定結束的地方呢？沒法知道在哪結束，但是可能讓結束之后的地方恢復原來的值，所以要在[end+1]的方法更新成負值，這樣結束之后就抵消了。如果結束的地方就在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;
    }
}

GPU云服務器云服務器 Addition range() Range Range操作

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66629.html

370. Range Addition

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

shuibo 2019-08-14 14:16 評論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 2019-08-16 12:46 評論0 收藏0
Java實現通過日語元音ae的發音曲線分類9個發音者

摘要：需要對個人的日語元音的發音分析，然后根據分析確定名發音者。九個發音者發出兩個日本元音先后。其中每塊數據中包含的行數為到不等，每行代表著發音者的一個時間幀。業務理解（Business Understanding）該業務是分類問題。需要對9個人的日語元音ae的發音分析，然后根據分析確定9名發音者。ae.train文件是訓練數據集，ae.test文件是用來測試訓練效果的，size_ae...

lncwwn 2019-08-14 12:04 評論0 收藏0
【開發語言】PHP、Java、C語言的編譯執行過程

摘要：效率比較低，依賴解釋器，跨平臺性好語言編譯執行過程下面都是鳥哥博客的內容深入理解原理之引擎對這個文件進行詞法分析，語法分析，編譯成，然后執行。編譯型語言和解釋型語言從PHP，Java和C語言的編譯執行過程可以先解釋下編譯型語言和解釋型語言。編譯型語言程序在執行之前需要一個專門的編譯過程，把程序編譯成為機器語言的文件，運行時不需要重新翻譯，直接使用編譯的結果就行了。程序執行效率高...

gnehc 2019-08-15 10:47 評論0 收藏0