【力扣】1588. 所有奇数长度子数组的和 <前缀和>

这篇具有很好参考价值的文章主要介绍了【力扣】1588. 所有奇数长度子数组的和 <前缀和>。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【力扣】1588. 所有奇数长度子数组的和

给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。

示例 1:
输入:arr = [1,4,2,5,3]
输出:58
解释:所有奇数长度子数组和它们的和为:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

示例 2:
输入:arr = [1,2]
输出:3
解释:总共只有 2 个长度为奇数的子数组,[1] 和 [2]。它们的和为 3 。

示例 3:
输入:arr = [10,11,12]
输出:66

提示:
1 <= arr.length <= 100
1 <= arr[i] <= 1000文章来源地址https://www.toymoban.com/news/detail-695385.html

题解

下标 0 1 2 3 4 5
原数组 1 4 2 5 3
前缀和 0 1 5 7 12 15
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int[] s = new int[arr.length + 1];

        for (int i = 0; i < arr.length; i++) {
            s[i + 1] = s[i] + arr[i];
        }

        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int length = 1; i + length <= arr.length; length += 2) {
                int right = i + length ;
                int left = i;
                sum += s[right] - s[left];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] testArry = {1, 4, 2, 5, 3};
        System.out.println(solution.sumOddLengthSubarrays(testArry));

    }
}

到了这里,关于【力扣】1588. 所有奇数长度子数组的和 <前缀和>的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法萌新闯力扣】:找到所有数组中消失对数字

      这两天刚交了蓝桥杯的报名费,刷题的积极性高涨。算上打卡题,今天刷了10道算法题了,题目都比较简单,挑选了一道还不错的题目与大家分享。   把数组先排序,然后利用桶排来统计数组中存在的元素,对于数量为0的元素则存入list集合中,最后返回list集合   如果这

    2024年02月04日
    浏览(41)
  • c# 从零到精通 数据库 定义LINQ查询表达式,从数组中查找长度小于7的所有项

    c# 从零到精通 数据库 定义LINQ查询表达式,从数组中查找长度小于7的所有项 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace LINQQuery { class Program { static void Main(string[] args) { //定义一个字符串数组 string[] strName = new string[] { “明日科技”,“C#编程词典”

    2024年02月10日
    浏览(46)
  • 子矩阵的和(二维前缀和)

    上一篇文章介绍了一维前缀和,也就是一个数组的前 n 项和,这篇文章来介绍一下什么是二维前缀和。 含义 一维的是前 n 项的和,那么二维的情况下,表示的则是与左上角形成的矩形和。 怎么求 一维的递推关系式是 s[i] = s[i - 1] + a[i]; ,我们根据含义来思考二维的递推关系

    2024年02月08日
    浏览(40)
  • 796. 子矩阵的和(二维前缀和)

    796. 子矩阵的和 - AcWing题库   1.暴力搜索(搜索时间复杂度为O(n2),很多时候会超时) 2. 前缀和(左上角(二维)前缀和):本题特殊在不是直接求前n个数的和,而是求矩阵中某个元素左上角所以数的和(包括该元素自己),利用左上角前缀和的运算求子矩阵和。 3.在求左上

    2024年02月06日
    浏览(36)
  • C++ 二维前缀和 子矩阵的和

    输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2 ,表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n,m,q 。 接下来 n 行,每行包含 m 个整数,表示整数矩阵。 接下来

    2024年02月21日
    浏览(50)
  • 利用前缀和计算二维矩阵子矩阵的和

    作者简介 :一名后端开发人员,每天分享后端开发以及人工智能相关技术,行业前沿信息,面试宝典。 座右铭 :未来是不可确定的,慢慢来是最快的。 个人主页 :极客李华-CSDN博客 合作方式 :私聊+ 这个专栏内容 :用最低价格鼓励和博主一起在寒假打卡高频大厂算法题,

    2024年04月17日
    浏览(45)
  • 二维前缀和公式 AcWing 796. 子矩阵的和

    记住两个公式就行 不知道算难还是算简单,公式就是代码里面写的那样,完完全全公式,没有任何其他东西

    2024年02月19日
    浏览(42)
  • 二维矩阵的前缀和+子矩阵的和-java

    二维矩阵的前缀和,我们可以通过求前缀和来把求二维矩阵的求某一块的和,从时间复杂度O(n^2)变成O(1)常数级,大大降低了时间复杂度 文章目录 前言 一、二维矩阵的前缀和应该怎么做? 1.引入一个二维数组 2.二维前缀和矩阵数组 3.推出二维矩阵前缀和的公式计算 3.1 代码如

    2024年03月27日
    浏览(100)
  • 前缀和例题:子矩阵的和AcWing796-Java版

    //前缀和模板提,在读入数据的时候就可以先算好前缀和的大小 // 计算前缀的时候用 :g[i][j] = g[i][j-1] + g[i-1][j] - g[i-1][j-1] + Integer.parseInt(init[j-1]); // 计算结果的时候用 :g[x2][y2] - g[x1 - 1][y2]- g[x2][y1-1]   + g[x1 -1][y1 - 1] + \\\"n\\\" //一些重复加的地方都需要减掉,如计算前缀和的时候 g[i-1

    2024年02月02日
    浏览(41)
  • 【算法】编写一个函数,返回两个正数的和,有可能超过ulong长度

    编写一个函数,返回两个数字的和。输入数字是字符串,函数必须返回一个字符串。 示例: 添加(“123”,“321”);-“444” 添加(“11”,“99”);-“110” 备注: 输入的数字很大,有可能超过ulong长度。 输入是一个只有数字的字符串。 数字是正数。     算法实现:

    2024年02月14日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包