刷题第六天<滑动窗口>(跑路人笔记)

简介: 刷题第六天<滑动窗口>(跑路人笔记)

第六天(滑动窗口)

无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣(LeetCode)

image.png

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

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] != '\0')
    {
        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;
}

字符串的排列

567. 字符串的排列 - 力扣(LeetCode)


image.png


其实这个题倒是还给我们简化了思路,因为只需要是排序之一就可以算成是子串,我们只需要记录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] != '\0')
    {
        if(check(s2,map2,start,end))//通过函数判断是否子串字符个数都相同
        {
            return true;
        }
        else
        {
            memcpy(map2,map1,sizeof(map1));//如果为假就重新吧map2回归到map1状态
            start++;
            end++;//移动窗口
        }
    }
    return false;
}
目录
打赏
0
0
0
0
0
分享
相关文章
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
花了30天才肝出来,史上最全面Java设计模式总结,看完再也不会忘
Design Patterns: Elements of Reusable Object-Oriented Software(以下简称《设计模式》),一书由Erich Gamma、Richard Helm、Ralph Johnson和John Vlissides合著(Addison-Wesley,1995)。这四位作者常被称为“四人组(Gang of Four)”,而这本书也就被称为“四人组(或 GoF)”书。他们首次给我们总结出一套软件开发可以反复使用的经验,帮助我们提高代码的可重用性、系统的可维护性等,解决软件开发中的复杂问题。
203 0
算法 | 高楼丢鸡蛋(源自谷歌面试题)| 刷题打卡
算法 | 高楼丢鸡蛋(源自谷歌面试题)| 刷题打卡
201 0
算法 | 高楼丢鸡蛋(源自谷歌面试题)| 刷题打卡
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等