登录
[Python3/Java/C++/Go/TypeScript] 一题一解：一次遍历（清晰题解）
2024年11月26日 09:14
方法一：一次遍历
我们令 $k = 3$，表示交替组的长度为 $3$。
为了方便处理，我们可以将环展开成一个长度为 $2n$ 的数组，然后从左到右遍历这个数组，用一个变量 $\textit{cnt}$ 记录当前交替组的长度，如果遇到了相同的颜色，就将 $\textit{cnt}$ 重置为 $1$，否则将 $\textit{cnt}$ 加一。如果 $\textit{cnt} \ge k$，并且当前位置 $i$ 大于等于 $n$，那么就找到了一个交替组，答案加一。
遍历结束后，返回答案即可。
###python
class Solution:
def numberOfAlternatingGroups(self, colors: List[int]) -> int:
k = 3
n = len(colors)
ans = cnt = 0
for i in range(n << 1):
if i and colors[i % n] == colors[(i - 1) % n]:
cnt = 1
else:
cnt += 1
ans += i >= n and cnt >= k
return ans
###java
class Solution {
public int numberOfAlternatingGroups(int[] colors) {
int k = 3;
int n = colors.length;
int ans = 0, cnt = 0;
for (int i = 0; i < n << 1; ++i) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 1;
} else {
++cnt;
}
ans += i >= n && cnt >= k ? 1 : 0;
}
return ans;
}
}
###cpp
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors) {
int k = 3;
int n = colors.size();
int ans = 0, cnt = 0;
for (int i = 0; i < n << 1; ++i) {
if (i && colors[i % n] == colors[(i - 1) % n]) {
cnt = 1;
} else {
++cnt;
}
ans += i >= n && cnt >= k ? 1 : 0;
}
return ans;
}
};
###go
func numberOfAlternatingGroups(colors []int) (ans int) {
k := 3
n := len(colors)
cnt := 0
for i := 0; i < n<<1; i++ {
if i > 0 && colors[i%n] == colors[(i-1)%n] {
cnt = 1
} else {
cnt++
}
if i >= n && cnt >= k {
ans++
}
}
return
}
###ts
function numberOfAlternatingGroups(colors: number[]): number {
const k = 3;
const n = colors.length;
let [ans, cnt] = [0, 0];
for (let i = 0; i < n << 1; ++i) {
if (i && colors[i % n] === colors[(i - 1) % n]) {
cnt = 1;
} else {
++cnt;
}
ans += i >= n && cnt >= k ? 1 : 0;
}
return ans;
}
时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{colors}$ 的长度。空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
