通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 1480. 一维数组的动态和(简单)一题三解

230人浏览 / 0人评论 / | 作者:whisper  | 分类: 设计模式与算法  | 标签: leetcode

作者:whisper

链接:https://www.qingyu.blue/article/821

声明:请尊重原作者的劳动,如需转载请注明出处


说一个简单题

1480. 一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1:

输入:nums = [1,2,3,4]
输出:[1,3,6,10]
解释:动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2:

输入:nums = [1,1,1,1,1]
输出:[1,2,3,4,5]
解释:动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

示例 3:

输入:nums = [3,1,2,10,1]
输出:[3,4,6,16,17]

提示:

1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6

下面是完整java代码

class Solution {
    int len = 0;
    // 前缀和
    public int[] runningSum(int[] nums) {
        int[] res = new int[nums.length];
        res[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            res[i] = res[i - 1] + nums[i];
        }

        return res;
    }

    // 优化:不使用额外空间
    public int[] runningSum2(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            nums[i] = nums[i - 1] + nums[i];
        }

        return nums;
    }

    // 趣味优化:一行代码(使用一个全局变量)
    public int[] runningSum3(int[] nums) {
        return ++len == nums.length ? (((len = 0) == 0) ? nums : new int[0])
            : (((nums[len] = nums[len - 1] + nums[len]) == nums[len] -1) ? new int[0] : runningSum(nums)); 
    }
}

runningSum是一般解法,定义一个结果数组,每次利用前一项更新下一项

runningSum2是优化后的解法,不使用额外空间

runningSum3只有一行代码(额外用到了一个对象变量),这里说一下一个技巧,在判断中赋值,比如想赋值后判断为真,那么可以 (a=2) == a,如果想赋值后判断为假,那么可以(a=2) == a - 1,这样不但赋值了,而且可以控制下一步的分支,配合?:,既可以有赋值,又可以有语句和分支,那么可以做的事就比较多了


自己写的文章声明标题示例:


点赞(0) 打赏

全部评论

还没有评论!