记一次手撕算法面试:字节跳动的面试官把我四连击了
2020/1/23 6:26:32
本文主要是介绍记一次手撕算法面试:字节跳动的面试官把我四连击了,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
字节跳动这家公司,应该是所有秋招的公司中,对算法最重视的一个了,每次面试基本都会让你手撕算法,今天这篇文章就记录下当时被问到的几个算法题,并且每个算法题我都详细着给出了最优解,下面再现当时的面试场景。看完一定让你有所收获
一、小牛试刀:有效括号
大部分情况下,面试官都会问一个不怎么难的问题,不过你千万别太开心,因为这道题往往可以拓展出更多有难度的问题,或者一道题看起来很简单,但是给出最优解,确实很不容易的。这道题是这样的
给定一个只包括 '(',')'的字符串,判断字符串是否有效。注:空字符串属于有效字符串
示例 1: 输入: "(())" 输出: true 实例 2: 输入: "())(" 输出: false 复制代码
第一眼看到这道题,我去,这么简单,稳了(因为一面的时候,刚刚被面试官怼过勇者斗恶龙的DP题,在 leetcdoe 属于 hard 级别)。
其实这道题的 leetcode 第 20 题的简化版,属于 easy 级别
于是我也不假思索直接用栈来解决了,相信 99% 都会用栈解决吧?这里我稍微说以下过程吧,步骤如下:
1、在遍历字符串的过程中,遇到 "(" 就让它入栈,遇到 ")" 就判断下栈里面有没有 "(" :
(1)、如果有,则把处于栈顶的 "(" 弹出,相当于和 ")" 进行匹配,然后继续往后遍历字符串 (2)、如果没有,则匹配失败。相当于字符串的最前面出现了 ")",显然这是不合理的。 复制代码
2、当字符串遍历完成,判断栈是否为空,如果为空则表示字符串有效,否则无效。
为了兼顾小白,我该给你们画了个图演示,,,,我太良心了。
代码如下所示(Java,不过不是学Java也能看懂)
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),能想到用栈来处理,算是很不错的了。
4、最后一击
我以为我给出这个解法算是可以的了,面试官应该换一道题的了,然后,面试官又来了一句:还能再优化吗?。这个时候我陷入了沉思.......
看文章的各位大佬们可以想一想在空间上是否还能优化,因为在时间上是不可能优化的了。
想了一会,居然不可以用栈,优化的方案肯定是类似于上面那道题一样,用记录数量的变量来代替栈,然后就被我想出了,具体如下:
实际上,这道题仍然可以像上面那样,用变量来代替栈来优化,不过这个时候我们需要两个变量,我们假设变量为 left 和 right。
我们在从从左到右遍历字符串的过程中,用 left 记录 '(' 的数量,用 right 记录 ')' 的数量。并且在遍历的过程中:
1、如果 left == right,显然这个时候 right 个 ')' 都将一定能够得到匹配。所以当前的有效括号长度为 2 * right。然后更新 max。
2、如果 left < right,显然这个时候部分 ')' 一定得不到匹配,此时我们把 left 和 right 都置为 0。
**当遍历完字符串,我们是否就得到最大长度的有效括号了呢?**大家可以想一下
答是不可以的,我们还需要从右到左遍历计算一下。
为什么呢?
因为实际上 '(' 和 ')' 其实是等价的,为什么就不可以倒过来遍历计算呢?所以,千万别忽略了哈。
最后的代码如下:
public int longestValidParentheses(String s) { if(s == null || s.length() < 1) return 0; 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)。
总结
说时候,最后一种方法还是比较难想到了,从这次面试中也可以看出,千万不要看一道题很简单,有些题要做出来很简单,但是,如果要以最优解的方式做出来,难度马上指数上升。。
如果你后面看不大懂,建议多看几遍哦,这道题考的频率还是挺高的,主要是可以做的方法多,每种方法的效率又不一样,不过我这里必须给你们的提醒,就是平时在做题的时候,一定要寻找最优解,而不是 ac 了就不管了,应该多看看别人的解法。
有收获?希望老铁们来个三连击,给更多的人看到这篇文章
1、点赞,可以让更多的人看到这篇文章
2、关注原创微信公众号『帅地玩编程』,为了巩固计算机基础知识(计算机网络+ 操作系统+数据库+Linux)以及算法,最近开了个微信公众号『帅地玩编程』,感兴趣的可以关注,重点讲解算法相关文章,嘻嘻。后台回复『电子书』送你一份精选电子书大礼包,包含各类技能的优质电子书
这篇关于记一次手撕算法面试:字节跳动的面试官把我四连击了的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22程序员出海做 AI 工具:如何用 similarweb 找到最佳流量渠道?
- 2024-12-20自建AI入门:生成模型介绍——GAN和VAE浅析
- 2024-12-20游戏引擎的进化史——从手工编码到超真实画面和人工智能
- 2024-12-20利用大型语言模型构建文本中的知识图谱:从文本到结构化数据的转换指南
- 2024-12-20揭秘百年人工智能:从深度学习到可解释AI
- 2024-12-20复杂RAG(检索增强生成)的入门介绍
- 2024-12-20基于大型语言模型的积木堆叠任务研究
- 2024-12-20从原型到生产:提升大型语言模型准确性的实战经验
- 2024-12-20啥是大模型1
- 2024-12-20英特尔的 Lunar Lake 计划:一场未竟的承诺