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

資訊專欄INFORMATION COLUMN

327. Count of Range Sum

mj / 468人閱讀

摘要：題目鏈接這題實際就是給定范圍內(nèi)的，的方法。注意一開始把加進(jìn)去，考慮結(jié)果是的情況，還有要用型，以免會還是可以來做，要統(tǒng)計范圍內(nèi)的個數(shù)，就是用。

327. Count of Range Sum

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

這題實際就是給定范圍內(nèi)的range sum，divide and conquer的方法。一路計算prefixSum[0:i]，并把結(jié)果放進(jìn)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加進(jìn)去，考慮結(jié)果是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來做，要統(tǒng)計sum[0:j+1] - upper <= sum[0:i] <= sum[0:j+1] - lower范圍內(nèi)的個數(shù)，就是用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;
            }
        }
    }
}

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

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

相關(guān)文章

  • leetcode327. Count of Range Sum

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

    miya 評論0 收藏0

  • 幾個有趣的算法題目

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

    honhon 評論0 收藏0

  • SICP Python 描述 2.3 序列

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

    AlexTuan 評論0 收藏0

  • 315. Count of Smaller Numbers After Self

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

    cnio 評論0 收藏0

  • [LeetCode] 4Sum & 4Sum II

    摘要：和方法一樣，多一個數(shù)，故多一層循環(huán)。完全一致，不再贅述， 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 評論0 收藏0

發(fā)表評論

0條評論

mj

男|高級講師

TA的文章

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