Easy

题目描述

有一圆环，上面有红色和蓝色的瓷砖。给你一个整数数组 colors，其中 colors[i] 表示第 i 块瓷砖的颜色：

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

环中每 3 个连续的瓷砖中，如果是交替颜色（即中间的瓷砖颜色与其左右两边的瓷砖颜色都不同），则称其为一个 交替组。

请你返回交替组的数目。

注意，由于是一个环，第一个和最后一个瓷砖也是相邻的。

示例 1：

输入：colors = [1,1,1]
输出：0
解释：没有交替组。

示例 2：

输入：colors = [0,1,0,0,1]
输出：3
解释：交替组为：[0,1,0]、[1,0,0]、[0,0,1]。

提示：

  • 3 <= colors.length <= 100
  • 0 <= colors[i] <= 1

解题思路

解题思路

这道题要求找出圆环中交替颜色的组数。关键在于理解什么是"交替组"：连续的 3 个瓷砖中，中间的瓷砖颜色与左右两边都不同。

主要思路：

  1. 遍历每个位置：对于每个位置 i，检查以它为中心的 3 个瓷砖是否构成交替组
  2. 处理环形结构：由于是圆环，需要用取模运算处理边界情况
  3. 交替条件判断：对于位置 i，需要检查 colors[i] 是否与 colors[i-1] 和 colors[i+1] 都不同

具体实现：

  • 遍历每个位置 i（从 0 到 n-1）
  • 计算前一个位置：(i-1+n) % n
  • 计算后一个位置：(i+1) % n
  • 检查当前位置的颜色是否与前后位置都不同
  • 如果满足条件，计数器加 1

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，非常高效。

代码实现

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors) {
        int n = colors.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int prev = (i - 1 + n) % n;
            int next = (i + 1) % n;
            
            if (colors[i] != colors[prev] && colors[i] != colors[next]) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        n = len(colors)
        count = 0
        
        for i in range(n):
            prev = (i - 1 + n) % n
            next = (i + 1) % n
            
            if colors[i] != colors[prev] and colors[i] != colors[next]:
                count += 1
        
        return count

public class Solution {
    public int NumberOfAlternatingGroups(int[] colors) {
        int n = colors.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int prev = (i - 1 + n) % n;
            int next = (i + 1) % n;
            
            if (colors[i] != colors[prev] && colors[i] != colors[next]) {
                count++;
            }
        }
        
        return count;
    }
}

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

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个数组一次，每次操作为常数时间
空间复杂度O(1)只使用了常数个额外变量