[LintCode] Interval Sum

kelvinlee 發布于2019-08-14 16:23 / 3191人閱讀

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

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

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

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;
    }
}

云服務器 GPU云服務器 Interval LintCode LintCode134_LRU sum

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

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

[LeetCode/LintCode] Merge Intervals

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

gougoujiang 2019-08-14 15:16 評論0 收藏0
[LintCode] Interval Minimum Number

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

taowen 2019-08-14 16:23 評論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 2019-08-16 12:34 評論0 收藏0
[LintCode] Segment Tree Query I & Segment Tree

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

vibiu 2019-08-14 16:22 評論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 2019-08-16 12:37 評論0 收藏0