高新区规划建设局网站,开发一个app需要什么条件,wordpress免费音乐插件,WordPress grace7主题题目 ”最小覆盖子串“问题#xff0c;难度为Hard#xff0c;题目如下#xff1a; 给你两个字符串 S 和 T#xff0c;请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串#xff0c;则算法返回空串#xff0c;如果存在这样一个子串#xff0c;则可…题目 ”最小覆盖子串“问题难度为Hard题目如下 给你两个字符串 S 和 T请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串则算法返回空串如果存在这样一个子串则可以认为答案是唯一的。 比如输入 S ADBECFEBANCT ABC算法应该返回 BANC。 如果我们使用暴力解法代码大概是这样的 for (int i 0; i s.size; i) { for (int j i 1; j s.size; j) { if [i : j] 包含 t 的所有字母: 更新答案 } } 思路很简单但显然不是我们想要的。
滑动窗口思路分析 1.我们在字符串 S 中使用双指针中的左、右指针技巧初始化 left right 0把索引左闭右开区间 [left, right) 称为一个”窗口“。 2.先不断地增加 right 指针扩大窗口 [left, right)直到窗口中的字符串符合要求(包含了 T 中的所有字符)。 3.此时停止增加 right转而不断增加 left 指针缩小窗口 [left, right)直到窗口中的字符串不再符合要求(不包含 T 中所有字符了)。同时每次增加 left都要更新一轮结果。 4.重复第2和第3步直到 right 到达字符 S 的尽头。 第2步相当于在寻找一个”可行解“然后第3步在优化这个”可行解“最终找到最优解也就是最短的覆盖子串。左、右指针轮流前进 窗口大小增增减减窗口不断向右滑动这就是”滑动窗口“这个名字的来历。 下面画图理解一下这个思路。needs 和 window 相当于计数器分别记录 T 中字符出现次数和”窗口“中的相应字符的出现次数。 初始状态 增加 right直到窗口 [left, right) 包含了 T 中所有字符 现在开始增加 left缩小窗口 [left, right) 直到窗口中的字符串不再符合要求left 不再继续移动 之后重复上述过程先移动 right再移动 left······直到 right 指针到达字符串 S 的末端算法结束。现在来看看滑动窗口代码框架怎么用。 首先初始化 window 和 need 两个哈希表记录窗口中的字符和需要凑齐的字符 MapCharacter, Integer need new HashMap(); MapCharacter, Integer window new HashMap(); for (int i 0; i t.length(); i) { char key t.charAt(i); need.put(key, need.getOrDefault(key, 0) 1); } 然后使用 left 和 right 变量初始化窗口的两端不要忘了区间 [left, right) 是左闭右开的所以初始情况下窗口没有包含任何元素 int left 0, right 0, valid 0; while (right s.length()) { // 开始滑动 } 其中valid 变量表示窗口中满足 need 条件的字符个数如果 valid 和 need.size 的大小相同则说明窗口已满足条件已经完全覆盖了串 T。 现在开始套模板只需要思考以下4个问题 1.当移动 right 扩大窗口即加入字符时应该更新哪些数据 2.什么条件下窗口应该暂停扩大开始移动 left 缩小窗口 3.当移动 left 缩小窗口即移出字符时应该更新哪些数据 4.我们要的结果应该在扩大窗口时还是缩小窗口时进行更新 一般来说如果一个字符进入窗口应该增加 window 计数器如果一个字符移出窗口应该减少 window 计数器当 valid 满足 need 时应该收缩窗口收缩窗口的时候应该更新最终结果。 下面是完整代码
package SlidingWindow;import java.util.HashMap;
import java.util.Map;// leetcode 017 最小覆盖子串
public class MCS {public String slidingWindow(String s, String t) {MapCharacter, Integer need new HashMap();MapCharacter, Integer window new HashMap();for (int i 0; i t.length(); i) {char key t.charAt(i);need.put(key, need.getOrDefault(key, 0) 1);}int left 0, right 0, valid 0; // valid 表示窗口中满足 need 条件的字符个数// 记录最小覆盖子串的启始索引及长度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.getOrDefault(c, 0).equals(need.getOrDefault(c, 0))) { // window[c] need[c]valid;}}/*** debug 输出的位置***/System.out.println(window:( left , right ));/*********************/// 判断左侧窗口是否要收缩while (valid need.size()) { // window need shrink —窗口需要收缩// 在这里更新最小覆盖子串if (right - left len) {start left;len right - left;}// d 是将要移出窗口的字符char d s.charAt(left);// 左移窗口left;// 进行窗口内数据的一系列更新if (need.containsKey(d)) {if (window.getOrDefault(d, 0).equals(need.getOrDefault(d, 0))) {valid--;}window.put(d, window.getOrDefault(d, 0) - 1);}}}// 返回最小覆盖子串return len Integer.MAX_VALUE ? : s.substring(start, start len); // s.substring(start, start len) C 中的 s.substr(start, len)}public static void main(String[] args) {MCS mcs new MCS();String str mcs.slidingWindow(ADOBECODEBANC, ABC);System.out.println(str);}}
