2025-02-18：交替组Ⅱ。用go语言，给定一个整数数组 colors 和一个整数 k，数组 colors 由红色和蓝色瓷砖

福大大架构师每日一题

发布于 2025-02-19 12:49:36

8100

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-02-18：交替组Ⅱ。用go语言，给定一个整数数组 colors 和一个整数 k，数组 colors 由红色和蓝色瓷砖组成。数组中的元素表示瓷砖的颜色：

1.colors[i] == 0 表示第 i 块瓷砖为红色。

2.colors[i] == 1 表示第 i 块瓷砖为蓝色。

这组瓷砖形成一个环，意味着数组的首尾是相连的。若环中有 k 块连续的瓷砖颜色交替（即除了首尾两块外，任意中间的瓷砖颜色都与它两侧的颜色不同），则这 k 块瓷砖被称为一个交替组。

你的任务是计算并返回这样的交替组的数量。

3 <= colors.length <= 100000。

0 <= colors[i] <= 1。

3 <= k <= colors.length。

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

输出：2。

答案2025-02-18：

chatgpt[1]

题目来自leetcode3208。

大体步骤如下：

1.定义一个函数 numberOfAlternatingGroups(colors []int, k int)，接收一个整数数组 colors 和一个整数 k。

2.初始化变量 res 和 cnt 为0和1。

3.循环遍历数组 colors：

• 从下标 -k+2 开始，直到数组末尾。
• 检查当前瓷砖颜色和它前一块瓷砖颜色是否不同。

4.如果颜色不同，递增 cnt；否则，将 cnt 重置为1。

5.如果 cnt 大于等于 k，增加 res 的计数。

6.返回最终的 res 值。

总的时间复杂度为O(n)，其中n为数组colors的长度；

总的额外空间复杂度为O(1)，因为除了几个变量外，没有使用额外的空间。

Go完整代码如下：

package main

import"fmt"

func numberOfAlternatingGroups(colors []int, k int)int {
    n := len(colors)
    res, cnt := 0, 1
    for i := -k + 2; i < n; i++ {
        if colors[(i+n)%n] != colors[(i-1+n)%n] {
            cnt++
        } else {
            cnt = 1
        }
        if cnt >= k {
            res++
        }
    }
    return res
}

func main() {
    colors := []int{0, 1, 0, 0, 1, 0, 1}
    k := 6
    result := numberOfAlternatingGroups(colors, k)
    fmt.Println(result) // 输出 : 2
}

Rust完整代码如下：

fn number_of_alternating_groups(colors: Vec<i32>, k: i32) ->i32 {
    letn = colors.len();
    letmut res = 0;
    letmut cnt = 1;

    foriin -k + 2..n asi32 {
        if colors[(i + n asi32) asusize % n] != colors[(i - 1 + n asi32) asusize % n] {
            cnt += 1;
        } else {
            cnt = 1;
        }

        if cnt >= k {
            res += 1;
        }
    }

    return res;
}

fnmain() {
    letcolors = vec![0, 1, 0, 0, 1, 0, 1];
    letk = 6;
    letresult = number_of_alternating_groups(colors, k);
    println!("输出 : {}", result); // 输出 : 2
}

Python完整代码如下：

# -*-coding:utf-8-*-

defnumber_of_alternating_groups(colors, k):
    n = len(colors)
    res = 0
    cnt = 1
    
    for i inrange(-k + 2, n):
        if colors[(i + n) % n] != colors[(i - 1 + n) % n]:
            cnt += 1
        else:
            cnt = 1
            
        if cnt >= k:
            res += 1
            
    return res

if __name__ == '__main__':
    colors = [0, 1, 0, 0, 1, 0, 1]
    k = 6
    result = number_of_alternating_groups(colors, k)
    print(result)  # 输出: 2