Leecode刷题C语言之统计满足K约束的子字符串数量②

执行结果:通过

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

题目： 统计满足K约束的子字符串数量②

给你一个 二进制 字符串 s 和一个整数 k。另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。

返回一个整数数组 answer ，其中 answer[i] 表示 s[li..ri] 中满足 k 约束的子字符串的数量。

示例 1：

输入：s = "0001111", k = 2, queries = [[0,6]]

输出：[26]

解题思路：

1. 初始化变量：
   • cnt[2]：一个数组，用于记录当前遍历到的子字符串中字符 '0' 和字符 '1' 的数量。
   • n：字符串 s 的长度。
   • returnSize：用于返回结果数组的大小，设置为查询的数量 queriesSize。
   • ans：结果数组，用于存储每个查询的结果，初始化为全零。
   • right：一个数组，用于记录每个位置 i 右侧第一个使得字符 '0' 和字符 '1' 的数量都大于 k 的位置（如果不存在这样的位置，则设为 n）。
   • temp：一个辅助数组，用于快速计算满足条件的子字符串数量。
2. 预处理：
   • 初始化 right 数组，将所有值设为 n，表示默认没有位置使得字符 '0' 和字符 '1' 的数量都大于 k。
   • 初始化 temp 数组，用于存储到当前位置为止，满足条件的子字符串数量。
3. 第一次遍历（计算 right 和 temp 数组）：
   • 使用双指针 i 和 p，其中 i 是当前遍历到的位置，p 是窗口的左边界。
   • 遍历字符串 s，更新 cnt 数组以记录当前窗口内字符 '0' 和字符 '1' 的数量。
   • 当窗口内字符 '0' 和字符 '1' 的数量都大于 k 时，移动左边界 p，并更新 right[p] 为当前位置 i（表示 p 右侧第一个不满足条件的位置是 i）。
   • 计算 temp[i+1]，表示到当前位置为止，以每个位置为结尾的满足条件的子字符串数量。这是通过累加 (i - p + 1) 实现的，因为从 p 到 i 的每个位置都可以作为满足条件的子字符串的结尾。
4. 处理查询：
   • 对于每个查询 [l, r]，计算满足条件的子字符串数量。
   • 使用 right[l] 来确定从 l 开始，第一个不满足条件的位置 t（如果 right[l] 大于 r，则 t 设为 r + 1）。
   • 计算两部分子字符串的数量：
     • part1：从 l 到 t-1 的子字符串中，满足条件的子字符串数量。这部分可以通过计算等差数列的和 (t - l + 1) * (t - l) / 2 得到。
     • part2：从 t 到 r 的子字符串中，满足条件的子字符串数量。这部分可以直接从 temp 数组中通过 temp[r+1] - temp[t] 得到。
   • 将 part1 和 part2 相加，得到查询结果，并存储在 ans 数组中。
5. 释放内存：
   • 释放 right 和 temp 数组占用的内存。
6. 返回结果：
   • 返回结果数组 ans。

long long* countKConstraintSubstrings(char* s, int k, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int cnt[2] = {0};
    int n = strlen(s);
    (*returnSize) = queriesSize;
    long long* ans = calloc(queriesSize,sizeof(long long));
    int *right = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        right[i] = n;
    }
    long long* temp = calloc(n+1,sizeof(long long));
    int p = 0;
    for(int i = 0;i < n;i++){
        cnt[s[i]-'0']++;
        while(cnt[0] > k&&cnt[1] > k){
            cnt[s[p]-'0']--;
            right[p] = i;
            p++;
        }
        temp[i+1] = temp[i] + i - p + 1;
    }
    for(int i = 0;i < queriesSize;i++){
        int l = queries[i][0] , r = queries[i][1];
        int t = right[l] <= r ? right[l] : r + 1;
        long long part1 = (long long)(t - l + 1) * (t - l) / 2;
        long long part2 = temp[r+1] - temp[t];
        ans[i] = part1 + part2;
    }
    free(right);
    free(temp);
    return ans;
}

 

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

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