如何使用qq空间做推广网站,收录快的网站,wordpress 微信导航,网站建设流程资讯Every day a Leetcode
题目来源#xff1a;3208. 交替组 II
解法1#xff1a;环形数组
把数组复制一份拼接起来#xff0c;和 3101 题一样#xff0c;遍历数组的同时#xff0c;维护以 i 为右端点的交替子数组的长度 cnt。
如果 i ≥ n 且 cnt ≥ k#xff0c;那么 i…Every day a Leetcode
题目来源3208. 交替组 II
解法1环形数组
把数组复制一份拼接起来和 3101 题一样遍历数组的同时维护以 i 为右端点的交替子数组的长度 cnt。
如果 i ≥ n 且 cnt ≥ k那么 i 就是一个长为 k 的交替子数组的右端点答案加一。注意这里要判断 i ≥ n从而避免重复统计。
代码实现时不需要复制数组而是用 i mod n 的方式取到对应的值。
代码
/** lc appleetcode.cn id3208 langcpp** [3208] 交替组 II*/// lc codestart
class Solution
{
public:int numberOfAlternatingGroups(vectorint colors, int k){int n colors.size();int ans 0, cnt 0;for (int i 0; i n * 2; i){if (i 0 colors[i % n] colors[(i - 1) % n]){cnt 0;}cnt;ans i n cnt k;}return ans;}
};
// lc codeend结果 复杂度分析
时间复杂度O(n)其中 n 是数组 colors 的长度。
空间复杂度O(1)。
