第六天(滑动窗口)
无重复字符的最长子串
这个解法是一个大佬的做法非常牛逼,而且十分易懂,注释已做讲解.
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）
其实这个题倒是还给我们简化了思路,因为只需要是排序之一就可以算成是子串,我们只需要记录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; }
