101 Days

切换主题

滑窗穷百变，倦极复摸鱼 ​

22 ​

2.26，进阶不是我这小菜鸟刷的，继续题单里的“不定长滑动窗口”，只刷 rating 分 1700 以下的题。

3. 无重复字符的最长子串 ​

py
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = left = 0
        cnt = defaultdict(int)
        for right, x in enumerate(s):
            cnt[x] += 1
            while cnt[x] > 1:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

1004. 最大连续1的个数 III ​

py
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        ans = left = cnt0 = 0
        for right, x in enumerate(nums):
            cnt0 += 1 - x
            while cnt0 > k:
                cnt0 -= 1 - nums[left]
                left += 1
            ans = max(ans, right - left + 1)
        return ans

1658. 将 x 减到 0 的最小操作数 ​

py
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        target = sum(nums) - x
        if target < 0:
            return -1

        s = left = 0
        ans = -1
        for right, x in enumerate(nums):
            s += x
            while s > target:
                s -= nums[left]
                left += 1
            if s == target:
                ans = max(ans, right - left + 1)

        return -1 if ans < 0 else len(nums) - ans

76. 最小覆盖子串 ​

py
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt = defaultdict(int)
        for i in t:
            cnt[i] += 1
        missing = len(cnt)

        ans_l, ans_r = -1, len(s)
        left = 0
        for right, x in enumerate(s):
            cnt[x] -= 1
            if cnt[x] == 0:
                missing -= 1

            while missing == 0:
                if right - left < ans_r - ans_l:
                    ans_l, ans_r = left, right

                out = s[left]
                if cnt[out] == 0:
                    missing += 1
                cnt[out] += 1
                left += 1

        return "" if ans_l < 0 else s[ans_l : ans_r + 1]

23 ​

刷了“越短越合法”和“越长越合法”，还有“恰好型滑动窗口”的题。

有点心力交瘁，感觉违背了摸鱼原则，明天歇歇，做一下这几个类型的总结。

24 ​

2.28，总结也不想写，刷了 Exercism 的题目，休息一下。

25 ​

三月第一天，总结一下之前刷的题。

子数组越短越符合题目要求，内层循环结束后 [left, right] 为合法区间，那么对于固定的右端点 right 来说，left、left+1、...、right 都是合法的左端点，所以有 right - left + 1 个合法的子数组。

713. 乘积小于 K 的子数组 ​

py
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        ans = left = 0
        prod = 1
        for right, x in enumerate(nums):
            prod *= x
            while prod >= k: # 左端点右移，缩小区间，直到满足题目要求
                prod //= nums[left]
                left += 1
            ans += right - left + 1
        return ans

26 ​

子数组越长越符合题目要求，内层循环结束后 [left, right] 不满足题目要求，但退出循环前的上一轮循环，[left-1, right] 是满足题目要求的，

所以对于固定的 right 来说，left-1、left-2、...、0 都是合法的左端点，所以有 left 个合法的子数组。

2962. 统计最大元素出现至少 K 次的子数组 ​

py
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        ans = left = cnt = 0
        for right, x in enumerate(nums):
            if x == mx:
                cnt += 1
            while cnt == k:
                if nums[left] == mx:
                    cnt -= 1
                left += 1
            ans += left
        return ans

3325. 字符至少出现 K 次的子字符串 I ​

py
class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        ans = left = 0
        cnt = defaultdict(int)
        for right, x in enumerate(s):
            cnt[x] += 1
            while cnt[x] == k:
                cnt[s[left]] -= 1
                left += 1
            ans += left
        return ans

27 ​

3.2，恰好型滑动窗口。

例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：计算有多少个元素和 ≥k 的子数组。计算有多少个元素和 >k，也就是 ≥k+1 的子数组。答案就是元素和 ≥k 的子数组个数，减去元素和 ≥k+1 的子数组个数。这里把 > 转换成 ≥，从而可以把滑窗逻辑封装成一个函数 solve，然后用 solve(k)−solve(k+1) 计算，无需编写两份滑窗代码。总结：「恰好」可以拆分成两个「至少」，也就是两个「越长越合法」的滑窗问题。注：也可以把问题变成 ≤k 减去 ≤k−1，即两个「至多」。可根据题目选择合适的变形方式。注：也可以把两个滑动窗口合并起来，维护同一个右端点 right 和两个左端点 left1 和 left2，我把这种写法叫做三指针滑动窗口。

930. 和相同的二元子数组 ​

py
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        # 找到和 < goal 的子数组个数
        def solve(goal):
            ans = left = s = 0
            for right, x in enumerate(nums):
                s += x
                while s >= goal and left <= right:
                    s -= nums[left]
                    left += 1
                ans += right - left + 1
            return ans

        # 和为 0,1,2, ..., goal 的子数组个数
        # 和为 0,1,2, ..., goal-1 的子数组个数
        # 相减得到和为 goal 的子数组个数
        return solve(goal + 1) - solve(goal)
py
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        # 找到和 >= goal 的子数组个数
        def solve(goal):
            ans = left = s = 0
            for right, x in enumerate(nums):
                s += x
                while s >= goal and left <= right:
                    s -= nums[left]
                    left += 1
                ans += left
            return ans

        # 和为 goal, goal+1, ..., sum(nums) 的子数组个数
        # 和为 goal+1, goal+2, ..., sum(nums) 的子数组个数
        # 相减得到和为 goal 的子数组个数
        return solve(goal) - solve(goal + 1)

1248. 统计「优美子数组」 ​

py
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def solve(k):
            ans = left = cnt = 0
            for right, x in enumerate(nums):
                cnt += x % 2
                while cnt > k:
                    cnt -= nums[left] % 2
                    left += 1
                ans += right - left + 1  # <= k
            return ans

        return solve(k) - solve(k - 1)
py
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def solve(k):
            ans = left = cnt = 0
            for right, x in enumerate(nums):
                cnt += x % 2
                while cnt >= k: # >=
                    cnt -= nums[left] % 2
                    left += 1
                ans += left # >= k
            return ans

        return solve(k) - solve(k + 1)
py
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        ans = left1 = left2 = cnt1 = cnt2 = 0
        for right, x in enumerate(nums):
            cnt1 += x % 2
            while cnt1 >= k:
                cnt1 -= nums[left1] % 2
                left1 += 1
            cnt2 += x % 2
            while cnt2 > k:
                cnt2 -= nums[left2] % 2
                left2 += 1
            ans += left1 - left2
        return ans

28 ​

3.3，Exercism 进度 35/146 ^_^

29 ​

Exercism 继续。

30 ​

Exercism 继续。

31 ​

3.6，开始双指针。

两个指针 left=0, right=n−1，从数组的两端开始，向中间移动，这叫相向双指针。上面的滑动窗口相当于同向双指针。

32 ​

3.7，周末懒得动，写点 codewars 简单题。