数据结构笔记总结(8.5)Leetcode上线段树相关的问题

303. 区域和检索 – 数组不可变

给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

说明:

  1. 你可以假设数组不可变。
  2. 会多次调用 sumRange 方法。

这道题和我们之前的题不同,不是让我们创建一个solution类,而是设计一个叫做NumArray的类,对于这个类有它的构造函数也有方法,我们写算法的方式就是构建这个类的对象

class NumArray {

    public NumArray(int[] nums) {
        
    }
    
    public int sumRange(int i, int j) {
        
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

根据题目描述及分析我们可以非常容易使用线段树来解决

class NumArray {

    private SegmentTree segmentTree;
    public NumArray(int[] nums) {

        if(nums.length > 0){
            Integer[] data = new Integer[nums.length];
            for (int i = 0; i < nums.length; i++)
                data[i] = nums[i];
            segmentTree = new SegmentTree<>(data, (a, b) -> a + b);
        }

    }

    public int sumRange(int i, int j) {

        if(segmentTree == null)
            throw new IllegalArgumentException("Segment Tree is null");

        return segmentTree.query(i, j);
    }
}

对于这个问题虽然关注的是区间的和,但是由于这个数据是不可变的,其实不使用线段树可以得到更好的解答,使用预处理方式解答

public class NumArray {

    private int[] sum; // sum[i]存储前i个元素和, sum[0] = 0
                       // 即sum[i]存储nums[0...i-1]的和
                       // sum(i, j) = sum[j + 1] - sum[i]
    public NumArray2(int[] nums) {

        sum = new int[nums.length + 1];
        sum[0] = 0;
        for(int i = 1 ; i < sum.length ; i ++)
            sum[i] = sum[i - 1] + nums[i - 1];
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(8.5)Leetcode上线段树相关的问题

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多