太可惜了,四面字节跳动,我的offer竟被一道“算法题”给拦截了

简介: 算法,在行业里越来越重要,一线互联网公司也非常注重算法,所以在面试时基本上都有涉及到。字节跳动是出了名的爱问算法题,几乎每一面都要问到算法。实际上,现在很多公司都会问算法,尤其是对于应届生来说,要求更高,所以想要进大厂,搞定算法是很重要的。

前言

算法,在行业里越来越重要,一线互联网公司也非常注重算法,所以在面试时基本上都有涉及到。字节跳动是出了名的爱问算法题,几乎每一面都要问到算法。实际上,现在很多公司都会问算法,尤其是对于应届生来说,要求更高,所以想要进大厂,搞定算法是很重要的。

前段时间,我就去面了一次字节跳动,好不容易进到第四面,眼看offer就要拿到手了,可惜竟然被一道“算法题”给拦截了,与字节的offer失之交臂。今天就分享一下这道算法题,让我们好好聊一聊,怎么搞定字节跳动的面试吧!

拦截我的offer,竟是这道算法题

给定一个只包括 '(',')'的字符串,判断字符串是否有效。注:空字符串属于有效字符串

示例 1:
输入: "(())"
输出: true
 实例 2:
 输入: "())("
输出: false

第一眼看到这道题,我去,这么简单,稳了(因为一面的时候,刚刚被面试官怼过勇者斗恶龙的DP题,在 leetcdoe 属于 hard 级别)。

于是我也不假思索直接用来解决了,相信 99% 都会用栈解决吧?这里我稍微说一下过程吧,步骤如下:

1、在遍历字符串的过程中,遇到 "(" 就让它入栈,遇到 ")" 就判断下栈里面有没有 "(" :

(1)、如果有,则把处于栈顶的 "("  弹出,相当于和 ")" 进行匹配,然后继续往后遍历字符串
(2)、如果没有,则匹配失败。相当于字符串的最前面出现了 ")",显然这是不合理的。

2、当字符串遍历完成,判断栈是否为空,如果为空则表示字符串有效,否则无效。

为了兼顾小白,我该给你们画了个图演示,,,,我太良心了。

代码如下所示:

public static boolean isValid(String s){
    if(s == null || s.length() < 1)
        return true;
    int n = s.length();// 字符串长度
    // 创建一个栈来装字符
    Stack<Character> stack = new Stack<>();
    // 遍历字符串
    for(int i = 0; i < n; i++){
        // 获取字符串的第 i 个字符
        char c = s.charAt(i);
        if(c == '('){
            stack.push(c);
        }else{
            if(stack.isEmpty())
                return false;
            else
                stack.pop();
        }
    }
    // 判断是否为空
    if(stack.isEmpty())
        return true;
    return false;
}

接着面试官说我这道题的空间复杂度是 O(n),问我能优化一下吗?

说实话,如果你做过 leetcode 的第 20 题,可能你的脑子会被定向也不一定,因为那道题用栈来处理就是最优解的了。不过这道题属于简化版,其实可以把空间复杂度优化成 O(1),大家可以想一下哦。

由于我们栈里面存放的都是同一种字符 "(" ,其实我们可以用一个变量来取代栈的,这个变量就记录 "(" 的个数,遇到 "(" 变量就加 1,遇到 ")" 变量就减 1,栈为空就相当于变量的值为 0。

当时脑子有点不知为啥,就马上想到这个方法了,于是一分钟就修改好了代码,如下:

public static boolean isValid(String s){
    if(s == null || s.length() < 1)
        return true;
    int n = s.length();// 字符串长度
    // 用来记录遇到的 "(" 的个数
    int sum = 0;
    // 遍历字符串
    for(int i = 0; i < n; i++){
        // 获取字符串的第 i 个字符
        char c = s.charAt(i);
        if(c == '('){
            sum++;
        }else{
            if(sum == 0)
                return false;
            else
                sum--;
        }
    }
    return sum == 0 ? true : false;
}

这样子的话,时间复杂度为 O(n),空间复杂度为 O(1)。

接着面试官就继续就这道题继续加大难度,问题改为如下

给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

其实这道题就是 leetcode 的原题,第 32 题,难度为 hard。

这道题由于我之前做过,微微一笑,假装用严肃的表情思考一下,然后马上给出了思路,刚开始我是用暴力法的。

1、暴力法

暴力法其实很简单,就是最开始把第一个字符当做最长有效括号的首字符来遍历字符串,接着把第二个字符当做最长有效括号的首字符来遍历字符串,接着把第三个字符......

例如对于 s = "( ) ) ( ( ) )"。

把第一个字符作为首字符,则 max = 2 (遇到第三个字符 ')' 就匹配不了了) 把第二个字符作为首字符,则 max = 0 (一开始就是 ')',显然啥也匹配不了) 把第三个字符作为首字符,则 max = 0 把第四个字符作为首字符,则 max = 4 ..... 这种做法的时间复杂度为 O(n^2),空间复杂度为 O(1)

基本上面那道题一样,只是做了 n 次遍历。

接着面试官问,还能优化吗?

早就知道会问优化的了,我自己之前也做过这道题,于是假装思考了一下,马上给出了优化。

2、优化

这道题的优化版本我们仍然是用栈来做,不过入栈的时候,不是让 "(" 入栈,而是让 "(" 的下标入栈。步骤如下:

1、先把 -1 放入栈内。(至于为什么?看到后面你就知道了) 2、、对于遇到的每个 '(' ,我们将它的下标放入栈中。 3、对于遇到的每个 ‘)’ ,我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差,得出当前有效括号字符串的长度

通过这种方法,我们继续计算有效子字符串的长度,并最终返回最长有效子字符串的长度。

看不懂?没事,我弄个例子画几个图,例如 s = "( ) ) ( ( ) )",并且用变量 max 来保存最长有效字符串的程度,i 表示当前字符串的下标

0、初始化:max = 0; i = 0。-1 放入栈内

1、i = 0,s[i] = '(',下标 i = 0 入栈

2、i = 1,s[i] = ')',出栈; i - 栈顶元素 = 1 - (-1) = 2,此时 max = 2

3、i = 2,s[i] = ')',出栈;这个时候要注意:由于 -1 出栈后,栈顶没有元素了,所以这个时候我们必须把 ')' 的下标入栈,相当于最开始的初始化。

4、i = 3,s[i] = '(',入栈;

5、i = 4,s[i] = '(',入栈;

6、i = 5,s[i] = ')',出栈;i - 栈顶 = 5 - 3 = 2;此时 max = 2;

7、i = 6,s[i] = ')',出栈;i - 栈顶 = 6 - 2 = 4;此时 max = 4;

8、遍历结束,最长有效括号为 4。

看不大懂?没事,看下代码加深理解了,代码如下:

public int longestValidParentheses(String s) {
    int max = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
        //下标入栈
            stack.push(i);
        } else {
        // 出栈
            stack.pop();
            // 看栈顶是否为空,为空的话就不能作差了
            if (stack.empty()) {
                stack.push(i);
            } else {
            // i - 栈顶,获得档期有效括号长度
                max = Math.max(max, i - stack.peek());
            }
        }
    }
    return maxans;
}

这种做法的时间复杂度为 O(n),空间复杂度为 O(n),能想到用栈来处理,算是很不错的了。

最后一击

我以为我给出这个解法算是可以的了,面试官应该换一道题的了,然后,面试官又来了一句:还能再优化吗?。这个时候我陷入了沉思.......

看文章的各位大佬们可以想一想在空间上是否还能优化,因为在时间上是不可能优化的了。

想了一会,居然不可以用栈,优化的方案肯定是类似于上面那道题一样,用记录数量的变量来代替栈,然后就被我想出了,具体如下:

实际上,这道题仍然可以像上面那样,用变量来代替栈来优化,不过这个时候我们需要两个变量,我们假设变量为 left 和 right。

我们在从从左到右遍历字符串的过程中,用 left 记录 '(' 的数量,用 right 记录 ')' 的数量。并且在遍历的过程中:

1、如果 left == right,显然这个时候 right 个 ')' 都将一定能够得到匹配。所以当前的有效括号长度为 2 * right。然后更新 max。

2、如果 left < right,显然这个时候部分 ')' 一定得不到匹配,此时我们把 left 和 right 都置为 0。

当遍历完字符串,我们是否就得到最大长度的有效括号了呢?大家可以想一下

答是不可以的,我们还需要从右到左遍历计算一下。

为什么呢?

因为实际上 '(' 和 ')' 其实是等价的,为什么就不可以倒过来遍历计算呢?所以,千万别忽略了哈。

最后的代码如下:

public int longestValidParentheses(String s) {
    int left = 0, right = 0, max = 0;
    // 从左到右
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            max = Math.max(max, 2 * right);
        } else if(right > left){
            left = right = 0;
        }
    }
    left = right = 0;
    // 从右到左
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            max = Math.max(max, 2 * left);
        } else if (left > right) {
            left = right = 0;
        }
    }
    return max;
}

这种做法的时间复杂度为 O(n),空间复杂度为 O(1)。

注意,友情提醒:本篇文章内容主题为“算法”,需要楼主这次字节跳动面试的全部4面真题含答案的朋友,可以点击此处来获取就可以了!

复习算法,再战字节跳动

对于字节跳动,心中总是有一股执念的,所以之后的计划是打算二战字节跳动,但要想过算法这关,还是得需要花一些心思的,所以算法的复习就尤为重要了。对于算法的学习,我主要是阅读一些书籍和文档资料,具体如下:

(1)LeetCode中文版

(2)算法的乐趣

(3)算法

更多算法资料:

以上这些算法资料,均可以免费分享,可以点击此处来获取就可以了!

总结

算法是需要大量练习的,首先我们需要选择基本比较好的教材来加强我们的理论知识,然后需要在这里理论基础上进行上机练习。

如果你也对算法的学习感兴趣,想要获取以上算法的相关资料,可以点击此处来获取就可以了!

相关文章
|
8月前
|
负载均衡 算法 应用服务中间件
面试题:Nginx有哪些负载均衡算法?Nginx位于七层网络结构中的哪一层?
字节跳动面试题:Nginx有哪些负载均衡算法?Nginx位于七层网络结构中的哪一层?
162 0
|
8月前
|
设计模式 算法 Java
京东Java高开岗三面算法+数据库+设计模式,复习1个月成功拿offer
京东高级java现场三面,包含:算法、数据库、设计模式、java高级等,尾部有最全BAT高级java面试题目和答案福利,想要的就快来领走吧~(领取方式见文末)
|
8月前
|
人工智能 算法 程序员
这本“算法宝典”讲得透彻,完全掌握后,我竟拿到字节跳动offer
字节跳动,相信大家都已经对这家公司很熟悉了,尤其是近几年来,对它的认识也在不断刷新,它惊人的发展速度确实让行业内人刮目相看,如今很多年轻人也想要挤进字节跳动,它越来越火热,自然也就越来越难进了!
|
8月前
|
消息中间件 算法 Java
三面“有赞”Java岗斩获offer:Spring+JVM+并发锁+分布式+算法
年末离职,年初为面试也筹备挺长一段时间,找了不少复习资料,刷了很多题在网上投了很多简历最终面试了有赞,还有幸拿到offer!
|
2天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
15天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
149 80
|
3天前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
|
3天前
|
算法
基于龙格库塔算法的锅炉单相受热管建模与matlab数值仿真
本设计基于龙格库塔算法对锅炉单相受热管进行建模与MATLAB数值仿真,简化为喷水减温器和末级过热器组合,考虑均匀传热及静态烟气处理。使用MATLAB2022A版本运行,展示自编与内置四阶龙格库塔法的精度对比及误差分析。模型涉及热传递和流体动力学原理,适用于优化锅炉效率。
|
1天前
|
移动开发 算法 计算机视觉
基于分块贝叶斯非局部均值优化(OBNLM)的图像去噪算法matlab仿真
本项目基于分块贝叶斯非局部均值优化(OBNLM)算法实现图像去噪,使用MATLAB2022A进行仿真。通过调整块大小和窗口大小等参数,研究其对去噪效果的影响。OBNLM结合了经典NLM算法与贝叶斯统计理论,利用块匹配和概率模型优化相似块的加权融合,提高去噪效率和保真度。实验展示了不同参数设置下的去噪结果,验证了算法的有效性。
|
8天前
|
机器学习/深度学习 算法
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。

热门文章

最新文章

下一篇
开通oss服务