【LeetCode】每日一题 2024_11_12 统计满足 K 约束的子字符串数量 I（滑动窗口）

前言

每天和你一起刷 LeetCode 每日一题~

LeetCode 启动！

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

这道题给了很小的数据范围，能够直接用暴力通过（不过我对滑窗比较熟悉，所以也就直接用滑窗解答了~）

代码与解题思路

先读题：

题目要求找 0 不超过 k 个， 1 不超过 k 个的子数组（注意：只有 0 和 1 都超过 k 个才算违反的题目要求），直接通过滑动窗口来维护这个子数组，r 指针给子数组添加元素，不符合题目条件就让 l 指针减少元素，代码如下：（我平时用的滑窗模版）

func countKConstraintSubstrings(s string, k int) (ans int) {
    // 经典的子数组型滑窗
    l, cnt := 0, [2]int{}
    for r := range s {
        if s[r] == '0' {
            cnt[0]++
        } else {
            cnt[1]++
        }
        // 题目要求满足 0 和 1 两个数量都超过 k 才算违反
        for cnt[0] > k && cnt[1] > k {
            if s[l] == '0' {
                cnt[0]--
            } else {
                cnt[1]--
            }
            l++
        }
        ans += r-l+1
    }
    return ans
}

小优化（精简代码）

小细节：字符 0 的 ASCII 值是偶数，所以我们可以通过 &1 的方式直接区分 0 和 1

func countKConstraintSubstrings(s string, k int) (ans int) {
    l, cnt := 0, [2]int{}
    for r := range s {
        cnt[s[r]&1]++
        for cnt[0] > k && cnt[1] > k {
            cnt[s[l]&1]--
            l++
        }
        ans += r-l+1
    }
    return ans
}

每天进步一点点，我们明天不见不散~

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。

原文地址：https://blog.csdn.net/Locky136/article/details/143710829

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