76. 最小覆盖子串-滑动窗口法
窗口 最小 滑动 覆盖 子串 76
2023-09-14 09:06:53 时间
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
示例 2:
输入:s = “a”, t = “a”
输出:“a”
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
char * minWindow(char * s, char * t){
int r[128];//记录t中字母个数
int rt[128];
int i;
for(i=0;i<128;i++){
rt[i]=0;
r[i]=0;
}
i=0;
while(t[i]!='\0'){
r[t[i]-'A']++;
i++;
}
int len=i; //t的长度
int lent=len;
len=len*10;
char ps[len];
int index[len];
int po=0;//ps指针
int posize=0;
int size=0;//已统计的t中有效字母的数量
i=0;
int min =100000,min_index=-1,max_index=-1;
while(s[i]!='\0'){
int index_s=s[i]-'A';
if(r[index_s]!=0){
if(rt[index_s]<r[index_s]){
size++;//有效数据加一
rt[index_s]++;
ps[posize%len]=s[i];//将有效字母放入队列中
index[posize%len]=i;
posize=(posize+1)%len;//长度加一
// printf("si:%d %d ",size,i);
while(size==lent){
// printf("po i index %d %d %d ",po,i,index[po%len]);
int range=i-index[po%len];
if(range<min){
min_index=index[po%len];
max_index=i;
min=range;
}
char ch=ps[po%len];
rt[ch-'A']--;
if( rt[ch-'A']<r[ch-'A']){
size--;
}
po=(po+1)%len;//长度加一
}
}
else{
rt[index_s]++;
ps[posize%len]=s[i];//将有效字母放入队列中
index[posize%len]=i;
posize++;//长度加一
}
}
i++;
}
if(max_index==-1){
s[0]='\0';
return s;
}
s[max_index+1]='\0';
return s+min_index;
}
相关文章
- 使用layui弹框实现添加时,当添加成功之后如何进行关闭当前窗口刷新父页面的数据
- Java实现 LeetCode 567 字符串的排列(滑动窗口,处理区间内的字符数量)
- 获取窗口属性
- hive Spark SQL分析窗口函数
- MFC Windows 程序设计[217]之多样窗口示例展示(附源码)
- JavaFX弹出窗口和消息对话框代码示例
- JavaScript检测窗口是否滚动到底部
- Android创建窗口的过程
- 1509. 三次操作后最大值与最小值的最小差-快速排序+局部滑动窗口,力扣双百代码
- Qt中实现悬浮窗口
- MFC 设置窗口置顶显示
- MFC一一窗口控件随窗口大小进行自适应
- 在OpenCV里让窗口获得鼠标事件
- C# wpf 实现窗口靠近屏幕边缘自动吸附
- [ Windows 10 ] 任务栏按钮不显示正在打开的窗口了(打开任何程序任务栏图标按钮都不显示)
- Win10怎么隐藏文件资源管理器窗口左侧OneDrive图标