題目資訊

• 題目編號: 3208
• 題目連結: Alternating Groups II
• 主題: Array, Sliding Window

題目敘述

有一個由紅色和藍色瓷磚組成的圓圈。給定一個整數數組 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 \leq \text{colors.length} \leq 10^5$
• $0 \leq \text{colors}[i] \leq 1$
• $3 \leq k \leq \text{colors.length}$

直覺

問題要求我們在一個圓形的排列中找到所有可能的交替色塊組。一個交替組由連續的色塊構成，從指定的色塊開始，每個色塊的顏色交替。由於色塊形成一個圓，我們需要考慮可能從數組末端繞到數組起始的組。

為了解決這個問題，想法是追蹤交替顏色的序列，通過掃描數組，將其視作一個圓。這涉及評估相鄰色塊的顏色並計算有多少這樣的序列達到或超過給定的長度 $k$。

主要的障礙是如何有效地維護圓形的屬性，這可以通過虛擬擴展數組，使用模運算來模擬繞圈效果來實現。

解法

此方法涉及以視數組為圓形的方式遍歷色塊。通過迭代 colors.length + k - 2 次來達成。額外的 $k - 2$ 次迭代確保所有可能的組，包括那些繞圈的組，都被考慮到了。

1. 初始化:

   • 將 colorsLength 設置為輸入顏色數組的長度。
   • currentLength 初始化為 1，這用於追蹤當前正在評估的交替序列的長度。
   • result 初始化為 0，這用於存儲有效的交替組的數量。

2. 迭代:

   • 循環從 0 執行到 colorsLength + k - 2，以確保我們檢查所有可能的起始位置，甚至是那些靠近末端可能繞到起始的。
   • 對於每次迭代的索引 i，我們比較當前索引的顏色與下一個顏色（使用模運算來考慮圓形性質）：
     • 如果顏色相同，交替序列被打斷，currentLength 重置為 1。
     • 如果不同，則視為序列的延續，並增長 currentLength。
   • 如果 currentLength 達到 $k$，這表明有一個有效的交替組，因此增加 result。

3. 返回:

   • 最後返回 result，這代表至少長度為 $k$ 的交替組的總數。

這個方法確保每個色塊和每個潛在的起始點被檢查恰好一次，使算法具有時間複雜度 $O(n)$，其中 $n$ 是色塊的數量。該方法通過模運算有效地處理了圓形屬性，而不需要修改初始數組。

程式碼

C++

class Solution {
public:
    int numberOfAlternatingGroups(vector<int>& colors, int k) {
        int colorsLength = colors.size();
        int currentLength = 1; // 當前交替序列的長度
        int result = 0; // 交替群組的計數

        // 遍歷圓形結構
        for (int i = 0; i < colorsLength + k - 2; i++) {
            // 比較當前瓷磚與圓形數組中的下一個瓷磚
            if (colors[i % colorsLength] == colors[(i + 1) % colorsLength]) {
                // 序列中斷，重置長度
                currentLength = 1;
            } else {
                // 擴展當前序列
                currentLength++;
            }

            // 若當前交替序列的長度至少為 k
            if (currentLength >= k) {
                result++;
            }
        }

        return result; // 返回交替群組的總數
    }
};

Python

class Solution:
    def numberOfAlternatingGroups(self, colors, k):
        colorsLength = len(colors)
        currentLength = 1  # 當前交替序列的長度
        result = 0  # 交替群組的計數

        # 遍歷圓形結構
        for i in range(colorsLength + k - 2):
            # 將當前的瓷磚與圓形陣列中的下一個進行比較
            if colors[i % colorsLength] == colors[(i + 1) % colorsLength]:
                # 序列中斷，重設長度
                currentLength = 1
            else:
                # 延伸當前序列
                currentLength += 1

            # 如果當前交替序列的長度至少為 k
            if currentLength >= k:
                result += 1

        return result  # 返回交替群組的總計數

複雜度分析

• 時間複雜度: $O(n + k)$，其中 $n$ 為 colors 陣列的長度。由於迴圈遍歷了 colorsLength + k - 2 個元素，因此實際的複雜度為 $O(n + k)$，當考慮 $n$ 為最大值時，簡化為主導因素的 $O(n)$。

• 空間複雜度: $O(1)$，這反映了使用固定量的額外空間（例如，一些整數變數），而不受輸入大小影響。該算法不需要與輸入大小成比例的額外空間，因此是恆定的空間複雜度。