【Leetcode 每日一题 - 扩展】3208. 交替组 II

问题背景

给你一个整数数组 $colors$ 和一个整数 $k$，$colors$ 表示一个由红色和蓝色瓷砖组成的环，第 $i$ 块瓷砖的颜色为 $colors[i]$：

• $colors[i]==0$ 表示第 $i$ 块瓷砖的颜色是 红色 。
• $colors[i]==1$ 表示第 $i$ 块瓷砖的颜色是 蓝色 。

环中连续 $k$块 瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。
请你返回 交替 组的数目。
注意 ，由于 $colors$ 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

数据约束

• $3\le colors.length\le 10^5$
• $0\le colors[i]\le 1$
• $3\le k\le colors.length$

解题过程

在 前置题 的基础上增加了长度限制和环状两个要求，因此在延续枚举潜在交替组右端点的前提下，针对性地将实现改为计算长度。要处理环状的问题，不必要扩展数组，用模运算来映射即可。

考虑到遍历的过程中相当于走了两遍原数组，原数组内部的交替子数组会被重复计算。而原数组内部的这些可能一定会在回到环初始位置时再次出现，所以仅当 $i\ge n$ 时统计结果就可以避免重复。

具体实现

class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int len = 0;
        for(int i = 0; i < 2 * n; i++) {
            if(i > 0 && colors[i % n] == colors[(i - 1) % n]) {
                len = 0;
            }
            len++;
            if(i >= n && len >= k) {
                res++;
            }
        }
        return res;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/144049236

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！