327. Count of Range Sum

mj 發布于2019-08-14 17:34 / 457人閱讀

摘要：題目鏈接這題實際就是給定范圍內的，的方法。注意一開始把加進去，考慮結果是的情況，還有要用型，以免會還是可以來做，要統計范圍內的個數，就是用。

327. Count of Range Sum

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

這題實際就是給定范圍內的range sum，divide and conquer的方法。一路計算prefixSum[0:i]，并把結果放進tree里面，然后計算到prefixSum[0:j+1]的時候，找tree里面有沒有滿足條件的prefixSum[0:i]，這里的條件是lower <= sum[0:j+1] - sum[0:i] <= upper，那么可知sum[0:j+1] - upper <= sum[0:i] <= sum[0:j+1] - lower，那么這個就一個recursion就好了。注意一開始把0加進去，考慮結果是sum[0:j]的情況，還有要用long型，以免sum會overflow

public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        if(n == 0) return 0;
        // binary search tree
        Node root = new Node(0);
        int res = 0;
        long prefixSum = 0;
        for(int i = 0; i < n; i++) {
            prefixSum += nums[i];
            res += findNumInBound(root, lower, upper, prefixSum);
            insert(root, prefixSum);
        }
        return res;
    }
    
    private int findNumInBound(Node node, long low, long up, long sum) {
        // base case
        if(node == null) return 0;
        // range: sum - up <= node.val <= sum - low
        if(node.val < sum - up) return findNumInBound(node.right, low, up, sum);
        else if(node.val > sum - low) return findNumInBound(node.left, low, up, sum);
        else return 1 + findNumInBound(node.left, low, up, sum) + findNumInBound(node.right, low, up, sum);
    }
    
    private void insert(Node node, long value) {
        while(node != null) {
            if(node.val > value) {
                if(node.left == null) {
                    node.left = new Node(value);
                    break;
                }
                node = node.left;
            }
            else {
                if(node.right == null) {
                    node.right = new Node(value);
                    break;
                }
                node = node.right;
            }
        }
    }
    
    class Node {
        long val;
        Node left;
        Node right;
        Node(long val) { this.val = val; }
    }
}

還是可以binary index tree來做，要統計sum[0:j+1] - upper <= sum[0:i] <= sum[0:j+1] - lower范圍內的個數，就是用sum。參考博客：
http://bookshadow.com/weblog/...

public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        if(n == 0) return 0;
        // prefix array
        long[] prefixSum = new long[n];
        for(int i = 0; i < n; i++) {
            prefixSum[i] = (i > 0 ? prefixSum[i-1] : 0) + nums[i];
        }
        long[] sorted = Arrays.copyOf(prefixSum, prefixSum.length);
        Arrays.sort(sorted);
        // binary index tree
        map = new HashMap();
        int idx = 1;
        for(long sum : sorted) {
            if(!map.containsKey(sum)) map.put(sum, idx++);
        }
        // build tree
        BIT t = new BIT(idx);
        int res = 0;
        for(int i = 0; i < n; i++) {
            int l = binarySearch(sorted, prefixSum[i] - upper - 1);
            int r = binarySearch(sorted, prefixSum[i] - lower);
            res += t.sum(r) - t.sum(l);
            if(prefixSum[i] >= lower && prefixSum[i] <= upper) res += 1;
            t.add(map.get(prefixSum[i]), 1);
        }
        return res;
    }
    Map map;
    // find the last element <= val
    private int binarySearch(long[] arr, long val) {
        int l = 0, r = arr.length - 1;
        while(l < r) {
            int mid = l + (r - l) / 2 + 1;
            if(arr[mid] <= val) l = mid;
            else r = mid - 1;
        }
        if(arr[l] > val) return 0;
        return map.get(arr[l]);
    }
    
    class BIT {
        int n;
        int[] tree;
        BIT(int n) { this.n = n; tree = new int[n]; }
        
        protected int sum(int i) {
            int res = 0;
            while(i > 0) {
                res += tree[i];
                i -= i & -i;
            }
            return res;
        }
        
        protected void add(int i, int val) {
            while(i < n) {
                tree[i] += val;
                i += i & -i;
            }
        }
    }
}

云服務器 GPU云服務器 range() Range Count sum

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

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

leetcode327. Count of Range Sum

摘要：接著計算所有子數組中元素的和，并判斷是否位于數值區間內。因此，在對左右子數組進行排序后，以左子數組中的每一位作為開頭，在右子數組中找到滿足和區間的第一個值，和超過區間的第一個值。則二者的差即為橫穿左右的滿足條件的子數組個數。題目要求 Given an integer array nums, return the number of range sums that lie in [lo...

miya 2019-08-16 16:47 評論0 收藏0
幾個有趣的算法題目

摘要：統計元素個數排序第一步用來枚舉和的大小，由題目可知，數組的長度。時間復雜度為數組長度，排序的時間為，枚舉時間為，枚舉時間為跨度，枚舉全部元素時間為，因此算法的時間上界為實際情況下，由于剪枝等操作的存在，應優于這個時間。本文首發 http://svtter.cn 最接近的數字題目一個K位的數N $$ (Kleq2000，Nleq10^{20}) $$ 找出一個比N大且最接近的數，這...

honhon 2019-07-30 14:56 評論0 收藏0
SICP Python 描述 2.3 序列

摘要：序列不是特定的抽象數據類型，而是不同類型共有的一組行為。不像抽象數據類型，我們并沒有闡述如何構造序列。這兩個選擇器和一個構造器，以及一個常量共同實現了抽象數據類型的遞歸列表。 2.3 序列來源：2.3 Sequences 譯者：飛龍協議：CC BY-NC-SA 4.0 序列是數據值的順序容器。不像偶對只有兩個元素，序列可以擁有任意（但是有限）個有序元素。序列在計算機科學中...

AlexTuan 2019-07-25 10:43 評論0 收藏0
315. Count of Smaller Numbers After Self

摘要：題目鏈接的題，用來做，這種求有多少的題一般都是。里多加一個信息表示以為的節點數。也可以做，因為是統計有多少的，其實就是求從最小值到的。的是，要做一個映射，把的值映射到之間。所以先把給一下，用一個來做映射。還有的方法，參考 315. Count of Smaller Numbers After Self 題目鏈接：https://leetcode.com/problems... divi...

cnio 2019-08-14 17:34 評論0 收藏0
[LeetCode] 4Sum & 4Sum II

摘要：和方法一樣，多一個數，故多一層循環。完全一致，不再贅述， 4Sum Problem Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which ...

sydMobile 2019-08-14 15:42 評論0 收藏0