【LeetCode 训练营 3,5】无重复字符的最长子串+最长回文子串

简介: 【LeetCode 训练营 3,5】无重复字符的最长子串+最长回文子串

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;
}


成功过关。


018a5fe4d465ef73762abba8fd92068d_f2b87e71ecdc416094f12fc7309e7d44.png


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;//输出到回文子串结束为止
}

成功过关。

e8e08d74b325aa63e0a6b6dd2789a40a_a363ea66a9e44db09dd09233746141cd.png


后记


我的方法时间复杂度和空间复杂度可能比较高,如果大佬们有更好的方法,请在下面评论区不吝赐教,私信我就更好了,我们一起进步!


 2bb07965b4b08461e9d6a456d4551dae_a48b467cc4ed4dd884f91916cd012343.jpeg


相关文章
|
22天前
Leetcode第五题(最长回文子串)
这篇文章介绍了解决LeetCode第五题“最长回文子串”问题的一种方法,使用了中心扩展法来寻找给定字符串中的最长回文子串。
30 0
|
22天前
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
54 0
Leetcode第三题(无重复字符的最长子串)
|
3月前
|
Python
【Leetcode刷题Python】5. 最长回文子串
LeetCode 5题 "最长回文子串" 的Python解决方案,使用动态规划算法找出给定字符串中的最长回文子串。
43 3
|
3月前
|
算法
LeetCode第5题最长回文子串
该文章介绍了 LeetCode 第 5 题最长回文子串的解法,通过分析回文子串的特点,使用动态规划的思想,用二维数组记录字符串是否为回文串,从后往前遍历找子串,减少重复判断,最终找到最长回文子串,并总结了解题时通过举例推导找规律的思路。
LeetCode第5题最长回文子串
|
3月前
|
算法
LeetCode第3题无重复字符的最长子串
该文章介绍了 LeetCode 第 3 题无重复字符的最长子串的解法,通过使用 HashSet 记录不重复的子元素,以每个字符开头遍历字符串,遇到重复字符则重新计算,最终找到最长子串,同时提到可以考虑使用 HashMap 降低复杂度。
LeetCode第3题无重复字符的最长子串
|
5月前
|
存储 算法 测试技术
力扣经典150题第三十三题:最小覆盖子串
力扣经典150题第三十三题:最小覆盖子串
34 1
|
4月前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
31 0
|
5月前
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
25 0
|
5月前
|
存储 算法 程序员
力扣经典150题第三十一题:无重复字符的最长子串
力扣经典150题第三十一题:无重复字符的最长子串
29 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行