370. Range Addition

bluesky 发布于2019-08-14 17:25 / 2222人阅读

摘要：题目链接这道题暴力法是可以的，每次把所有在到之间的值都更新一遍，不过题目要求要，所以其实每次更新只能用的时间。如果结束的地方就在末尾，那就不更新。

370. Range Addition

题目链接：https://leetcode.com/problems...

这道题暴力法是可以的，每次把所有在start到end之间的值都更新一遍，不过题目要求要O(k+n)，所以其实每次更新只能用constant的时间。有点像prefix sum的意思，每次只更新第一个值，最后把值加起来，最后怎么确定结束的地方呢？没法知道在哪结束，但是可能让结束之后的地方恢复原来的值，所以要在[end+1]的方法更新成负值，这样结束之后就抵消了。如果结束的地方就在array末尾，那就不更新。

public class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        // only update start and end + 1
        for(int[] update : updates) {
            result[update[0]] += update[2];
            if(update[1] < length - 1) result[update[1] + 1] -= update[2];
        }
        // calculate prefix sum
        int prefix = 0;
        for(int i = 0; i < result.length; i++) {
            result[i] += prefix;
            prefix = result[i];
        }
        return result;
    }
}

GPU云服务器云服务器 Addition range() Range Range操作

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66629.html

370. Range Addition

摘要：题目解法这题与算法无关，是个数学题。思想是把所有需要相加的值存在第一个数，然后把这个范围的最后一位的下一位减去这个这样我所以这个范围在求最终值的时候，都可以加上这个，而后面的数就不会加上。题目：Assume you have an array of length n initialized with all 0s and are given k update operations. ...

shuibo 2019-08-14 14:16 评论0 收藏0
[LintCode/LeetCode] Range Addition

Problem Assume you have an array of length n initialized with all 0s and are given k update operations. Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each el...

endless_road 2019-08-16 12:46 评论0 收藏0
Java实现通过日语元音ae的发音曲线分类9个发音者

摘要：需要对个人的日语元音的发音分析，然后根据分析确定名发音者。九个发音者发出两个日本元音先后。其中每块数据中包含的行数为到不等，每行代表着发音者的一个时间帧。业务理解（Business Understanding）该业务是分类问题。需要对9个人的日语元音ae的发音分析，然后根据分析确定9名发音者。ae.train文件是训练数据集，ae.test文件是用来测试训练效果的，size_ae...

lncwwn 2019-08-14 12:04 评论0 收藏0
【开发语言】PHP、Java、C语言的编译执行过程

摘要：效率比较低，依赖解释器，跨平台性好语言编译执行过程下面都是鸟哥博客的内容深入理解原理之引擎对这个文件进行词法分析，语法分析，编译成，然后执行。编译型语言和解释型语言从PHP，Java和C语言的编译执行过程可以先解释下编译型语言和解释型语言。编译型语言程序在执行之前需要一个专门的编译过程，把程序编译成为机器语言的文件，运行时不需要重新翻译，直接使用编译的结果就行了。程序执行效率高...

gnehc 2019-08-15 10:47 评论0 收藏0