首页 > 其他分享 >双指针做题总结2(76. 最小覆盖子串)

双指针做题总结2(76. 最小覆盖子串)

时间:2024-04-04 18:23:16浏览次数:30  
标签:子串 pre start int 76 map mp 指针

76.最小覆盖子串

 

思路:

双指针滑动窗口问题,指针的移动条件是双指针的核心。

 

反思:

1、考虑右指针已经移动到最右端,无法继续移动的情况。(flag1的思路)
2、用map.empty()是要千万注意:map[key]相当于往map中添加元素

 

代码:

class Solution {
public:
    unordered_map<char, int> mp;
    bool empty(){
        for(auto it = mp.begin(); it != mp.end(); it++){
            if(it -> second > 0) return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        vector<vector<int>> ans;
        int index[100005]={0};
        for(int i = 0; i < t.size(); i++){
            mp[t[i]]++;
        }
        int pre = -1, start = -1;
        for(int i = 0; i < s.size(); i++){
            if(mp[s[i]]){
                if(pre == -1) start = i;
                if(pre != -1) index[pre] = i;
                pre = i;
            }
        }
        if(start == -1){
            return "";
        }
        int l = start, r = start;
        bool flag1 = true; 
        while(l <= r){
            while(!empty() && flag1){
                mp[s[r]]--;
                if(index[r] == 0){
                    flag1 = false;
                    break;
                }
                if(!empty())r = index[r];
            }
            // cout<<l<<" "<<r<<" "<<mp['a']<<" "<<mp['e']<<" "<<mp['c']<<endl;
            if(empty()){
                ans.push_back({l, r});
                mp[s[l]]++; 
                if(index[l] == 0) break;
                l = index[l]; 
            }else{
                break;
            }
            if(!empty() && index[r] != 0){
                r = index[r];
            }
        }
        int minn = 100005, minl = -1 , minr = -1;
        for(int i = 0; i < ans.size(); i++){
            int rr = ans[i][1], ll = ans[i][0];
            if(rr - ll < minn){
                minn = rr - ll;
                minl = ll;
                minr = rr;
            }
        } 
        if(minl == -1){
            return "";
        }else{
            return s.substr(minl, minr - minl + 1);
        }
    }
};

 

标签:子串,pre,start,int,76,map,mp,指针
From: https://www.cnblogs.com/yccy/p/18114451

相关文章

  • luoguP1102-双指针
    题目链接:P1102A-B数对-洛谷|计算机科学教育新生态(luogu.com.cn)利用单调性求解双指针解法:排序构造出区间单调,则若存在目标值B,B在序列中一定为连续区间,此时通过双指针l和r,此时维护一段区间:有S[L]大于S[I]-C,S[R]大于等于S[I]-C,此时我们枚举每一位,若存在A......
  • 代码随想录DAY1 | 二分,双指针移除元素
    代码随想录DAY1|二分,双指针移除元素题目描述给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且......
  • P1776 宝物筛选
    知识点:多重背包,也就是一个物品有多个,然后求总价值。算法竞赛上的板子题目:链接:https://www.luogu.com.cn/problem/P1776介绍二进制拆分优化就是把几个完全相同的拆成1+2+4+...+2^n+mod,然后再进行dp的办法代码:重点在new_n,new_w,new_m这几个#include<iostream>#include<vec......
  • 【目标检测数据集】鼠标数据集1876张VOC+YOLO格式
    鼠标,作为计算机的重要外接输入设备,其形状酷似老鼠,因此得名。它不仅是计算机显示系统纵横坐标定位的指示器,更是简化计算机操作的关键工具。通过鼠标,用户可以轻松控制屏幕上的光标,实现点击、拖拽、滚动等操作,使计算机的使用更加简便快捷。鼠标的种类繁多,有机械鼠标、光电鼠标、......
  • C语言——深入理解指针
    1.数组名的理解实数组名就是数组⾸元素(第⼀个元素)的地址,但是有两个例外:•sizeof(数组名),sizeof中单独放数组名,这⾥的数组名表⽰整个数组,计算的是整个数组的⼤⼩,单位是字节•&数组名,这⾥的数组名表⽰整个数组,取出的是整个数组的地址(整个数组的地址和数组⾸元素的......
  • 第十四届省赛大学B组(C/C++)子串简写
    原题链接:子串简写程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n,Kubernetes 简写成 K8s,Lanqiao 简写成 L5o 等。在本题中,我们规定长度大于等于 K 的字......
  • 37.深⼊理解指针(2)
    1.数组名的理解intarr[10]={1,2,3,4,5,6,7,8,9,10};int*p=&arr[0];这⾥我们使⽤&arr[0]的⽅式拿到了数组第⼀个元素的地址,但是其实数组名本来就是地址,⽽且是数组⾸元素的地址,我们来做个测试。#include<stdio.h>intmain(){intarr[10]={1,2,3,4,5,6,......
  • C语言------------指针
    指针的类型:指针:在学习指针之前,要有一个认知,那就是指针==地址;指针的基本使用:​​这里要注意三点:1.*标识符—————只产生在指针变量定义或声明的时候;2.指针的类型要和被赋值的类型一致;3.*p=*(p)这2个的意思是一样的;在scanf中,不能使用指针进行;上面的是最基......
  • P8776 [蓝桥杯 2022 省 A] 最长不下降子序列
    1.首先想到的做法设up_len[i]为以a[i]为结尾的最长不下降子序列的长度,down_len[i]表示以a[i]为开始的最长不下降子序列的长度。在求pre的过程中记录下额外信息:down_pre[i]表示在求down_len[i]的过程中,i是由哪个点转移过来的;得到dp的转移方程:if(down_pre[i])ans......
  • Linux C++ 015-对象模型和this指针
    LinuxC++015-对象模型和this指针本节关键字:Linux、C++、对象模型、this指针相关库函数:成员变量和成员函数分开存储1、在C++中,类内的成员变量和成员函数分开存储,只有非静态成员变量才属于类的对象上;2、C++编译器会给每个空对象也分配一个字节的空间,是为了区分空对象占......