每日一题 ———————— 交替子数组计数

题目介绍：

         本题来自力扣，给你一个二进制数组nums 。如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。返回数组 nums 中交替子数组的数量。

示例 1：

输入： nums = [0,1,1,1]

输出： 5

解释：

以下子数组是交替子数组：[0] 、[1] 、[1] 、[1] 以及 [0,1] 。

示例 2：

输入： nums = [1,0,1,0]

输出： 10

解释：

数组的每个子数组都是交替子数组。可以统计在内的子数组共有 10 个。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1 。

题目分析：
        

本题主要有两点要注意：1、本题要求为求交替子数组，因此要注意特殊情况单个

                                         2、本题要求子数组中不得包含两个相邻的相同元素

由此，我们可以建立一个 dp数组  保存以每一个元素为头最大的子数组个数，用sum来保存总数， 然后利用一个 for循环 从头遍历数组，再用一个 while循环 + if判断语句 判断以当前元素为头符合要求的交替子数组，

但是这就引出一个问题，出现了许多重复判断的区域，这浪费许多时间。以 [1,0,1,0]为例子，最后两位就被重复判断了。

所以我们从后面开始判断，以最后一位为头的就交替子数组只能唯一，然后加给sum. 而后往前移一位，有应为以最后一位为头的就交替子数组已经被计算，也就是说如果符合要求的话，其子数组数目只能为后一位 dp[i] =  dp[i+1] + 1,  而如果不符合要求的话 dp[i] = 1;

于是我们可以将while循环优化掉，只剩下for循环以及一个判断语句

代码实现：

long long countAlternatingSubarrays(int* nums, int numsSize) {int dp[numsSize]; //建立dp数组保存子数组数目memset(dp,0,numsSize);  // 数组初始化long long int sum = 1;dp[numsSize-1] = 1;    // 最后一位dp初始化for(int i = numsSize-2;i >= 0;i--){dp[i] = 1; //每一位元素最少有一个符合要求的子数组，即自身if(nums[i] != nums[i+1]){dp[i] = fmax(dp[i],dp[i+1]+1);}sum +=dp[i];}return sum;}