【算法】滑动窗口题单——1.定长滑动窗口⭐

news/2024/5/20 8:06:21 标签: 算法, 滑动窗口, 双指针, 力扣, leetcode, 滚动哈希

文章目录

  • 1456. 定长子串中元音的最大数目
  • 2269. 找到一个数字的 K 美丽值
  • 1984. 学生分数的最小差值（排序）
  • 643. 子数组最大平均数 I
  • 1343. 大小为 K 且平均值大于等于阈值的子数组数目
  • 2090. 半径为 k 的子数组平均值
  • 2379. 得到 K 个黑块的最少涂色次数
  • 1052. 爱生气的书店老板
  • 2841. 几乎唯一子数组的最大和
  • 2461. 长度为 K 子数组中的最大和
  • 1423. 可获得的最大点数（转换成找中间窗口最小）
  • 2134. 最少交换次数来组合所有的 1 II
  • 2653. 滑动子数组的美丽值⭐
    • 解法1——利用二分维护窗口中的排序（超时了）
    • 解法2——滑动窗口+暴力枚举 ⭐（牛逼的暴力枚举！🐂）
  • 567. 字符串的排列
  • 438. 找到字符串中所有字母异位词
  • 2156. 查找给定哈希值的子串⭐⭐⭐
  • 346. 数据流中的移动平均值（用队列维护窗口）
  • 1100. 长度为 K 的无重复字符子串

题单来源：https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/solutions/2464878/hua-dong-chuang-kou-on-shi-jian-o1-kong-cqawc/

1456. 定长子串中元音的最大数目

https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/

在这里插入图片描述

提示：

1 <= s.length <= 10^5
s 由小写英文字母组成
1 <= k <= s.length

定长滑动窗口，进来一个加一个，出去一个减一个。

class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length(), cnt = 0, ans = 0;
        Set<Character> vowel = Set.of('a', 'e', 'i', 'o', 'u');
        for (int l = 0, r = 0; r < n; ++r) {
            if (vowel.contains(s.charAt(r))) cnt++;
            if (r >= l + k) {
                if (vowel.contains(s.charAt(l))) cnt--;
                l++;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

2269. 找到一个数字的 K 美丽值

https://leetcode.cn/problems/find-the-k-beauty-of-a-number/

在这里插入图片描述
提示：
1 <= num <= 10^9
1 <= k <= num.length （将 num 视为字符串）

以240为例，
起初 x=100，y=1. 取出 240 % 100 / 1 = 40;
之后 x=1000，y=10 取出 240 % 1000 / 10 = 24;

class Solution {
    public int divisorSubstrings(int num, int k) {
        int ans = 0;
        long x = 1, y = 1;
        for (int i = 0; i < k; ++i) x *= 10;
        for (; x / 10 <= num; x *= 10, y *= 10) {
            long z = (long)num % x / y;
            if (z != 0 && num % z == 0) ++ans;
        }
        return ans;
    }
}

1984. 学生分数的最小差值（排序）

https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/description/

在这里插入图片描述

排序之后的区间两边一定是一个最大值和一个最小值。
逐个枚举即可。

class Solution {
    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, ans = nums[n - 1] - nums[0];
        for (int l = 0, r = k - 1; r < n; ++l, ++r) {
            ans = Math.min(ans, nums[r] - nums[l]);
        }
        return ans;
    }
}

643. 子数组最大平均数 I

https://leetcode.cn/problems/maximum-average-subarray-i/description/
在这里插入图片描述

注意可能会溢出的问题。

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double ans = -10001, s = 0;
        for (int l = 0, r = 0; r < nums.length; ++r) {
            s += nums[r];
            if (r - l + 1 == k) {
                ans = Math.max(ans, s / k);
                s -= nums[l++];
            }
        }
        return ans;
    }
}

1343. 大小为 K 且平均值大于等于阈值的子数组数目

https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/

在这里插入图片描述
提示：
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int ans = 0;
        long t = threshold * k, s = 0;
        for (int i = 0; i < k - 1; ++i) s += arr[i];
        for (int i = k - 1; i < arr.length; ++i) {
            s += arr[i];
            if (s >= t) ans++;
            s -= arr[i - k + 1];
        }
        return ans;
    }
}

2090. 半径为 k 的子数组平均值

https://leetcode.cn/problems/k-radius-subarray-averages/description/

在这里插入图片描述
提示：

n == nums.length
1 <= n <= 10^5
0 <= nums[i], k <= 10^5

用 s 维护长度为 2*k+1 窗口内所有值的总和。

class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        long s = 0, l = 2 * k + 1;
        for (int i = 0; i < 2 * k && i < n; ++i) s += nums[i];
        for (int i = 2 * k; i < n; ++i) {
            s += nums[i];
            ans[i - k] = (int)(s / l);
            s -= nums[i - 2 * k];
        }
        return ans;
    }
}

2379. 得到 K 个黑块的最少涂色次数

https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/description/

在这里插入图片描述

提示：
n == blocks.length
1 <= n <= 100
blocks[i] 要么是 'W' ，要么是 'B' 。
1 <= k <= n

固定长度滑动窗口。

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int ans = k, n = blocks.length(), s = 0;
        for (int i = 0; i < k - 1; ++i) {
            if (blocks.charAt(i) == 'W') s++;
        }
        for (int i = k - 1; i < n; ++i) {
            if (blocks.charAt(i) == 'W') s++;
            ans = Math.min(ans, s);
            if (blocks.charAt(i - k + 1) == 'W') s--;
        }
        return ans;
    }
}

1052. 爱生气的书店老板

https://leetcode.cn/problems/grumpy-bookstore-owner/description/

在这里插入图片描述

提示：

n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 10^4
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1

变量 s 维护长度为minutes的窗口中 生气时的顾客数量，这些顾客可以通过秘密技巧变得满意。
变量 total 计算本来就满意的顾客数量。

最后的答案是本来就满意的顾客数量+使用技巧变得满意的最多顾客数量。

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int n = customers.length, s = 0, mx = 0, total = 0;
        for (int i = 0; i < minutes - 1; ++i) {
            if (grumpy[i] == 1) s += customers[i];
            else total += customers[i];
        }
        for (int i = minutes - 1; i < n; ++i) {
            if (grumpy[i] == 1) s += customers[i];
            else total += customers[i];
            mx = Math.max(mx, s);
            if (grumpy[i - minutes + 1] == 1) s -= customers[i - minutes + 1];
        }
        return total + mx;
    }
}

2841. 几乎唯一子数组的最大和

https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/submissions/

在这里插入图片描述

提示：
1 <= nums.length <= 2 * 10^4
1 <= m <= k <= nums.length
1 <= nums[i] <= 10^9

用 s 维护和。
用 cnt 维护不同数字的种类数量。

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        long ans = 0, s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < k - 1; ++i) {
            s += nums.get(i);
            cnt.merge(nums.get(i), 1, Integer::sum);
        }
        for (int i = k - 1; i < nums.size(); ++i) {
            s += nums.get(i);
            cnt.merge(nums.get(i), 1, Integer::sum);
            if (cnt.size() >= m) ans = Math.max(ans, s);
            s -= nums.get(i - k + 1);
            cnt.merge(nums.get(i - k + 1), -1, Integer::sum);
            if (cnt.get(nums.get(i - k + 1)) == 0) cnt.remove(nums.get(i - k + 1));
        }
        return ans;
    }
}

2461. 长度为 K 子数组中的最大和

https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/description/
在这里插入图片描述
提示：
1 <= k <= nums.length <= 10^5
1 <= nums[i] <= 10^5

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        long ans = 0, s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            s += nums[i];
            cnt.merge(nums[i], 1, Integer::sum);
            if (cnt.size() == k) ans = Math.max(ans, s);
            if (i >= k - 1) {
                int x = nums[i - k + 1];
                s -= x;
                cnt.merge(x, -1, Integer::sum);
                if (cnt.get(x) == 0) cnt.remove(x);
            }
        }
        return ans;
    }
}

1423. 可获得的最大点数（转换成找中间窗口最小）

https://leetcode.cn/problems/maximum-points-you-can-obtain-from-cards/description/
在这里插入图片描述

提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

从两边拿要取最大，也就是找中间连续的最小。
可以使用固定长度滑动窗口。

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, l = n - k, total = 0, s = 0, mn = Integer.MAX_VALUE;
        if (l == 0) return Arrays.stream(cardPoints).sum();
        for (int i = 0; i < n; ++i) {
            s += cardPoints[i];
            total += cardPoints[i];
            if (i >= l - 1) {
                mn = Math.min(mn, s);
                s -= cardPoints[i - l + 1];
            }
        }
        return total - mn;
    }
}

2134. 最少交换次数来组合所有的 1 II

https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/description/

在这里插入图片描述

提示：
1 <= nums.length <= 10^5
nums[i] 为 0 或者 1

最后所以的 1 一定会相邻。
所以转换成求固定长度窗口中 1 出现的最大值，其它不在窗口中的 1 都需要交换过来。

class Solution {
    public int minSwaps(int[] nums) {
        int k = Arrays.stream(nums).sum(), mx = 0, s = 0, n = nums.length;
        for (int x = 0; x < 2 * n; ++x) {
            int i = x % n;
            s += nums[i];
            if (x >= k - 1) {
                mx = Math.max(mx, s);
                s -= nums[(x - k + 1) % n];
            }
        }
        return k - mx;
    }
}

2653. 滑动子数组的美丽值⭐

https://leetcode.cn/problems/sliding-subarray-beauty/description/

在这里插入图片描述

提示：

n == nums.length
1 <= n <= 10^5
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

解法1——利用二分维护窗口中的排序（超时了）

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        List<Integer> ls = new ArrayList<>();
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n; ++i) {
            int t = nums[i];
            int id = bs(ls, t);
            ls.add(id, t);
            if (ls.size() > k) {
                id = bs(ls, nums[i - k]);
                ls.remove(id);
            }
            if (ls.size() == k) {
                if (ls.get(x - 1) < 0) ans[i - k + 1] = ls.get(x - 1);
                else ans[i - k + 1] = 0;
            }
        }
        return ans;
    }

    public int bs(List<Integer> ls, int t) {
        int l = 0, r = ls.size();
        while (l < r) {
            int mid = l + r >> 1;
            if (ls.get(mid) < t) l = mid + 1;
            else r = mid;
        }
        return l;
    }
}

在这里插入图片描述

把 ArrayList 换成 LinkedList 超时会更多。

解法2——滑动窗口+暴力枚举 ⭐（牛逼的暴力枚举！🐂）

https://leetcode.cn/problems/sliding-subarray-beauty/solutions/2241294/hua-dong-chuang-kou-bao-li-mei-ju-by-end-9mvl/
在这里插入图片描述
虽然是暴力枚举，但是充分利用了数值的值域很小的特性。

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        final int BIAS = 50;
        int[] cnt = new int[BIAS * 2 + 1];  // 计数数组
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n; ++i) {
            cnt[nums[i] + BIAS]++;          // 进入窗口
            if (i >= k - 1) {               // 计算该位置的答案
                int left = x;               // 计算剩余的x
                for (int j = 0; j < BIAS; ++j) {
                    left -= cnt[j];
                    if (left <= 0) {        // 找到了答案
                        ans[i - k + 1] = j - BIAS;
                        break;
                    }
                }
                --cnt[nums[i - k + 1] + BIAS];  // 移出窗口
            }
        }
        return ans;
    }
}

567. 字符串的排列

https://leetcode.cn/problems/permutation-in-string/description/

在这里插入图片描述

提示：

1 <= s1.length, s2.length <= 10^4
s1 和 s2 仅包含小写字母

如果 s1 的排列之一是 s2 的 子串。那么应该满足 s2 的一个字串中，各个字符的数量和 s1 相同。

用计数数组维护窗口中各个字符的数量即可。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] cnt = new int[128];
        for (char ch: s1.toCharArray()) cnt[ch]++;
        for (int l = 0, r = 0; r < s2.length(); ++r) {
            cnt[s2.charAt(r)]--;
            if (r - l >= s1.length()) cnt[s2.charAt(l++)]++; 
            boolean f = true;
            for (char ch = 'a'; ch <= 'z'; ++ch) {
                if (cnt[ch] != 0) {
                    f = false;
                    break;
                }
            }
            if (f) return true;
        }
        return false;
    }
}

438. 找到字符串中所有字母异位词

https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

在这里插入图片描述

提示:

1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

维护 s 中长度等于 p 的滑动窗口，检查 窗口中的各个字符数量和 p 中的字符数量是否相等即可。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] cnt = new int[128];
        for (char ch: p.toCharArray()) cnt[ch]++;
        for (int l = 0, r = 0; r < s.length(); ++r) {
            cnt[s.charAt(r)]--;
            if (r - l >= p.length()) cnt[s.charAt(l++)]++;
            boolean f = true;
            for (char ch = 'a'; ch <= 'z'; ++ch) {
                if (cnt[ch] != 0) {
                    f = false;
                    break;
                }
            }
            if (f) ans.add(l);
        } 
        return ans;
    }
}

2156. 查找给定哈希值的子串⭐⭐⭐

https://leetcode.cn/problems/find-substring-with-given-hash-value/description/

在这里插入图片描述

提示：
1 <= k <= s.length <= 2 * 10^4
1 <= power, modulo <= 10^9
0 <= hashValue < modulo
s 只包含小写英文字母。
测试数据保证一定 存在 满足条件的子串。

解法1——倒序滚动哈希

https://leetcode.cn/problems/find-substring-with-given-hash-value/solutions/1249153/cha-zhao-gei-ding-ha-xi-zhi-de-zi-chuan-fi8jd/
倒序处理，
先处理出 p o w e r ( k − 1 ) m o d    m o d u l o power^(k-1) \mod modulo power(k−1)modmodulo。

class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int n = s.length(), pos = -1;
        // h:子串哈希值   mult:power^(k-1) mod modulo
        long h = 0, mult = 1;
        // 预处理最后一个子串的哈希值和 power^k mod modulo
        for (int i = n - 1; i >= n - k; --i) {
            h = (h * power + (s.charAt(i) - 'a' + 1)) % modulo;
            if (i != n - k) {
                mult = mult * power % modulo;
            }
        }
        if (h == hashValue) pos = n - k;
        // 向前计算哈希值并尝试更新下标
        for (int i = n - k - 1; i >= 0; --i) {
            h = ((h - (s.charAt(i + k) - 'a' + 1) * mult % modulo + modulo) * power + (s.charAt(i) - 'a' + 1)) % modulo;
            if (h == hashValue) {
                pos = i;
            }
        }
        return s.substring(pos, pos + k);
    }
}

解法2——倒序滑动窗口 + O ( 1 ) O(1) O(1) 额外空间

class Solution {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int n = s.length(), pos = -1;
        // h:子串哈希值   mult:power^(k-1) mod modulo
        long h = 0, mult = 1;
        // 预处理最后一个子串的哈希值和 power^k mod modulo
        for (int i = n - 1; i >= n - k; --i) {
            h = (h * power + (s.charAt(i) & 31)) % modulo;
            if (i != n - k) {
                mult = mult * power % modulo;
            }
        }
        if (h == hashValue) pos = n - k;
        // 向前计算哈希值并尝试更新下标
        for (int i = n - k - 1; i >= 0; --i) {
            h = ((h - (s.charAt(i + k) & 31) * mult % modulo + modulo) * power + (s.charAt(i) & 31)) % modulo;
            if (h == hashValue) {
                pos = i;
            }
        }
        return s.substring(pos, pos + k);
    }
}

小技巧，将’a’——'z’转成1——26 🐂

只需要 & 31 即可。
在这里插入图片描述

346. 数据流中的移动平均值（用队列维护窗口）

https://leetcode.cn/problems/moving-average-from-data-stream/description/

在这里插入图片描述
提示：
1 <= size <= 1000
-10^5 <= val <= 10^5
最多调用 next 方法 10^4 次

class MovingAverage {
    Queue<Integer> q = new LinkedList<>();
    int sz;
    double sum;

    public MovingAverage(int size) {
        sz = size;
        sum = 0;
    }
    
    public double next(int val) {
        q.offer(val);
        sum += val;
        if (q.size() > sz) sum -= q.poll();
        return sum / q.size();
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

1100. 长度为 K 的无重复字符子串

https://leetcode.cn/problems/find-k-length-substrings-with-no-repeated-characters/description/

在这里插入图片描述
提示：
1 <= S.length <= 10^4
S 中的所有字符均为小写英文字母
1 <= K <= 10^4

维护长度为 k 的滑动窗口中各个字符出现的数量。

class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        int[] cnt = new int[128];
        int ans = 0;
        for (int l = 0, r = 0; r < s.length(); ++r) {
            cnt[s.charAt(r)]++;
            if (r - l >= k) cnt[s.charAt(l++)]--;
            if (r >= k - 1 && check(cnt)) ans++;
        }
        return ans;
    }

    public boolean check(int[] cnt) {
        for (char ch = 'a'; ch <= 'z'; ++ch) {
            if (cnt[ch] > 1) {
                return false;
            }
        }
        return true;
    }
}

http://www.niftyadmin.cn/n/5223454.html

相关文章

渗透测试考核--两层内网 cs windows socks5

渗透测试考核--两层内网 cs windows socks5

这里考核为渗透 这里是网络拓扑图 这里记录一下 两台外网 两台内网 首先拿到C段 nmap进行扫描 外网1 nmap -p 80 172.16.17.2/24 主机存活 一般都是web服务入手 所以我们指定80端口 然后去查找开放的 最后获取到2个ip Nmap scan report for 172.16.17.177 Host is u…
阅读更多...
汽车内饰灯不亮问题修复

汽车内饰灯不亮问题修复

车内饰灯不亮问题修复 最近换后座阅读灯火光闪了一下&#xff0c;保险丝短路&#xff0c;导致车内所有灯光&#xff0c;包括前后座阅读灯、后备箱灯都不亮了。 因为是所有灯都不亮&#xff0c;所以排除灯泡问题&#xff0c;网上查了下大概率是保险丝烧了。于是查了自己更换保…
阅读更多...
从Android面试题目溯源-1、创建线程有那几种方式

从Android面试题目溯源-1、创建线程有那几种方式

概念 程序执行流的最小单位&#xff0c;处理器调度调度和分派的基本单位。 如何理解这个概念 如下图&#xff0c;可以简单类比吉他&#xff0c;六根弦代表六个线程&#xff0c;每个线程独立且单独运行&#xff0c;且持有上一个音的状态&#xff0c;每根手指可类比为一个CPU的…
阅读更多...
图书管理系统源码，图书管理系统开发，图书借阅系统源码整体功能演示

图书管理系统源码，图书管理系统开发，图书借阅系统源码整体功能演示

用户登录 基础资料 操作员管理 超期罚金设置 读者分类 读者管理 图书分类 图书管理 图书借还管理 图书借取 图书还去 图书借还查询 读者借书排行 用户登录 运行View目录下Login文件夹下的Index.csthml出现登录界面&#xff0c;输入用户名密码分别是admin密码admin12…
阅读更多...
Spark_Spark高阶特性

Spark_Spark高阶特性

wscg filter导致断链 Codegen 向量化 simdjson Orc Parquet 支持批量读取 spark本身对parquet支持比较好&#xff0c;因为parquet
阅读更多...
人民币已初步具备了国际使用的网络效应/首批疏解的在京部委所属4所高校雄安校区开工建设/墨茉点心局撤出北京市场

人民币已初步具备了国际使用的网络效应/首批疏解的在京部委所属4所高校雄安校区开工建设/墨茉点心局撤出北京市场

&#x1f396; 人民币已初步具备了国际使用的网络效应 ​ &#x1f384; 首批疏解的在京部委所属4所高校雄安校区开工建设 &#x1f386; 周鸿祎称互联网遭受攻击会使生活受到巨大影响 &#x1f387; 我国涉海距离最长城市燃气管线今日通气运行 &#x1f381; “零延时”快速通…
阅读更多...
osgFX扩展库-异性光照、贴图、卡通特效（1）

osgFX扩展库-异性光照、贴图、卡通特效（1）

本章将简单介绍 osgFX扩展库及osgSim 扩展库。osgFX库用得比较多,osgSim库不常用&#xff0c;因此&#xff0c;这里只对这个库作简单的说明。 osgFX扩展库 osgFX是一个OpenSceneGraph 的附加库&#xff0c;是一个用于实现一致、完备、可重用的特殊效果的构架工具&#xff0c;其…
阅读更多...
AIGC系列之：GroundingDNIO原理解读及在Stable Diffusion中使用

AIGC系列之：GroundingDNIO原理解读及在Stable Diffusion中使用

目录 1.前言 2.方法概括 3.算法介绍 3.1图像-文本特征提取与增强 3.2基于文本引导的目标检测 3.3跨模态解码器 3.4文本prompt特征提取 4.应用场景 4.1结合生成模型完成目标区域生成 4.2结合stable diffusion完成图像编辑 4.3结合分割模型完成任意图像分割 1.前言 …
阅读更多...
最新文章

Copyright @ 2022~2023