有没有网站可以做试卷,一套oa系统大概需要多少钱,网站做排名有用吗,桂林漓江景区门票#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 滑动窗口 求解思路 实现代码 运行结果 共勉 题目链接
76. 最小覆盖子串
⛲ 题目描述
给你一个字符串 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 105 s 和 t 由英文字母组成 求解思路实现代码运行结果 ⚡ 滑动窗口 求解思路
该题目我们通过滑动窗口来求解同时该题目需要维护俩个字符串的词频表(s是变化的t是固定的)然后右指针不断向右移动每次判断s是否覆盖t(通过维护的词频表来判断)如果可以那么判断是否满足长度最短如果最短更新并记录答案如果不是最短继续判断此时左指针右移缩小窗口继续后续的过程。实现代码如下所示 实现代码
class Solution {public String minWindow(String s, String t) {int max s.length();String ans ;int left 0;int n s.length();int[] cnt new int[128];int[] cnt1 new int[128];for (char c : t.toCharArray()) {cnt1[c];}for (int right 0; right n; right) {char c s.charAt(right);cnt[c];while (check(cnt, cnt1)) {if (right - left 1 max) {max right - left 1;ans s.substring(left, right 1);}cnt[s.charAt(left)]--;}}return ans;}public boolean check(int[] cnt, int[] cnt1) {for (int i 0; i cnt1.length; i) {if (cnt1[i] cnt[i])return false;}return true;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
