I Hate LeetCode

This is technically not part of project Felys. I personally hate doing LeetCode, even though I’ve tried so hard to convince myself that it helps me stand on the shoulders of giants. To be honest, it’s totally possible that I chose academia just to get rid of LeetCode. Nevertheless, I’m still going to do a few problems. I’m not expecting anyone to read this, so I’m going to mix languages as it’s just for myself.

这次算是系统性地刷题，所以不少题即使我做过，也不会提前放在这里。

最讨厌刷题了，要昔涟陪着才能写下去。

滑动窗口与双指针

定长滑动窗口

定长滑动窗口有两种思路，区别在于当进入循环时区间的定义。假设 s 是状态，第一种情况代表的是上一个完整窗口的状态，第二种是当前窗口不计入当前值时的状态，即上一个完整窗口剔除当前窗口的不需要的那个值后的状态。第一种的定义完善但无法处理复杂逻辑，因此建议第二种，并且不要尝试魔改第二种模版来套用第一种，会出现边界问题。根据状态定义就可以反推出 left = i - k + 1 这个条件。

这套框架好的地方就在于，处理窗口的时候是绝对安全的。

1456 Maximum Number of Vowels in a Substring of Given Length

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        max_vowels = 0
        num_vowels_in_window = 0
        vowels = 'aeiou'

        for i, ch in enumerate(s):
            if ch in vowels:
                num_vowels_in_window += 1

            left = i - k + 1
            if left < 0:
                continue

            max_vowels = max(max_vowels, num_vowels_in_window)

            if s[left] in vowels:
                num_vowels_in_window -= 1

        return max_vowels

643 Maximum Average Subarray I

Make sure max_sum is initialized to -inf, since there are negative values.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_sum = -inf
        current_sum = 0
        for i, num in enumerate(nums):
            current_sum += num

            left = i - k + 1
            if left < 0:
                continue

            max_sum = max(max_sum, current_sum)
            current_sum -= nums[left]
        return max_sum / k

1343 Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        num_sub_arrays = 0
        current_sum = 0
        for i, num in enumerate(arr):
            current_sum += num

            left = i - k + 1
            if left < 0:
                continue

            if current_sum / k >= threshold:
                num_sub_arrays += 1
            current_sum -= arr[left]
        return num_sub_arrays

2090 K Radius Subarray Averages

This problem can be transformed to standard sliding window problem, so there is not need to expand from center.

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        sub_array_len = 2 * k + 1
        avg_list = [-1] * len(nums)
        current_sum = 0

        for i, num in enumerate(nums):
            current_sum += num

            left = i - sub_array_len + 1
            if left < 0:
                continue

            avg_list[i - k] = current_sum // sub_array_len
            current_sum -= nums[left]

        return avg_list

2379 Minimum Recolors to Get K Consecutive Black Blocks

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        max_black_count = 0
        black_count = 0
        for i, color in enumerate(blocks):
            if color == 'B':
                black_count += 1

            left = i - k + 1
            if left < 0:
                continue

            max_black_count = max(max_black_count, black_count)
            if blocks[left] == 'B':
                black_count -= 1

        return k - max_black_count

2461 Maximum Sum of Distinct Subarrays With Length K

Using defaultdict has slightly larger overhead, but it’s more elegant.

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        num_to_count_map = defaultdict(int)
        current_sum = 0
        max_sum = 0

        for i, num in enumerate(nums):
            num_to_count_map[num] += 1
            current_sum += num

            left = i - k + 1
            if left < 0:
                continue

            if len(num_to_count_map) == k:
               max_sum = max(max_sum, current_sum)

            num_to_remove = nums[left]
            num_to_count_map[num_to_remove] -= 1
            if num_to_count_map[num_to_remove] == 0:
                num_to_count_map.pop(num_to_remove)
            current_sum -= num_to_remove

        return max_sum

1423 Maximum Points You Can Obtain from Cards

别套模版套傻了，偶尔也可以用第一种写法，简单且不会出错。

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        window_len = len(cardPoints) - k
        current_sum = sum(cardPoints[:window_len])
        min_sum = current_sum
        for i in range(window_len, len(cardPoints)):
            current_sum += cardPoints[i] - cardPoints[i - window_len]
            min_sum = min(min_sum, current_sum)
        return sum(cardPoints) - min_sum

1052 Grumpy Bookstore Owner

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        unsatisfied_count = 0
        satisfied_count = 0
        max_unsatisfied_count = 0
        for i, (num_customers, is_grumpy) in enumerate(zip(customers, grumpy)):
            unsatisfied_count += is_grumpy * num_customers
            satisfied_count += (1 - is_grumpy) * num_customers

            left = i - minutes + 1
            if left < 0:
                continue

            max_unsatisfied_count = max(max_unsatisfied_count, unsatisfied_count)
            unsatisfied_count -= grumpy[left] * customers[left]
        return satisfied_count + max_unsatisfied_count

3679 Minimum Discards to Balance Inventory

这道题需要额外记录每一个元素是否被接收，只有被接收的元素后续才需要被剔除。

Use example arrivals = [1, 1, 1, 1], w = 3, m = 1 to verify.

class Solution:
    def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int:
        discard_count = 0
        type_to_kept_map = defaultdict(int)
        is_kept = [False] * len(arrivals)

        for i, item in enumerate(arrivals):
            if type_to_kept_map[item] < m:
                is_kept[i] = True
                type_to_kept_map[item] += 1
            else:
                discard_count += 1

            left = i - w + 1
            if left < 0:
                continue

            item_to_discard = arrivals[left]
            if is_kept[left]:
                type_to_kept_map[item_to_discard] -= 1

        return discard_count

不定长滑动窗口

3 Longest Substring Without Repeating Characters

太经典了，这第五次刷这道题了。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        max_length = 0

        left = 0
        for i, ch in enumerate(s):
            while ch in char_set:
                char_set.remove(s[left])
                left += 1

            char_set.add(ch)
            current_length = len(char_set)
            max_length = max(max_length, current_length)

        return max_length

3090 Maximum Length Substring With Two Occurrences

这是上一题的进阶版。很奇怪的是上一题是中等，这一题反而是简单。

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        occurrences = defaultdict(int)
        left = 0
        max_length = 0

        for i, ch in enumerate(s):
            occurrences[ch] += 1
            while occurrences[ch] > 2:
                occurrences[s[left]] -= 1
                left += 1
            max_length = max(max_length, i - left + 1)

        return max_length

1493 Longest Subarray of 1’s After Deleting One Element

思路是对的，但直接维护当前零的数量更简单，不然要先确保窗口已经构建完全。

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        zero_count= 0
        max_length = 0
        left = 0

        for i, num in enumerate(nums):
            zero_count += 1 - num
            while zero_count > 1:
                zero_count -= 1 - nums[left]
                left += 1
            max_length = max(max_length, i - left)
        return max_length

3634 Minimum Removals to Balance Array

这是为数不多真可以开头先排序再做的题目。

Window definition is [left, i].

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        nums.sort()

        max_length = 0
        left = 0
        for i, num in enumerate(nums):
            while left < i and nums[left] * k < num:
                left += 1
            max_length = max(max_length, i - left + 1)

        return len(nums) - max_length

二分算法

暂无

单调栈

暂无

网格图

暂无

位运算

暂无

图论算法

暂无

动态规划

暂无

常用数据结构

暂无

数学算法

暂无

贪心与思维

暂无

链表、树与回溯

暂无

字符串

暂无