交替子数组计数 - 力扣题解

我会带着你远行 2024-04-20 07:39 41阅读 0赞

⭐**简单说两句**⭐

> **✨ 正在努力的小新~**  
> **? 超级爱分享，分享各种有趣干货！**  
> **?? 提供：模拟面试 | 简历诊断 | 独家简历模板**  
> **? 感谢关注，关注了你就是我的超级粉丝啦！**  
> **? 以下内容仅对你可见~**
> 
> **作者：****后端小知识**，**CSDN后端领域新星创作者 |阿里云专家博主**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

## 交替子数组计数 - 力扣题解 ##

![056dd17dd0506591d04525f015765ab749e9f9f19dcaf6e0dcae5d77057d2392-15@3x][056dd17dd0506591d04525f015765ab749e9f9f19dcaf6e0dcae5d77057d2392-15_3x]

### 前言 ###

亲爱的朋友们，好久不见，十分想念

今天参加力扣周赛，做了三个题（自己还是太菜了???）

![image-20240331162043883][]

下面我给各位友友们来分享一下周赛的第三题吧，前面两题太简单了，就不分享了哈

### 题解 ###

题目：**交替子数组计数**

链接：[**交替子数组计数**][Link 2]

![image-20240331163734165][]

贴心吧，链接和图给安排上了?

**思路：**

题目的意思很明朗，就看怎么做了

如果我们采用直接暴力循环（一个一个模拟子数组）去做的话肯定是会TLE的

那正确的做法是什么呢?

![image-20240331165123396][]

答案就是**动态规划**

这个方程式还是比较好推演的，很简单，大家看一眼就懂了

**我们定义dp\[i\]：以nums\[i\] 结尾的交替子数组个数**

**初始化dp\[0\]=1,只有一个时，个数肯定是1**

**如果相邻的两个数不相等的话：dp\[i\]=dp\[i-1\]+1;**

**如果相邻的两个数相等的话：dp\[i\]=1;**

最后求和一下就是总的个数了，是不是超级简单吖

下面就是代码展示啦

> AC代码清单

class Solution {
        
    public:
        int dp[100010];
        long long countAlternatingSubarrays(vector<int>& nums) {
        
            dp[0]=1;
            for(int i=1;i<nums.size();i++){
        
                if(nums[i]!=nums[i-1]){
        
                    dp[i]=dp[i-1]+1;
                }else{
        
                    dp[i]=1;
                }
            }
            long long ans=0;
            for(auto x:dp) ans+=x;
            return ans;
        }
    };

【都看到这了，点点赞点点关注呗，爱你们】??

![后端小知识关注引导][aae32671d2d4d8713d763ecddb51fee9.gif]

![image-20240330155339598][]

**✨ 正在努力的小新~**  
**? 超级爱分享，分享各种有趣干货！**  
**?? 提供：模拟面试 | 简历诊断 | 独家简历模板**  
**? 感谢关注，关注了你就是我的超级粉丝啦！**  
**? 以下内容仅对你可见~**

**作者：****后端小知识**，**CSDN后端领域新星创作者 | 阿里云专家博主**

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[056dd17dd0506591d04525f015765ab749e9f9f19dcaf6e0dcae5d77057d2392-15_3x]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/39003eb1c9944fce9c6182535b802a70.png
[image-20240331162043883]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c05f30bcd35b4dc7a513c27cd8414355.png
[Link 2]: https://leetcode.cn/problems/count-alternating-subarrays/description/
[image-20240331163734165]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b2ba944d857b4fd3b027d00ca2d1f619.png
[image-20240331165123396]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/89853fd6dd7b4a38b231a943db09862e.png
[aae32671d2d4d8713d763ecddb51fee9.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c08ce342da434e4f80c3d3dd7f6855ba.gif
[image-20240330155339598]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/94257151cf9e44c7b3bd892cd7e13b04.png