面试官：你工作了 3 年了，这道算法题你都答不出来？
9 月又是换工作的最佳时机。我幻想着只要换一份工作，就可以离开这个“破碎的地方”，赚更多的钱，做最舒服的事情，但事与愿违。
最近，一名女学生正在换工作。面试前她准备了很多问题。我以为她很有信心，结果却在算法上吃了大亏。什么样的算法题能让面试官对一个女孩说出这么狠的话：你工作了 3 年了，这道算法题你都解不出来？
有效括号
这是 LeetCode 上的一道算法题，旨在考察考生对“栈”数据结构的熟悉程度。我们来看一下。
给定一个仅包含字符‘(‘、‘)’、‘{‘、‘}’、‘[‘和‘]’的字符串 s，确定输入字符串是否有效。
如果满足以下条件，输入字符串有效：开括号必须由相同类型的括号括起来。左括号必须按正确的顺序关闭。
示例 1：
示例 2：
示例 3：
示例 4：
示例 5：
限制条件：
1 <= s.length <= 104
s 仅由括号‘()[]{}’组成
问题信息：如果我们真的没学过算法，也不知道那么多套路，那么通过问题和例子来获取尽可能多的信息是非常重要的。
那么，我们可以得到以下信息：
字符串 s 的长度必须是偶数，不能是奇数（成对匹配）。
右括号前面必须有左括号。
方法一：暴力消除法
得到以上信息后，我想既然[]、{}、()是成对出现的，那我是不是可以一一消除呢？如果最后的结果是空字符串，那不是就说明符合题意了吗？
例如：
代码：
暴力消除方式还是可以通过 LeetCode 的用例，但是性能差了一点，哈哈。
方法二：使用“栈”来解决
主题信息中的第二项强调对称性。栈（后进先出）和（推入和弹出）正好相反，形成明显的对称性。
例如：
“abc”和“cba”是对称的，所以我们可以尝试从堆栈的角度来解析：
代码：
虽然暴力方案符合我们的常规思维，但是堆栈结构方案会更加高效。
最后
在面试中，算法是否应该成为评价候选人的重要指标，我们不会抱怨，但近年来，几乎每家公司都将算法纳入了前端面试中。为了拿到自己喜欢的 offer，复习数据结构、刷题还是有必要的。
版权声明: 本文为 InfoQ 作者【高端章鱼哥】的原创文章。
原文链接:【http://xie.infoq.cn/article/70d15c3d3087c3ec17bdf1cc3】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
还未添加个人签名 2023-06-19 加入
还未添加个人简介
评论