1588. 所有奇数长度子数组的和

2021-08-29  本文已影响0人  漫行者_

1588. 所有奇数长度子数组的和

这题目一开始读错,子序列理解成子数组
贴个代码吧。dfs。

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        List<Integer> result = new ArrayList<>();
        dfs(result, arr, 0, 0, 0);
        int sum = 0;
        for(int i=0; i<result.size(); i++) {
            sum += result.get(i);
        }
        return sum;
    }

    public void dfs(List<Integer> result, int[] arr, int count, int depth, int sum) {
        if(count%2 == 1) {
            result.add(sum);
        }
        if(depth == arr.length) {
            return;
        }
        dfs(result, arr, count,depth+1, sum);
        dfs(result, arr, count+1,depth+1, sum+arr[depth]);       
    }
}

如果子序列的话:
贴一个别人写的解释:
https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/solution/cong-on3-dao-on-de-jie-fa-by-liuyubobobo/
根据最后的来写的代码:

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;
        for(int i=0; i<arr.length; i++) {
            int left = i; 
            int right = arr.length - i - 1;
            int left_odd = (left+1)/2;//左边奇数的个数
            int right_odd = (right+1)/2;
            int left_idd = left/2 + 1;//左边偶数的个数,要注意加一个
            int right_idd = right/2 + 1;
            sum += (left_odd*right_odd + left_idd*right_idd)*arr[i];
        }
        return sum;
    }
}
上一篇下一篇

猜你喜欢

热点阅读