当前位置:首页 > 科技  > 软件

面试官:你工作了3年了,这道算法题你都答不出来?

来源: 责编: 时间:2023-09-21 20:46:47 202观看
导读9月又是换工作的最佳时机。我幻想着只要换一份工作,就可以离开这个“破碎的地方”,赚更多的钱,做最舒服的事情,但事与愿违。最近,一名女学生正在换工作。面试前她准备了很多问题。我以为她很有信心,结果却在算法上吃了大亏

9月又是换工作的最佳时机。我幻想着只要换一份工作,就可以离开这个“破碎的地方”,赚更多的钱,做最舒服的事情,但事与愿违。Zvy28资讯网——每日最新资讯28at.com

Zvy28资讯网——每日最新资讯28at.com

最近,一名女学生正在换工作。面试前她准备了很多问题。我以为她很有信心,结果却在算法上吃了大亏。Zvy28资讯网——每日最新资讯28at.com

什么样的算法题能让面试官对一个女孩说出这么狠的话:你工作了3年了,这道算法题你都解不出来?Zvy28资讯网——每日最新资讯28at.com

有效括号

这是LeetCode上的一道算法题,旨在考察考生对“栈”数据结构的熟悉程度。我们来看一下。Zvy28资讯网——每日最新资讯28at.com

给定一个仅包含字符‘(‘、‘)’、‘{‘、‘}’、‘[‘和‘]’的字符串 s,确定输入字符串是否有效。Zvy28资讯网——每日最新资讯28at.com

如果满足以下条件,输入字符串有效:开括号必须由相同类型的括号括起来。左括号必须按正确的顺序关闭。Zvy28资讯网——每日最新资讯28at.com

示例1:Zvy28资讯网——每日最新资讯28at.com

Input: s = "()"Output: true

示例2:Zvy28资讯网——每日最新资讯28at.com

Input: s = "()[]{}"Output: true

示例3:Zvy28资讯网——每日最新资讯28at.com

Input: s = "(]"Output: false

示例4:Zvy28资讯网——每日最新资讯28at.com

Input: s = "([)]"Output: false

实施例5:Zvy28资讯网——每日最新资讯28at.com

Input: s = "{[]}"Output: true

限制条件:Zvy28资讯网——每日最新资讯28at.com

  • 1 <= s.length <= 104
  • s 仅由括号‘()[]{}’组成

问题信息Zvy28资讯网——每日最新资讯28at.com

如果我们真的没学过算法,也不知道那么多套路,那么通过问题和例子来获取尽可能多的信息是非常重要的。Zvy28资讯网——每日最新资讯28at.com

那么,我们可以得到以下信息:Zvy28资讯网——每日最新资讯28at.com

  • 字符串 s 的长度必须是偶数,不能是奇数(成对匹配)。
  • 右括号前面必须有左括号。

方法一:暴力消除法

得到以上信息后,我想既然[]、{}、()是成对出现的,那我是不是可以一一消除呢?如果最后的结果是空字符串,那不是就说明符合题意了吗?Zvy28资讯网——每日最新资讯28at.com

例如:Zvy28资讯网——每日最新资讯28at.com

Input: s = "{[()]}"Step 1: The pair of () can be eliminated, and the result s is left with {[]}Step 2: The pair of [] can be eliminated, and the result s is left with {}Step 3: The pair of {} can be eliminated, and the result s is left with '', so it returns true in line with the meaning of the question

代码:Zvy28资讯网——每日最新资讯28at.com

const isValid = (s) => {  while (true) {    let len = s.length    // Replace the string with '' one by one according to the matching pair    s = s.replace('{}', '').replace('[]', '').replace('()', '')    // There are two cases where s.length will be equal to len    // 1. s is matched and becomes an empty string    // 2. s cannot continue to match, so its length is the same as the len at the beginning, for example ({], len is 3 at the beginning, and it is still 3 after matching, indicating that there is no need to continue matching, and the result is false    if (s.length === len) {      return len === 0    }  }}

暴力消除方式还是可以通过LeetCode的用例,但是性能差了一点,哈哈。Zvy28资讯网——每日最新资讯28at.com

方法二:使用“栈”来解决

主题信息中的第二项强调对称性。栈(后进先出)和(推入和弹出)正好相反,形成明显的对称性。Zvy28资讯网——每日最新资讯28at.com

例如Zvy28资讯网——每日最新资讯28at.com

Input: abcOutput: cba

“abc”和“cba”是对称的,所以我们可以尝试从堆栈的角度来解析:Zvy28资讯网——每日最新资讯28at.com

Input: s = "{[()]}"Step 1: read ch = {, which belongs to the left bracket, and put it into the stack. At this time, there is { in the stack.Step 2: Read ch = [, which belongs to the left parenthesis, and push it into the stack. At this time, there are {[ in the stack.Step 3: read ch = (, which belongs to the left parenthesis, and push it into the stack. At this time, there are {[( in the stack.Step 4: Read ch = ), which belongs to the right parenthesis, try to read the top element of the stack (and ) just match, and pop ( out of the stack, at this time there are {[.Step 5: Read ch = ], which belongs to the right parenthesis, try to read the top element of the stack [and ] just match, pop the [ out of the stack, at this time there are {.Step 6: Read ch = }, which belongs to the right parenthesis, try to read the top element of the stack { and } exactly match, pop { out of the stack, at this time there is still '' in the stack.Step 7: There is only '' left in the stack, s = "{[()]}" conforms to the valid bracket definition and returns true.

代码Zvy28资讯网——每日最新资讯28at.com

const isValid = (s) => {  // The empty string character is valid  if (!s) {    return true  }  const leftToRight = {    '(': ')',    '[': ']',    '{': '}'  }  const stack = []  for (let i = 0, len = s.length; i < len; i++) {    const ch = s[i]    // Left parenthesis    if (leftToRight[ch]) {      stack.push(ch)    } else {      // start matching closing parenthesis      // 1. If there is no left parenthesis in the stack, directly false      // 2. There is data but the top element of the stack is not the current closing parenthesis      if (!stack.length || leftToRight[ stack.pop() ] !== ch) {        return false      }    }  }  // Finally check if the stack is empty  return !stack.length}

虽然暴力方案符合我们的常规思维,但是堆栈结构方案会更加高效。Zvy28资讯网——每日最新资讯28at.com

最后

在面试中,算法是否应该成为评价候选人的重要指标,我们不会抱怨,但近年来,几乎每家公司都将算法纳入了前端面试中。为了拿到自己喜欢的offer,复习数据结构、刷题还是有必要的。Zvy28资讯网——每日最新资讯28at.com

本文链接:http://www.28at.com/showinfo-26-10891-0.html面试官:你工作了3年了,这道算法题你都答不出来?

声明:本网页内容旨在传播知识,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。邮件:2376512515@qq.com

上一篇: 一文读懂分布式追踪:过去、现在和未来

下一篇: CSS实现十个功能强大的一行布局技巧

标签:
  • 热门焦点
Top