Leetcode 3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

题解:
初步想法是用一个map数组储存现在遍历的字符串里的字符,初定义maxlen=0,nowlen=0,然后从字符串最先开始遍历,每次遍历一个字符便开始判断是否map里它对应的值是0吗?若是,则令其为1(代表现在字符串里有它),nowlen ;若否,则判断nowlen和maxmlen的大小并作出变化,nowlen再清零从这个字符重新开始遍历直到遍历结束。
在实现的过程中,我先后发现了这些问题:

  1. 我没有考虑到全部都是不重复的情况
  2. 我之前的思路是遇到重复的就全部清零,再从这个字符继续(因为之前觉得没必要从当前遍历的字符串的第二个字符开始,觉得遍历后的结点绝对比之前的短,现在想想是完全错误的)
    因此针对这两种情况我做了一些修改,通过了,但是代码效率似乎不高。
    代码:
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0||s.length()==1) return s.length();
        int maxlen=0,nowlen=0,index=0,hindex=0;
        unordered_map<char,int> m;
        while(index<s.length()){
            if(m[s[index]]==0){  //index号字符和之前的未重复
                m[s[index]]=1;
                nowlen  ;
                index  ;
            }
            else{
                if(nowlen>maxlen) maxlen=nowlen;
                nowlen=0;
                m.clear();
                hindex  ;
                index=hindex;
            }
        }
        if(nowlen>maxlen) maxlen=nowlen;
        return maxlen;
    }
};

在很多OJ上是不会提供给你具体的测试样例的,所以在写之前要想完全全部的情况,为了应对未来未知情况。

if(nowlen>maxlen) maxlen=nowlen;
这一句可以用max()函数来代替。

去看了看其他大神的代码并理解了一下思想:
我发现了一个核心点:下一次开始的子字符串头从哪开始?
其他的代码很妙的一点是,直接把字符能换算成整数这一点利用上,存在一个数组内(这一点我是用map实现的),而这里设计特别巧妙,通过本次子序列往后遍历,找到第一个与本次序列停止的字符重复的字符,并从这个字符的下一个字符开始下一次的子序列.

于是我再次做了修改,将此思想运用到我的代码中:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0||s.length()==1) return s.length();
        int maxlen=0,nowlen=0,index=0,hindex=0;
        unordered_map<char,int> m;
        while(index<s.length()){
            if(m[s[index]]==0){  //index号字符和之前的未重复
                m[s[index]]=1;
                nowlen  ;
            }
            else{
                maxlen=max(maxlen,nowlen);
                while(s[hindex]!=s[index]){
                    m[s[hindex]]=0;
                    hindex  ;
                }
                hindex  ;
                nowlen=index-hindex 1;
            }
            index  ;
        }
        maxlen=max(maxlen,nowlen);
        return maxlen;
    }
};

果然快了很多。来源:https://www.icode9.com/content-4-897701.html

(0)

相关推荐

  • 「八大排序算法」16张图带你搞懂基数排序

    前言 在排序算法中,大家可能对桶排序.计数排序.基数排序不太了解,不太清楚其算法地思想和流程,也可能看过会过但是很快就忘记了,但是不要紧,幸运的是你看到了本篇文章.本文将通俗易懂的给你讲解基数排序. ...

  • C#几个经常用到的字符串截取

    一. 1.取字符串的前i个字符 (1)string str1=str.Substring(0,i); (2)string str1=str.Remove(i,str.Length-i); 2.去掉字符 ...

  • LeetCode之Longest Common Prefix

    LeetCode之Longest Common Prefix

  • ​LeetCode刷题实战260:只出现一次的数字 III

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战258:各位相加

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战256:粉刷房子

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战262:行程和用户

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • leetcode刷题笔记-234. 回文链表(java实现)

    题目描述 请判断一个链表是否为回文链表. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 来源:力扣(LeetCo ...

  • ​LeetCode刷题实战255:验证前序遍历序列二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战263:丑数

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...