亲宝软件园·资讯

展开

C++ 无重复字符的最长子串 C++实现无重复字符的最长子串

IT-菜鸟 人气:0
想了解C++实现无重复字符的最长子串的相关内容吗,IT-菜鸟在本文为您仔细讲解C++ 无重复字符的最长子串的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++,无重复字符的最长子串,C++,无重复最长子串,下面大家一起来学习吧。

题目及要求:

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

提示:

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

原创代码:

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int begin=0;//每个当前子串的开头
        int end=0;//每个当前子串的末尾
        int value=0;//判断下一个字符是否属于当前子串
        int max=0;//记录历史字串的最大元素个数
        int now=0;//储存当前字串的元素个数
        string str;//代表当前字串
        if(s.size()==0)
        return 0;
        while(end<=(s.size()-1))
        {
            value=str.find(s[end],0);
            if(value!=-1)
            {
                str.erase(0,value+1);
                begin=end-(str.size()-value);
            }
            str.push_back(s[end]);
            now=str.size();
            max=now>max?now:max;
            end++;   
        }
        return max;
    }
};

 输出示例:
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。
示例 4:
输入: s = “”
输出: 0

代码思路:

首先:

定义变量

int begin=0;//每个当前子串的开头
int end=0;//每个当前子串的开头
int value=0;//判断下一个字符是否属于当前子串
int max=0;//记录历史字串的最大元素个数
int now=0;//储存当前字串的元素个数
string str;//代表当前字串

其次:
通过以下条件判断形参string s是否为空字符串

if(s.size()==0)
return 0;

再其次:
若形参string s不是空字符串,由于

int end=0;//每个当前子串的末尾

则用end来引入新元素,每判断一次新元素与当前子串的关系,则end++

最后:
若新元素与当前的关系表明新元素不与当前子串内的元素重复则直接将新元素加入子串,若新元素与当前的关系表明新元素与当前子串内的元素重复则将子串含有冲突元素的前半部分删除并将新元素加入到当前子串

反思所得:
在本次编程过程中我经常出现提示堆栈内存溢出的问题,之后发现是对形参string s是空字符串的情况没加以控制,在未来的编程中我会更加注意。
而且我还学会了利用条件运算符来记录记录历史字串的最大元素个数,即

max=now>max?now:max;

LeetCode链接:
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

加载全部内容

相关教程
猜你喜欢
用户评论