仁怀网站建设不好出手,网站排名提升工具,网站建设相关新闻,品牌网上旗舰店和商场质量一样吗滑动窗口 最小覆盖子串滑动窗口代码 上期经典 最小覆盖子串 难度 - 困难 原题链接 - 最小覆盖字串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 “” 。 注意#xff1a; 对于 t… 滑动窗口 最小覆盖子串滑动窗口代码 上期经典 最小覆盖子串 难度 - 困难 原题链接 - 最小覆盖字串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。 注意 对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。 示例 1 输入s “ADOBECODEBANC”, t “ABC” 输出“BANC” 解释最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。 示例 2 输入s “a”, t “a” 输出“a” 解释整个字符串 s 是最小覆盖子串。 示例 3: 输入: s “a”, t “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中 因此没有符合条件的子字符串返回空字符串。 提示 m s.length n t.length 1 m, n 1e5 s 和 t 由英文字母组成 滑动窗口 这个算法技巧的思路非常简单就是维护一个窗口不断滑动然后更新答案么. 该算法的大致逻辑如下 int left 0, right 0;while (left right right s.size()) {// 增大窗口window.add(s[right]);right;while (window needs shrink) {// 缩小窗口window.remove(s[left]);left;}
} 这个算法技巧的时间复杂度是 O(N)比字符串暴力算法要高效得多。 本题的解题思路 1、我们在字符串 S 中使用双指针中的左右指针技巧初始化 left right 0把索引左闭右开区间 [left, right) 称为一个「窗口」。 理论上你可以设计两端都开或者两端都闭的区间但设计为左闭右开区间是最方便处理的。因为这样初始化 left right 0 时区间 [0, 0) 中没有元素但只要让 right 向右移动扩大一位区间 [0, 1) 就包含一个元素 0 了。如果你设置为两端都开的区间那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素如果你设置为两端都闭的区间那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。 2、我们先不断地增加 right 指针扩大窗口 [left, right)直到窗口中的字符串符合要求包含了 T 中的所有字符。 3、此时我们停止增加 right转而不断增加 left 指针缩小窗口 [left, right)直到窗口中的字符串不再符合要求不包含 T 中的所有字符了。同时每次增加 left我们都要更新一轮结果。 4、重复第 2 和第 3 步直到 right 到达字符串 S 的尽头。 这个思路其实也不难第 2 步相当于在寻找一个「可行解」然后第 3 步在优化这个「可行解」最终找到最优解也就是最短的覆盖子串。左右指针轮流前进窗口大小增增减减窗口不断向右滑动这就是「滑动窗口」这个名字的来历。 下面画图理解一下needs 和 window 相当于计数器分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。 代码
public String minWindow1(String s, String t) {// 用于记录需要的字符和窗口中的字符及其出现的次数MapCharacter, Integer need new HashMap();MapCharacter, Integer window new HashMap();// 统计 t 中各字符出现次数for (char c : t.toCharArray())need.put(c, need.getOrDefault(c, 0) 1);int left 0, right 0;int valid 0; // 窗口中满足需要的字符个数// 记录最小覆盖子串的起始索引及长度int start 0, len Integer.MAX_VALUE;while (right s.length()) {// c 是将移入窗口的字符char c s.charAt(right);// 扩大窗口right;// 进行窗口内数据的一系列更新if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) 1);if (window.get(c).equals(need.get(c)))valid; // 只有当 window[c] 和 need[c] 对应的出现次数一致时才能满足条件valid 才能 1}// 判断左侧窗口是否要收缩while (valid need.size()) {// 更新最小覆盖子串if (right - left len) {start left;len right - left;}// d 是将移出窗口的字符char d s.charAt(left);// 缩小窗口left;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.get(d).equals(need.get(d)))valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时才能 -1window.put(d, window.get(d) - 1);}}}// 返回最小覆盖子串return len Integer.MAX_VALUE ? : s.substring(start, start len);}上期经典
leetcode59. 螺旋矩阵 II
