帝国cms调用网站地址,上海网页设计经验培训,微信自动加好友软件,如何做网站广告【问题描述】5457. 和为奇数的子数组数目[中等] 【解答思路】
1. 动态规划
第 1 步#xff1a;设计状态 dp[i][0] 记录以arr[i]结尾的和为奇数数量 dp[i][1] 记录以arr[i]结尾的和为偶数数量 第 2 步#xff1a;状态转移方程
for(int i1;in;i){if(arr[i]%20){dp[i][0]…【问题描述】5457. 和为奇数的子数组数目[中等] 【解答思路】
1. 动态规划
第 1 步设计状态 dp[i][0] 记录以arr[i]结尾的和为奇数数量 dp[i][1] 记录以arr[i]结尾的和为偶数数量 第 2 步状态转移方程
for(int i1;in;i){if(arr[i]%20){dp[i][0]dp[i-1][0];dp[i][1]dp[i-1][1]1;}else{dp[i][0]dp[i-1][1]1;dp[i][1]dp[i-1][0];}}
第 3 步考虑初始化
if(arr[0]%21){dp[0][0]1;}else{dp[0][1]1;}
第 4 步考虑输出 遍历dp[i][0]相加 for(int[] k:dp){res(resk[0])%base;}return res;
时间复杂度O(N^2) 空间复杂度O(1) static int base1000000007;public int numOfSubarrays(int[] arr) {int narr.length;int res0;int[][] dpnew int[n][2];if(arr[0]%21){dp[0][0]1;}else{dp[0][1]1;}for(int i1;in;i){if(arr[i]%20){dp[i][0]dp[i-1][0];dp[i][1]dp[i-1][1]1;}else{dp[i][0]dp[i-1][1]1;dp[i][1]dp[i-1][0];}}for(int[] k:dp){res(resk[0])%base;}return res;}
2. 前缀和和动态规划类似
如果当前的和为1那么找到前缀和为0的在这一段中和就为奇数 因为前缀和为0的变成前缀和为1的加上当前的数肯定是一个奇数 同理如果当前的和为0那么找到前缀和为1的在这一段中和就为奇数 我们只需要统计前缀和为0和1的个数即可 时间复杂度O(N) 空间复杂度O(1)
class Solution {public int numOfSubarrays(int[] arr) {int[] cnts new int[2];int cur 0;int ans 0;cnts[0] 1;int mod 1000000007;for(int x : arr){//查看当前的前缀和cur (cur x) % 2;//结果加上前缀和相反的个数ans cnts[1 - cur];//前缀和为cur的个数cnts[cur];ans % mod;}return ans % mod;}
}
【总结】
1. 动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
2.前缀和 想清楚状态转移
3. 一开始思路 遍历子序列 后发现有重复和 瞎搞了一个多小时 原来有更好的方法 不打周赛都不知道自己有多菜
转载链接https://leetcode-cn.com/problems/number-of-sub-arrays-with-odd-sum/solution/dong-tai-gui-hua-by-zhan-zai-yue-guang-xia-3/ 转载链接https://leetcode-cn.com/problems/number-of-good-ways-to-split-a-string/solution/javaer-fen-by-dui-fang-zheng-zai-jiang-hua-2/
