Leecode刷题C语言之交替组②

执行结果:通过

执行用时和内存消耗如下：

 

 

 

代码如下： 

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

解题思路： 

1. 初始化变量：
   • res 用于存储结果，即交替颜色组的数量。
   • cnt 用于记录当前考虑的连续交替颜色的长度。
2. 循环遍历：
   • 使用一个从 -k + 2 到 colorsSize - 1 的循环变量 i。这个范围的选择是为了确保能够检查每个可能的长度为 k 的子数组，同时避免数组越界。
   • 循环的起始值 -k + 2 是因为我们需要查看当前元素与其前面 k-1 个元素的关系，而由于数组是循环的（或者可以看作循环的），所以我们需要从稍微早于数组开始的位置开始考虑。
3. 处理循环数组：
   • 使用 (i + colorsSize) % colorsSize 和 (i - 1 + colorsSize) % colorsSize 来处理数组索引的循环。这确保了即使 i 是一个负数或超出了数组的实际长度，我们仍然可以正确地访问数组元素。
4. 交替颜色计数：
   • 对于每个 i，比较 colors[(i + colorsSize) % colorsSize] 和 colors[(i - 1 + colorsSize) % colorsSize]。
   • 如果这两个颜色不相同，说明当前元素延续了交替颜色序列，因此 cnt 增加 1。
   • 如果这两个颜色相同，说明交替颜色序列被打破，因此重置 cnt 为 1。
5. 更新结果：
   • 每次 cnt 达到或超过 k 时，说明找到了一个长度为 k 或更长的交替颜色组，因此 res 增加 1。
6. 返回结果：
   • 循环结束后，返回 res，即交替颜色组的总数。

注意：

• 这个方法有一个潜在的问题：它实际上会计算所有长度至少为 k 的交替颜色序列的数量，而不仅仅是长度为 k 的。如果只需要长度为 k 的交替颜色组的数量，需要在 cnt 达到 k 时立即重置它，而不是继续增加 cnt 并检查它是否超过 k。不过，根据函数名 numberOfAlternatingGroups 和没有特定说明只计算长度为 k 的组，这里的实现可能是合理的。
• 另外，循环的起始值 -k + 2 和结束值 colorsSize - 1 确保了所有可能的 k 长度的子数组都被检查到了，并且处理好了数组的循环性。

原文地址：https://blog.csdn.net/babyiu5201314/article/details/144096707

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！