3. 无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是
"abc",所以其
长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是
"b"
,所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是
"wke"
,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,
"pwke"
是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
我的思路
这道题目我们采用双指针写法,定义一个left变量指向最长子串的首字母,定义right来从首字母往后遍历字符串。
设置两个遍历,第一个遍历用来遍历字符串,并将same置为0,第二个遍历用来遍历无重复字符的子串,当有重复字符时将same置为1,并让left+1。
遍历完一次子串后,更新子串长度max的信息。
让right++继续判断。
源码
int lengthOfLongestSubstring(char * s){ int i,j,max=0; int left=0,right=0,same=0; int len=strlen(s); for(i=0;i<len;i++) { same=0; for(j=left;j<right;j++) { if(s[j]==s[right]) { same=1; break; } } if(same==1) { left=j+1; } max=max>(right-left+1)?max:(right-left+1); right++; } return max; }
成功过关。
5. 最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
我的思路
这道题目我是采用中心扩散的方法,遍历每个字符(这个字符可能是一个,也可能是两个,一个就像aba,两个就像abba)来找它周围的回文子串.
从对应的子串开始不断地向两边扩展。如果两边的字母相同,我们就继续扩展,如果两边的字母不同,我们就停止扩展,因为在这之后的子串都不能是回文串了。
我们要找出最长的那个,所以要记得更新子串长度max。
源码
void extend(char*s,int left,int right,int*end,int*start) { if(left<0||right>=strlen(s)) { return;//越界就直接结束 } while(left>=0&&right<strlen(s)&&s[left]==s[right]) { left--; right++;//是回文子串时就循环 } if(right-left-1>(*end)) { *end=right-left-1;//更新最大子串的长度 *start=left+1; } return; } char * longestPalindrome(char * s){ int i,j; int *start=(int*)malloc(sizeof(int)); *start=0; int *end=(int *)malloc(sizeof(int)); *end=0; for(i=0;i<strlen(s);i++) { extend(s,i,i,end,start); extend(s,i,i+1,end,start); } s[*start+*end]='\0';//从回文子串开始输出 return s+*start;//输出到回文子串结束为止 }
成功过关。
后记
我的方法时间复杂度和空间复杂度可能比较高,如果大佬们有更好的方法,请在下面评论区不吝赐教,私信我就更好了,我们一起进步!