做好网站建设工作总结,网站建设牜金手指花总十四,网站更换主机需要怎么做,wordpress崩了欢迎关注点赞评论#xff0c;共同学习#xff0c;共同进步#xff01;
------持续更新蓝桥杯入门系列算法实例--------
如果你也喜欢Java和算法#xff0c;欢迎订阅专栏共同学习交流#xff01;
你的点赞、关注、评论、是我创作的动力#xff01;
-------希望我的文章…欢迎关注点赞评论共同学习共同进步
------持续更新蓝桥杯入门系列算法实例--------
如果你也喜欢Java和算法欢迎订阅专栏共同学习交流
你的点赞、关注、评论、是我创作的动力
-------希望我的文章对你有所帮助-------- 前言过年前后因为个人原因没有持续更新目前已经开学将会稳定更新各种算法题解4月份即是蓝桥杯竞赛了时不我待共同加油进步趁着我们年轻且充满希望努力吧 一、题目描述 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
示例 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 的子串中
因此没有符合条件的子字符串返回空字符串。 二、思路及题解 这题是力扣上的hard难度本人自己写的算法在最后一个测试用例无法通过显然是时间复杂度过高导致的超时于是便参考其他大佬的方法重新写了一个接下来讲讲我的思路。 1、本题是两个字符串进行匹配重复子串问题首先把两个字符串转化为字符数组toCharArray即可实现。 2、使用HashMap哈希表来统计每个字符出现的次数。 3、确定一个区间为[left,right的滑动窗口首先将字符数组t放入Target中如果匹配到相同的字母即将该字母添加到Window滑动窗口中即right窗口扩张的过程。 4、遍历后当滑动窗口中国的字母数量Valid与Target一致时即是符合条件的子串记录长度Len。 5、窗口开始移动left将首个字母进行剔除再次验证窗口是否符合条件不符合则Vaild-1。 6、直至再次母数量Valid与Target一致时进行子串长度比较最后窗口right触及边界则获得最短的子串。 三、参考代码 public String minWindow(String s, String t) {char[] T t.toCharArray();char[] S s.toCharArray();MapCharacter, Integer Window new HashMap();MapCharacter, Integer Target new HashMap();//匹配目标int left 0, right 0, start 0;int Valid 0, Len Integer.MAX_VALUE;//默认设为最大值for (char ch : T) Target.put(ch, Target.getOrDefault(ch, 0) 1);//将t字符串放入哈希表while (right s.length()) {char ch S[right];right;if (Target.containsKey(ch)) {Window.put(ch, Window.getOrDefault(ch, 0) 1);if (Target.get(ch).equals(Window.get(ch)))Valid;//匹配到相同字母累加计算}while (Valid Target.size()) {//当目标字母全部都包含在s中时if (right - left Len) {start left;Len right - left;}char d S[left];left;//窗口左移开始收缩if (Target.containsKey(d)) {Window.put(d, Window.get(d) - 1);if (Window.get(d) Integer.valueOf(Target.get(d))){Valid--;}}}}return Len Integer.MAX_VALUE ? : s.substring(start, start Len);} 发文不易恳请大佬们高抬贵手
点赞随手点赞是种美德是大佬们对于本人创作的认可
评论往来无白丁是你我交流的的开始
收藏愿君多采撷是大佬们对在下的赞赏
