【LeetCode:3101. 交替子数组计数 + 滑动窗口 + 数学公式】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述
在这里插入图片描述

🚩 题目链接

⛲ 题目描述

给你一个二进制数组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. 在去寻找有多少个相同元素不同的过程中,我们通过一个变量来记录形如 01 或者 10 的个数有多少个。为什么呢?大家可以多举一些情况,注意,此时不考虑单独的情况, 这种情况我们直接累加到最后的结果即可。假设形如 01 ,此时贡献为1;形如010,贡献为3;形如0101,贡献为6,形如01010,贡献为10,依次类推,得到每次贡献的数值公式为 cnt * (cnt + 1) / 2。
  3. 最后,加上每一个字符的情况,也就是字符串的长度,直接返回即可。
  4. 有了基本的思路,接下来我们就来通过代码来实现一下递归和迭代的解法。
🥦 实现代码
class Solution {
    public long countAlternatingSubarrays(int[] nums) {
        long ans = 0;
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            int ori = nums[right];
            long cnt = 0;
            while (right < n - 1 && ori != nums[right + 1]) {
                cnt++;
                ori = nums[right + 1];
                right++;
            }
            ans += cnt * (cnt + 1) / 2;
            left = right;
        }
        return ans + n;
    }
}
🥦 运行结果

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-11 01:56:04       3 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-11 01:56:04       3 阅读
  3. 在Django里面运行非项目文件

    2024-07-11 01:56:04       2 阅读
  4. Python语言-面向对象

    2024-07-11 01:56:04       2 阅读

热门阅读

  1. 【Zoom安全解析】深入Zoom的端到端加密机制

    2024-07-11 01:56:04       9 阅读
  2. Qt QSettings 使用详解:跨平台的配置管理

    2024-07-11 01:56:04       9 阅读
  3. Docker Dockerfile:构建与优化

    2024-07-11 01:56:04       9 阅读
  4. 面试题07-09

    2024-07-11 01:56:04       10 阅读
  5. docker里日志分割的方法

    2024-07-11 01:56:04       9 阅读
  6. C#面:解释startup class的configure方法有什么作用?

    2024-07-11 01:56:04       10 阅读
  7. 甲方安全员应该持有什么心态

    2024-07-11 01:56:04       11 阅读
  8. Memcached介绍和详解

    2024-07-11 01:56:04       11 阅读
  9. python xlsx 导出表格超链接

    2024-07-11 01:56:04       9 阅读
  10. qt 子线程更新ui举例

    2024-07-11 01:56:04       8 阅读
  11. python——解决字节转义的问题

    2024-07-11 01:56:04       9 阅读