Loading...
墨滴

在IT中穿梭旅行

2021/09/13  阅读:67  主题:自定义主题1

字节1面:无重复字符的最长子串

大家好,我是土哥。

作为一名大数据算法工程师,需要有一些算法功底,但是学习算法又非常枯燥,冰冷的 文字+代码 往往使大部分读者在学习算法的道路上半途而废。

今天呢,土哥就用 漫画+动图 的风格让我的读者轻松、愉快的学习算法,毕竟

故事

今天,小笨猪 阿土 收到了字节跳动的一面邀请邮件,约定3天后面试。

这可把 阿土 高兴坏了,但是 阿土的算法水平比较差,他听说字节跳动每轮面试必考算法,所以心情很忐忑。

这个时候,他的好朋友小美猪 阿梅 来找她玩耍,看到小笨猪闷闷不乐,于是问起了缘由,当得知字节跳动每轮都考算法的时候,阿梅说,不要担心,我们现在就开始刷代码,正好我今天刚做了一道题,可以考考你。

题目描述:

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

示例:
输入: s = "abcabcbb"
输出: 3 

输入: s = "bbbbb"
输出: 1

阿土看了看题目,这个?想了好几分钟,没想出答案。

题目解析

阿梅看到小笨猪一直没有想出来,于是开始给小笨猪讲解:

1、题目思路

这道题主要用到思路是:滑动窗口

什么是滑动窗口?

其实就是一个队列,比如例题中的 pwwkew,进入这个队列(窗口)为 pw 满足题目要求,当再进入w,队列变成了 pww,这时候不满足要求。所以,我们要移动这个队列!

如何移动?

我们只要从队列的左边开始将元素移出,直到满足题目要求!

一直维持这样的队列,找出队列出现最长的长度时候,求出解!

时间复杂度:O(n)

2、步骤

  1. 可以定义一个map数据结构存储(k,v),其中key为字符,value为字符的下标;
  2. 我们定义不重复子串的开始位置为start,结束位置为end. start 刚开始不动,end向后移动;
  3. end遇到重复字符时,将start放在上一个重复字符位置的后一位,同时记录最长的长度max;
  4. 通过hashmapkey来判断重复字符,用value来记录该字符的下一个不重复的位置。

刚开始,startend 都处于下标0max初始定义为0hashmap中没有存放keyvalue

通过for循环,从end0 开始遍历,判断第1个字符phashmap中没有包含p,这时将p作为key存入map,下标0存入value中。 max =Math.max(max,end-start +1) =1

继续执行,end = end+1 = 1如下图:

判断第2个字符w,hashmap中没有包含w,这时将w作为key存入map,下标1存入value中。

max =Math.max(max,end-start +1) =2.

继续执行, end = 1+1 = 2。如下图:

判断第3个字符w``,hashmap中包含w,这时计算start,将start放在上一个重复字符位置的后一位,即上一个w下标为1的后一位,所以 start = Math.max(start,map.get(ch)+1)=2。

然后在map中更新w下标为2,重新计算max = Math.max(max,end-start +1) =2, 继续执行,end = 2+1 = 3。如下图:

判断第4个字符k,hashmap中没有包含k,这时将k作为key存入map,下标3存入value中。max =Math.max(max,end-start +1) =2,继续执行,end = 3+1 = 4。 如下图:

判断第5个字符e,hashmap中没有包含e,这时将作为key存入map,下标4存入value中。max =Math.max(max,end-start +1) =3, 继续执行,end = 4+1 = 4。 如下图:

判断第6个字符w,hashmap中包含w,这时计算start,将start放在上一个重复字符位置的后一位,即上一个w下标为2的后一位,所以start = Math.max(start,map.get(ch)+1)=3

然后在map中更新w下标为5,重新计算max = Math.max(max,end-start +1) =3, 继续执行,end = 5+1 = 6。如下图:

判断end=6时,超出字符串范围,程序结束,所以最终字符的长度为3

3、动画如下:

代码实现

java实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
// (1) 先创建map数据结构存储(k,v),其中key为字符,value为字符的下标.
     HashMap<Character,Integer> map = new HashMap<>();  
        //(2)定义不重复子串的开始位置为start,结束位置为end. start 刚开始不动,end向后移动    
        int max =  0 , start = 0;
        //(3) 遍历字符串
        for(int end = 0 ; end < s.length() ; end++){
            // (4)取出每个字符
            char ch = s.charAt(end);
            // (5)判断字符,hashmap中没有是否包含该字符
            if (map.containsKey(ch)){
            //  (6)包含字符,将start放在上一个重复字符位置的后一位。
                start = Math.max(start,map.get(ch)+1);
            }
            // (6)计算max长度
            max = Math.max(max,end -start+1);
            //(7)将字符作为key存入map,下标存入value中
            map.put(ch,end);

        }
        // (8)程序执行结束,返回无重复子串最大长度。
        return max;
    }
}

c++实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0return 0;
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++){
            while (lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
    }
        return maxStr;
        
    }
};

python3实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

土哥的代码均已经通过Leetcode在线测评,保证代码是没有问题。原创不易,各位觉得文章不错的话,不妨点赞(在看)、留言、转发三连走起!谢谢大家!

最近整理了一份计算机类的书籍,包含python、java、大数据、人工智能、算法等,种类特别齐全。 获取方式:关注公众号:3分钟秒懂大数据,回复:福利,就可以获得这份超级大礼!

在IT中穿梭旅行

2021/09/13  阅读:67  主题:自定义主题1

作者介绍

在IT中穿梭旅行