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;
}
}