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

資訊專欄INFORMATION COLUMN

[LintCode] Interval Sum

kelvinlee / 3198人閱讀

摘要：很簡單的題目，不過要達(dá)到的時(shí)間，只能用前綴和的方法來做。法前綴和法推薦

Problem

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(0,4),(1,2),(2,4)], return [23,9,20]

Challenge

O(logN) time for each query

Note

很簡單的題目，不過要達(dá)到O(logn)的時(shí)間，只能用前綴和的方法來做。

Solution

1. muggle法

public class Solution {
    public ArrayList intervalSum(int[] A, 
                                       ArrayList queries) {
        ArrayList res = new ArrayList ();
        for (int i = 0; i < queries.size(); i++) {
            int start = queries.get(i).start;
            int end = queries.get(i).end;
            res.add(sum(A, start, end));
        }
        return res;
    }
    public long sum(int[] A, int start, int end) {
        long sum = 0;
        for (int i = start; i <= end; i++) {
            sum += A[i];
        }
        return sum;
    }
}

2. 前綴和法（推薦）

public class Solution {
    public ArrayList intervalSum(int[] A, 
                                       ArrayList queries) {
        ArrayList res = new ArrayList();
        long[] preSum = new long[A.length];
        long sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            preSum[i] = sum;
        }
        for (Interval i: queries) {
            if (i.start == 0) {
                res.add(preSum[i.end]);
            }
            else {
                res.add(preSum[i.end] - preSum[i.start-1]);
            }
        }
        return res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

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

相關(guān)文章

  • [LeetCode/LintCode] Merge Intervals

    摘要：方法上沒太多難點(diǎn)，先按所有區(qū)間的起點(diǎn)排序，然后用和兩個(gè)指針，如果有交集進(jìn)行操作，否則向后移動。由于要求的，就對原數(shù)組直接進(jìn)行操作了。時(shí)間復(fù)雜度是的時(shí)間。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

    gougoujiang 評論0 收藏0

  • [LintCode] Interval Minimum Number

    摘要：這道題目是篩選出數(shù)組中的最小值，存入新數(shù)組。因此，聯(lián)想到和系列的題目，對于的處理，使用線段樹是非常有效的方法。之前我們創(chuàng)建的線段樹，有和兩個(gè)。參照這個(gè)參數(shù)，可以考慮在這道題增加一個(gè)的參數(shù)，代表每個(gè)結(jié)點(diǎn)的最小值。 Problem Given an integer array (index from 0 to n-1, where n is the size of this array),...

    taowen 評論0 收藏0

  • [LintCode/LeetCode] Meeting Rooms

    Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. Example Given intervals = [[0,30],[...

    Noodles 評論0 收藏0

  • [LintCode] Segment Tree Query I & Segment Tree

    摘要：題目是要查詢到這個(gè)區(qū)間內(nèi)某一點(diǎn)的。值是從最底層的子節(jié)點(diǎn)值里取最大值。因此，不用太復(fù)雜，遞歸就可以了。與所不同的是，對所給區(qū)間內(nèi)的元素個(gè)數(shù)求和，而非篩選。這樣就會出現(xiàn)的情況，視作本身處理。 Segment Tree Query Problem For an integer array (index from 0 to n-1, where n is the size of this ar...

    vibiu 評論0 收藏0

  • [LintCode] Teemo Attacking

    Problem In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemos attacking ascending time series towards Ashe and the poison...

    whjin 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<