leetcode 3208. 交替组 II 中等

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

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

环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。

注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

示例 1：

输入：colors = [0,1,0,1,0], k = 3

输出：3

解释：

交替组包括：

示例 2：

输入：colors = [0,1,0,0,1,0,1], k = 6

输出：2

解释：

交替组包括：

示例 3：

输入：colors = [1,1,0,1], k = 4

输出：0

解释：

提示：

• 3 <= colors.length <= 10^5
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

分析：这道题和3206题的区别是，K值从3变成了区间[3,colors.length]，以及colors.length增加到10的5次方。但是基本思路是一致的，枚举每个位置i，从i开始往后长度为k的0, 1串是否是0，1交替的。注意当出现某一个位置连续出现了00（11同理）时，需要把下一次枚举的i移动到第二个0的位置。

int numberOfAlternatingGroups(int* colors, int colorsSize, int k) {
    int dup[colorsSize*2+5];
    memset(dup,0,sizeof(int));
    for(int i=0;i<colorsSize;++i)//因为整个形状为环形，所以我将整个数组变为2倍长度
        dup[i]=dup[i+colorsSize]=colors[i];
    int ans=0,t=0;
    for(int i=0;i<colorsSize;++i)
    {
        if(!t)//如果上一次的结果不是一个交替01串，那么本次需要检查当前位置长度为k是否符合要求
        {
            int temp=dup[i],f=1,index=i;
            for(int j=i+1;j<i+k;++j)
            {
                if(dup[j]!=temp)temp=dup[j];
                else
                {
                    f=0;index=j;break;
                }
            }
            if(f)ans++,t=1;
            else i=index-1,t=0;
        }
        else//上一次是一个交替01串，只需要判断下一位是否满足要求
        {
            if(dup[i+k-1]!=dup[i+k-2])ans++,t=1;
            else t=0,i--;
            
        }
    }

    return ans;
}