隔壁组来了个新OD,据说是清华姚班的。。

科技   2024-12-10 15:15   广东  

大家好,我就是那个在B站讲算法的「华南溜达虎」。

今天在脉脉看到一位华为的同学说隔壁组来了个新od,辽宁理科状元,还是清华姚班的。楼主专门去确认了一下当年的姚班名单,确实是在里面。

评论区大部分脉友觉得不可思议,简直离谱,在质疑行情都差到这个地步了吗?姚班出来去其他大厂还不是随便进?也有脉友猜测可能是背了大厂的竞业协议来od过渡一下。还有脉友表示就算人家进了od也能立马转正,并且跳槽出去依旧抢手,od的履历丝毫不影响他那镶了金边的学历被大厂hr一眼看中。

最近虎哥利用业余时间在B站讲算法,id「华南溜达虎」,我已经把算法面试高频题目列表blind75中的题目讲了一遍,力扣hot100也快讲完了,一个视频五分钟左右,利用空闲时间就把算法学会了,对跳槽找工作升职加薪甚至对考研都有帮助,感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深,清晰明了,下面是一小部分评论截图。

言归正传,今天我们来分享一道高频面试题「无重复字符的最长子串」。

题目描述

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

输入:一个字符串s
输出:s的无重复字符最长子串的长度
举例:s = "abcabcbb", 那么其无重复字符的最长子串为"abc", 所以返回值是3。

思路解析

基本上有点编程基础的同学都能想到一种暴力的算法,两个for循环找出所有的子串,针对每个子串去判断是否有重复字符,这样的时间复杂度太高了,很显然这并不是面试官想要的答案。

下面介绍一种基于 滑动窗口 的方式来解此题。所谓滑动窗口,其实就是由两个索引维护一个区间,满足一定条件时会动态的去调整这个区间。非常像计算机网络里面tcp协议栈里所用到的滑动窗口算法。这里的两个索引的决定了滑动窗口的起点和终点,始终保持滑动窗口中的元素是不重复的,这题就变成了找到包含非重复元素的最长窗口

定义left = 0right = 0,结果保存到res, 统计窗口中字符的集合u_set,区间[left, right]即滑动窗口的区间。

问题的关键就是左右边界如何滑动,窗口滑动策略如下:

  1. 如果s[right]不在u_set中,把s[right]加入到u_set中并更新结果res = max(res, right - left + 1)right向右滑动,直到s[right]u_set中。
  2. 如果s[right]u_set中,u_set删除s[left]left向右滑动,直到s[right]不在u_set中。

根据上面的策略我们就可以获得以字符串s任意位置为右边界(枚举满足条件的右边界)的所有候选窗口,只需要把其中最长的一个窗口的长度返回即可。

看到这里有些同学可能还是不大理解,文字描述的比较抽象,我特意根据一个简单的例子画了个流程图来帮助理解。

比如给定s="abcac",其大致流程如图所示:

下面我们给出c++和python两种代码实现。

C++代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        unordered_set<char> u_set;
        int res = 0;
        int len = s.length();
        int cur_window = 0//当前窗口大小
        for (int left = 0, right = 0; right < len; ++right) {
            while (left < right && u_set.count(s[right])) {
                //s[right]已经在u_set中,窗口区间[left,right]中存在重复的元素
                //移动left直到窗口区间[left,right]中不存在重复元素
                u_set.erase(s[left]); 
                ++left;
                --cur_window;
            } 
            u_set.insert(s[right]);
            ++cur_window;
            res = max(res, cur_window);  
        } 
        return res;
    }
};

python代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        u_set = set()
        res = 0
        cur_window = 0  # 当前窗口大小
        left = 0  # 初始化左指针
        for right in range(len(s)):
            while left < right and s[right] in u_set:
                # s[right] 已经在 u_set 中,窗口区间 [left, right] 中存在重复的元素
                # 移动 left 直到窗口区间 [left, right] 中不存在重复元素
                u_set.remove(s[left])
                left += 1
                cur_window -= 1
            u_set.add(s[right])
            cur_window += 1
            res = max(res, cur_window)
        return res

复杂度分析

时间复杂度: 不要看到代码用了一个for嵌套一个while就以为时间复杂度是O(n2)leftright都是不会回头的两个索引,各自最多只遍历一遍字符串,unordered_set的查找效率一般是O(1),最坏的情况是O(n)这种情况一般是数据量巨大,存在很多哈希冲突,基本上退化成了链表。由于我们字符集大小也就几百个,不会出现这种最坏的情况。故总的时间复杂度为O(n)n为字符串长度。

空间复杂度: 用了三个int型变量,一个setset的最大元素个数为字符集的个数,所以空间复杂度为3 * O(1) + O(m) = O(m)m为字符集的大小。

号外

经常使用leetcode会员的同学可以使用我的优惠通道啦!

https://leetcode.cn/premium/?promoChannel=ldtiger ,年度会员有效期比官网多俩月,季度会员有效期比官网多两个星期,还有专属福利,需要的读者朋友可以找我了解。

今天的分享就到这里,希望大家能有所收获!


复旦毕业在OD干了两年,想重开了。。

离谱了,华为od开始卡年龄了。。

应届校招误拿ssp,因太菜惶恐不安。。

清华毕业,拿了华为和烟草局的offer,好纠结。。

拼多多开了68w,我却犹豫了。。

编程网事
曾就职于BAT的互联网大厂程序员。个人网站:ldtiger.com
 最新文章