Medium

题目描述

有一个由红色和蓝色瓷砖组成的圆圈。给你一个整数数组 colors 和一个整数 k。瓷砖 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

解题思路

这道题要求在环形数组中找到长度为 k 的交替颜色序列的数量。

核心思路： 我们需要统计所有长度为 k 的连续子序列中，颜色完全交替的序列数量。由于是环形数组，需要考虑数组末尾与开头的连接。

解法分析：

  1. 滑动窗口法（推荐）：

    • 将数组扩展一倍来处理环形特性，或者使用模运算
    • 对每个位置，检查从该位置开始长度为 k 的序列是否为交替序列
    • 交替序列的判断：相邻元素必须不相等

  2. 优化的连续计数法：

    • 先找到所有连续的交替段
    • 对于每个长度 ≥ k 的交替段，计算其中包含的长度为 k 的子序列数量

实现细节：

  • 由于是环形数组，我们需要处理 n + k - 1 个位置（其中 n 是数组长度）
  • 使用模运算 i % n 来访问环形数组中的元素
  • 对每个起始位置，检查连续 k-1 个相邻对是否都满足颜色不同的条件

时间复杂度为 O(n*k)，但可以通过预处理优化到 O(n)。

代码实现

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k) {
        int n = colors.size();
        int count = 0;
        
        // 检查每个可能的起始位置
        for (int i = 0; i < n; i++) {
            bool isAlternating = true;
            
            // 检查从位置i开始的k个连续元素是否交替
            for (int j = 0; j < k - 1; j++) {
                int curr = colors[(i + j) % n];
                int next = colors[(i + j + 1) % n];
                if (curr == next) {
                    isAlternating = false;
                    break;
                }
            }
            
            if (isAlternating) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        count = 0
        
        # 检查每个可能的起始位置
        for i in range(n):
            is_alternating = True
            
            # 检查从位置i开始的k个连续元素是否交替
            for j in range(k - 1):
                curr = colors[(i + j) % n]
                next_color = colors[(i + j + 1) % n]
                if curr == next_color:
                    is_alternating = False
                    break
            
            if is_alternating:
                count += 1
        
        return count

public class Solution {
    public int NumberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.Length;
        int count = 0;
        
        // 检查每个可能的起始位置
        for (int i = 0; i < n; i++) {
            bool isAlternating = true;
            
            // 检查从位置i开始的k个连续元素是否交替
            for (int j = 0; j < k - 1; j++) {
                int curr = colors[(i + j) % n];
                int next = colors[(i + j + 1) % n];
                if (curr == next) {
                    isAlternating = false;
                    break;
                }
            }
            
            if (isAlternating) {
                count++;
            }
        }
        
        return count;
    }
}

var numberOfAlternatingGroups = function(colors, k) {
    const n = colors.length;
    let count = 0;
    let currentLength = 1;
    
    for (let i = 1; i < n + k - 1; i++) {
        const prev = colors[(i - 1) % n];
        const curr = colors[i % n];
        
        if (prev !== curr) {
            currentLength++;
        } else {
            currentLength = 1;
        }
        
        if (currentLength >= k) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × k)需要检查 n 个起始位置，每个位置检查 k-1 对相邻元素
空间复杂度O(1)只使用常数额外空间