【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)

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

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

分析

  • 这道算法题的题意应该不难理解,暴力O(n3)的解法应该都能想到。
  • 有人会想到用滑动窗口或者前缀和,这些是常用的优化手段。
  • 根据题意我们知道子数组就像子序列,是否出现在子数组中,和数字具体是多少无关,只和位置有关。
  • 既然和具体数字无关,这种子序列,子数组,排列组合,就一定有规律,可以用数学的方式去解决。
  • 我们可以一头到尾遍历一遍,然后累加 每个数字的值乘以每个数字出现在子数组的次数 就可以得到结果。接下来就变成我们是否可以找到每个数字出现在子数组中的次数规律。
  • 假设我们选定一个数字,那么除了这个数字之外,我们还可以另外选择 偶数个其他数字 凑成奇数长度的子数组。
  • 我们可以把其他数字的选择,分成左面和右面两部分,那么这个选定的数字出现在子数组的次数就是 左面可选数字方案数 * 右面数字可选方案数
  • 奇数=1 + 偶数,选定一个数字之后,如果左面选择奇数个数字,那么右面也必须选择奇数个数字;如果左面选择偶数个数字,那么右面也要选择偶数个数字。这样加上选定的数字,就刚好是奇数长度子数组。
  • 最终每个数字出现的次数就是 左面选择奇数个数字的方案数 右面选择奇数个数字的方案数 + 左面选择偶数个数字的方案数 右面选择偶数个数字的方案数
  • 从0到n中,奇数的数量是(n + 1) / 2个,偶数的数量是n / 2 + 1(0也算偶数个)。

题解

java

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int ans = 0;

        int endIndex = arr.length - 1;
        for (int i = 0; i <= endIndex; ++i) {
            int leftCount  = i;
            int rightCount = endIndex - i;
            int leftOdd    = (leftCount + 1) / 2;
            int rightOdd   = (rightCount + 1) / 2;
            int leftEven   = leftCount / 2 + 1;
            int rightEven  = rightCount / 2 + 1;
            ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
        }

        return ans;
    }
}

c

int sumOddLengthSubarrays(int* arr, int arrSize){
    int ans = 0;

    int endIndex = arrSize - 1;
    for (int i = 0; i <= endIndex; i++) {
        int leftCount = i;
        int rightCount = endIndex - i;
        int leftOdd = (leftCount + 1) / 2;
        int rightOdd = (rightCount + 1) / 2;
        int leftEven = leftCount / 2 + 1;
        int rightEven = rightCount / 2 + 1;
        ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
    }

    return ans;
}

c++

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int ans = 0;

        int endIndex = arr.size() - 1;
        for (int i = 0; i <= endIndex; i++) {
            int leftCount = i;
            int rightCount = endIndex - i;
            int leftOdd = (leftCount + 1) / 2;
            int rightOdd = (rightCount + 1) / 2;
            int leftEven = leftCount / 2 + 1;
            int rightEven = rightCount / 2 + 1;
            ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
        }

        return ans;
    }
};

python

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ans = 0
        endIndex = len(arr) - 1
        for i, v in enumerate(arr):
            leftCount, rightCount = i, endIndex - i
            leftOdd = (leftCount + 1) // 2
            rightOdd = (rightCount + 1) // 2
            leftEven = leftCount // 2 + 1
            rightEven = rightCount // 2 + 1
            ans += v * (leftOdd * rightOdd + leftEven * rightEven)
        return ans
        

go

func sumOddLengthSubarrays(arr []int) (ans int) {
    endIndex := len(arr) - 1
    for i, v := range arr {
        leftCount, rightCount := i, endIndex-i
        leftOdd := (leftCount + 1) / 2
        rightOdd := (rightCount + 1) / 2
        leftEven := leftCount/2 + 1
        rightEven := rightCount/2 + 1
        ans += v * (leftOdd*rightOdd + leftEven*rightEven)
    }
    return ans
}

rust

impl Solution {
    pub fn sum_odd_length_subarrays(arr: Vec<i32>) -> i32 {
        let endIndex = arr.len() - 1;
        arr.iter().enumerate().map(|(i, v)| {
            let leftCount = i;
            let rightCount = endIndex - i;
            let leftOdd = (leftCount + 1) / 2;
            let rightOdd = (rightCount + 1) / 2;
            let leftEven = leftCount / 2 + 1;
            let rightEven = rightCount / 2 + 1;
            arr[i] * ((leftOdd * rightOdd + leftEven * rightEven) as i32)
        }).sum()
    }
}

在这里插入图片描述


原题传送门:https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~

相关文章
|
8天前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于D*算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于D*算法的机器人路径规划(Python代码实现)
|
8天前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于改进型A*算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于改进型A*算法的机器人路径规划(Python代码实现)
|
8天前
|
机器学习/深度学习 编解码 算法
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
|
8天前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于A*算法的机器人路径规划研究(Python代码实现)
【机器人路径规划】基于A*算法的机器人路径规划研究(Python代码实现)
|
8天前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
|
8天前
|
算法 机器人 定位技术
【机器人路径规划】基于流场寻路算法(Flow Field Pathfinding)的机器人路径规划(Python代码实现)
【机器人路径规划】基于流场寻路算法(Flow Field Pathfinding)的机器人路径规划(Python代码实现)
机器学习/深度学习 算法 自动驾驶
100 0
|
16天前
|
算法 定位技术 调度
基于蚂蚁优化算法的柔性车间调度研究(Python代码实现)
基于蚂蚁优化算法的柔性车间调度研究(Python代码实现)
|
16天前
|
机器学习/深度学习 算法 PyTorch
【DQN实现避障控制】使用Pytorch框架搭建神经网络,基于DQN算法、优先级采样的DQN算法、DQN + 人工势场实现避障控制研究(Matlab、Python实现)
【DQN实现避障控制】使用Pytorch框架搭建神经网络,基于DQN算法、优先级采样的DQN算法、DQN + 人工势场实现避障控制研究(Matlab、Python实现)
|
23天前
|
机器学习/深度学习 资源调度 算法
一种多尺度协同变异的粒子群优化算法(Python代码实现)
一种多尺度协同变异的粒子群优化算法(Python代码实现)

热门文章

最新文章

推荐镜像

更多