第六天(滑动窗口)

无重复字符的最长子串

这个解法是一个大佬的做法非常牛逼,而且十分易懂,注释已做讲解.

int lengthOfLongestSubstring(char * s)
{
          
   
    int start = 0;
    int end = 0;
    int map[256] = {
          
   0};//本题字符串有英文数字符号和空格组成
    int maxlen = 0;//用来记录最长 
    map[(int)s[start]] = 1;
    while(s[end] != )
    {
          
   
        maxlen = maxlen > (end - start + 1)?maxlen:(end-start+1);//更新maxlen
        end++;
        while(map[(int)s[end]] != 0)//新加入的字符跟子串有冲突就一直start向后移,直到把冲突的字符吐出
        {
          
   
            map[(int)s[start]] = 0;//把start位置的吐出
            start++;
        }
        map[(int)s[end]] = 1;//把新加入的字符输入进去方便后面排查
    }
    return maxlen;
}

字符串的排列

其实这个题倒是还给我们简化了思路,因为只需要是排序之一就可以算成是子串,我们只需要记录s1内都有多少元素并记录他们都出现了几次,然后再通过把s2分成和s1相同的子串并进行比对是否和s1字符出现的次数相同,若果有任意一个相同就可以返回true了.

看注释应该就能看懂了 =.=

bool check(char* s2,int*map2,int start,int end)
{
          
   
    for(int i = start;i <= end;i++)
    {
          
   
        if(map2[(int)(s2[i]-a)])
        {
          
   
             map2[(int)(s2[i]-a)]--;
        }
        else//一旦map2内的数值为0就返回假.
        {
          
   
            return false;
        }
    }
    return true;
}
bool checkInclusion(char * s1, char * s2)
{
          
   
    int ss1 = strlen(s1),ss2 = strlen(s2);
    if(ss2<ss1)
    {
          
   
        return false;
    }
    int map1[26] ,map2[26];//建立两个是为了方便拷贝
    memset(map1,0,sizeof(map1));
    memset(map2,0,sizeof(map2));//都初始化为0是为了后面记录子串中的字符
    int start = 0;
    int end = ss1-1;//保证窗口大小是n,也就是s2中子串长度为n
    for(int i = 0;i<ss1;i++)
    {
          
   
        map1[(int)(s1[i]-a)]++;
        map2[(int)(s1[i]-a)]++;//记录出现的字符次数
    }
    while(s2[end] != )
    {
          
   
        if(check(s2,map2,start,end))//通过函数判断是否子串字符个数都相同
        {
          
   
            return true;
        }
        else
        {
          
   
            memcpy(map2,map1,sizeof(map1));//如果为假就重新吧map2回归到map1状态
            start++;
            end++;//移动窗口
        }
    }
    return false;
}