成人艹逼视频,无码在线免费视频,色播五月天婷婷,欧美手机精品在线,插吧插吧综合网,午夜艹逼,黄色片网站免费观看,久热视频在线

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 區(qū)間加法，我們先來看題面：

https://leetcode-cn.com/problems/range-addition/

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

假設(shè)你有一個長度為 n 的數(shù)組，初始情況下所有的數(shù)字均為 0，你將會被給出 k 個更新的操作。

其中，每個操作會被表示為一個三元組：[startIndex, endIndex, inc]，你需要將子數(shù)組 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。

請你返回 k 次操作后的數(shù)組。

示例

示例:

輸入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
輸出: [-2,0,3,5,3]

解釋:

初始狀態(tài):
[0,0,0,0,0]

進行了操作 [1,3,2] 后的狀態(tài):
[0,2,2,2,0]

進行了操作 [2,4,3] 后的狀態(tài):
[0,2,5,5,3]

進行了操作 [0,2,-2] 后的狀態(tài):
[-2,0,3,5,3]

解題

創(chuàng)建一個 int[] 數(shù)組 ans，長度為 length。

??對于每一個給定的 [startIndex, endIndex, inc] 我們可以理解成如下：

??把 ans 的 [startIndex,length-1] 都加上了 inc，然后再把 [endIndex+1, length-1] 再減去 inc。

??具體的操作是：

??1、先 ans[startIndex] += val，ans[endIndex+1] += -val；

??2、然后 [startIndex,length-1] 遍歷進行 ans[i] += ans[i-1]。

??這樣做的目的是因為所有的三元組 [startIndex, endIndex, inc] 對數(shù)組 ans 的操作是獨立的，我們先對所有的三元組對 ans 的操作在邊界上做好，然后遍歷一遍 ans 數(shù)組即可同時執(zhí)行完所有三元組對 ans 的操作。

class Solution {
   public int[] getModifiedArray(int length, int[][] updates) {
        int[] ans = new int[length];
        int start, end, val;
        for (int[] update : updates) {
            start = update[0];
            end = update[1];
            val = update[2];
            ans[start] += val;
            if (end < length - 1) {
                ans[end + 1] -= val;
            }
        }
        for (int i = 1; i < length; i++) {
            ans[i] += ans[i - 1];
        }
        return ans;
    }
}