首页 > 其他分享 >力扣刷题——3261. 统计满足 K 约束的子字符串数量 II

力扣刷题——3261. 统计满足 K 约束的子字符串数量 II

时间:2024-11-13 17:59:10浏览次数:1  
标签:count 力扣 temLeft int mid 3261 prefix vector II

看了题目的两个初始用例,感觉能用前缀和和滑动窗口来解决,前缀和设定为从下标0到当前位置所有符合条件的答案数量,于是先写了一个:

vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>> &queries)
{
    int n = s.size();
    vector<long long> prefix(n + 1, 0);
    vector<int> count(2, 0);
    int temLeft = 0;
    for (int i = 0; i < s.size(); i++)
    {
        count[s[i] - '0']++;
        while (count[0] > k && count[1] > k)
        {
            count[s[temLeft] - '0']--;
            temLeft++;
        }
        prefix[i + 1] = prefix[i] + i - temLeft + 1;
    }

    vector<long long> res;
    for (int i = 0; i < queries.size(); i++)
    {
        int left = queries[i][0];
        int right = queries[i][1];
        if (left)
            res.emplace_back(prefix[right + 1] - prefix[left + 1]);
        else
            res.emplace_back(prefix[right + 1] - prefix[left + 1] + 1);
    }
    return res;
}

但是这样存在一个问题,当用例为s = "010101", k = 2时就会开始报错。在query = [[0,4],[1,4]]时,能够得到对于[0,4]用例的正确答案15,而在计算[1,4]时使用前缀和相减的方式15 - 3,得到了错误的答案12,这是因为在这两个查询区域之中,任取用例都是合法的,在这种情况下不能够用前缀和的方式求解,而应该用(query[1] - query[0] + 1) * (query[1] - query[0]) / 2。此外也需要注意到,每个查询区域中的子数组可能不全是合法的,所以最终的答案应该是一个查询区域中,两种可能的答案形式之和,即全合法区域和非全合法区域,因此需要一个能够将两个区域分开的下标mid,这样每个查询的答案就为,非全合法部分prefix[query[1]] - prefix[mid],与全合法部分(mid - query[0] + 1) * (mid - query[0]) / 2
为了能够得到下标mid,在处理计算前缀和的过程中,需要保存对于每一次当前位置的一个合法区域,其中的左边界。于是有如下实现:

vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>> &queries)
{
    int n = s.size();
    //这个实现跟上述文字描述有小出入,为了更优雅的写法,将前缀和的数组大小设置为n + 1
    vector<long long> prefix(n + 1, 0);
    vector<int> vecLeft(n, 0);
    vector<int> count(2, 0);
    int temLeft = 0;
    for (int i = 0; i < s.size(); i++)
    {
        count[s[i] - '0']++;
        while (count[0] > k && count[1] > k)
        {
            count[s[temLeft] - '0']--;
            temLeft++;
        }
        prefix[i + 1] = prefix[i] + i - temLeft + 1;
        vecLeft[i] = temLeft;
    }

    vector<long long> res;
    for (int i = 0; i < queries.size(); i++)
    {
        int left = queries[i][0];
        int right = queries[i][1];
        //因为在这个数组中,值是单调的,因此可以使用二分查找提速
        int mid = lower_bound(vecLeft.begin() + left, vecLeft.begin() + right + 1, left) - vecLeft.begin();
        res.emplace_back((long long)(mid - left) * (mid - left + 1) / 2 + prefix[right + 1] - prefix[mid]);
    }
    return res;
}

标签:count,力扣,temLeft,int,mid,3261,prefix,vector,II
From: https://www.cnblogs.com/yuhixyui/p/18544476

相关文章

  • Vue网站发布到iis后提示404页面不可访问
    vue重定向和跨域配置:https://zhuanlan.zhihu.com/p/5306882511.安装组件:URLRewrite:https://www.iis.net/downloads/microsoft/url-rewriteApplicationRequestRouting:https://www.iis.net/downloads/microsoft/application-request-routing2.新建一个web.config放到发布到文件......
  • 代码随想录算法训练营第二十五天| leetcode491.递增子序列、leetcode46.全排列、leetc
    1leetcode491.递增子序列题目链接:491.非递减子序列-力扣(LeetCode)文章链接:代码随想录视频链接:回溯算法精讲,树层去重与树枝去重|LeetCode:491.递增子序列_哔哩哔哩_bilibili思路:用之前的方法,结果翻车了,好好看视频学新技能吧1.1视频后的思路真的没想到用set来去重,还是基......
  • 力扣题目解析--有效的括号
    题目给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。代码展示 classSolution{public:boolisValid(string......
  • 代码随想录算法训练营第二十四天| leetcode93.复原IP地址、 leetcode78.子集、leetcod
    1leetcode93.复原IP地址题目链接:93.复原IP地址-力扣(LeetCode)文章链接:代码随想录视频链接:回溯算法如何分割字符串并判断是合法IP?|LeetCode:93.复原IP地址_哔哩哔哩_bilibili思路:就是将这个字符串符合要求的进行一个收集,然后使用列表存储,最后使用join函数将这个列表进行连......
  • 力扣21 打卡15 长度为 K 的子数组的能量值 II
    思路:该算法使用滑动窗口和计数器来判断每个长度为(k)的子数组是否满足连续递增的条件。遍历数组时,使用cnt记录当前连续递增的元素数。如果当前元素和前一个元素不连续递增,则将cnt重置为1,否则增加cnt。当cnt大于等于(k)时,表示找到了一个满足条件的子数组,将......
  • leetcode 59. 螺旋矩阵 II java解法
    以123456789为例n=奇数结果1                2                3      i8                9                47                6             ......
  • 力扣 653. 两数之和 IV 二叉树/binary-tree two-sum IV
    数组系列力扣数据结构之数组-00-概览力扣.53最大子数组和maximum-subarray力扣.128最长连续序列longest-consecutive-sequence力扣.1两数之和N种解法two-sum力扣.167两数之和IItwo-sum-ii力扣.170两数之和IIItwo-sum-iii力扣.653两数之和IVtwo-sum-IV力......
  • 代码随想录算法训练营第二十三天| leetcode39. 组合总和、leetcode40.组合总和II、lee
    1leetcode39.组合总和题目链接:39.组合总和-力扣(LeetCode)文章链接:代码随想录视频链接:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)|回溯法精讲!_哔哩哔哩_bilibili思路:跟之前差不多,就是将他的循环改一下,但是我发现有重复的数值了,不知道如何删除1.1自......
  • 本地html 加载js 和 两种定义模块的方式, IIFE and 对象字面量
    本地html加载js和两种定义模块的方式,IIFEand对象字面量需求希望写一个不启动服务的页面,也不用vitewebpack打包,就双击就能运行就行~开始以为requirejs比较老,结果发现本地也不能运行,chrome报跨域,没有权限。IIFE(立即执行函数表达式):varmyModule=(function(){v......
  • 力扣 170. 两数之和 III - 数据结构设计 two-sum III
    数组系列力扣数据结构之数组-00-概览力扣.53最大子数组和maximum-subarray力扣.128最长连续序列longest-consecutive-sequence力扣.1两数之和N种解法two-sum力扣.167两数之和IItwo-sum-ii力扣.170两数之和IIItwo-sum-iii力扣.653两数之和IVtwo-sum-IV力......