• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

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

极客笔记 Geekerstar 11个月前 (05-20) 659次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

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

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(8.5)Leetcode上线段树相关的问题
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00