滑動視窗 — 實戰題解

# python
# LC 1151 - Minimum Swaps to Group All 1's Together
# IDEA: fixed window of width ones = sum(data); the window holding the most 1s needs the fewest swaps
# time = O(n), space = O(1)
def minSwaps(data):
    ones = sum(data)
    if ones == 0:
        return 0
    in_window = 0                         # 1s inside the current window
    best = 0
    for right in range(len(data)):
        in_window += data[right]
        if right >= ones:                 # window is one too wide: drop the cell that fell off
            in_window -= data[right - ones]
        if right >= ones - 1:             # window is exactly `ones` wide
            best = max(best, in_window)
    return ones - best

# python
# LC 424 - Longest Repeating Character Replacement
# IDEA: grow right; while the window needs more than k replacements, shrink left; maxFreq only rises
# time = O(n), space = O(1)   (26 uppercase letters)
def characterReplacement(s, k):
    count = {}
    left = 0
    max_freq = 0                          # highest count of one letter seen in any window so far
    best = 0
    for right in range(len(s)):
        ch = s[right]
        count[ch] = count.get(ch, 0) + 1
        max_freq = max(max_freq, count[ch])
        while (right - left + 1) - max_freq > k:   # more than k letters to replace
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

// java
// LC 424 - Longest Repeating Character Replacement
// IDEA: grow right; while the window needs more than k replacements, shrink left; maxFreq only rises
// time = O(n), space = O(1)
public int characterReplacement(String s, int k) {
    int[] count = new int[26];
    int left = 0;
    int maxFreq = 0;
    int best = 0;
    for (int right = 0; right < s.length(); right++) {
        int ch = s.charAt(right) - 'A';
        count[ch]++;
        maxFreq = Math.max(maxFreq, count[ch]);
        while ((right - left + 1) - maxFreq > k) {   // more than k replacements needed
            count[s.charAt(left) - 'A']--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

# python
# LC 424 - Longest Repeating Character Replacement (one window per letter)
# IDEA: for each letter, the longest window whose non-letter count is <= k
# time = O(26 * n), space = O(26)
def characterReplacement_per_letter(s, k):
    best = 0
    for letter in set(s):
        left = 0
        matches = 0                       # copies of `letter` inside the window
        for right in range(len(s)):
            if s[right] == letter:
                matches += 1
            while (right - left + 1) - matches > k:
                if s[left] == letter:
                    matches -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

# python
# LC 1838 - Frequency of the Most Frequent Element
# IDEA: sort; the longest window whose cost to level up to nums[right] is <= k
# time = O(n log n), space = O(n)   (the sorted copy; the window itself is O(1))
def maxFrequency(nums, k):
    nums = sorted(nums)
    left = 0
    window_sum = 0
    best = 0
    for right in range(len(nums)):
        window_sum += nums[right]
        # raising every value in [left, right] to nums[right] costs this many increments
        while nums[right] * (right - left + 1) - window_sum > k:
            window_sum -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best

// java
// LC 1838 - Frequency of the Most Frequent Element
// IDEA: sort; the longest window whose cost to level up to nums[right] is <= k
// time = O(n log n), space = O(1) extra
public int maxFrequency(int[] nums, int k) {
    Arrays.sort(nums);
    int left = 0;
    long windowSum = 0;
    int best = 0;
    for (int right = 0; right < nums.length; right++) {
        windowSum += nums[right];
        // cost to raise every value in the window to nums[right]
        while ((long) nums[right] * (right - left + 1) - windowSum > k) {
            windowSum -= nums[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

# python
# LC 413 - Arithmetic Slices
# IDEA: run = slices ending at i; it grows by 1 while the difference holds and resets when it breaks
# time = O(n), space = O(1)
def numberOfArithmeticSlices(nums):
    total = 0
    run = 0                               # arithmetic slices that end at index i
    for i in range(2, len(nums)):
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
            run += 1                      # every slice ending at i-1, extended, plus the new length-3 one
            total += run
        else:
            run = 0                       # the difference changed: no slice crosses i-1..i
    return total

# python
# LC 713 - Subarray Product Less Than K
# IDEA: shrink while product >= k; every start in [left, right] gives one valid subarray ending at right
# time = O(n), space = O(1)
def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0                          # products of positive integers are never < 1
    left = 0
    product = 1
    count = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product //= nums[left]        # exact: nums[left] divides the product
            left += 1
        count += right - left + 1
    return count

// java
// LC 713 - Subarray Product Less Than K
// IDEA: shrink while product >= k; every start in [left, right] gives one valid subarray ending at right
// time = O(n), space = O(1)
public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) {
        return 0;                       // no product of positive ints is < 1
    }
    int left = 0;
    long product = 1;
    int count = 0;
    for (int right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        count += right - left + 1;      // subarrays ending at right, starting in [left, right]
    }
    return count;
}