JavaScript算法面试题

目录
  • 有效的括号问题
    • 解题信息
    • 暴力消除法
    • 栈解题法
  • 结尾

前言：

现实总是残酷的，最近有个学妹在换工作，面试前什么手写Priomise、vue双向绑定原理,webpack优化方式,准备了一大堆，本以为成竹在胸，结果却在算法上吃了大亏，心仪的offer没有拿到，一度怀疑人生。到底是什么算法题能让面试官对妹子说出你都工作3年了，这个算法题都不会？这样的狠话？

有效的括号问题

这是一道leetcode上的原题，本意是在考察候选人对栈数据结构的掌握。来看看题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

示例：

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([)]"
输出：false

示例 5：
输入：s = "{[]}"
输出：true

解题信息

如果咱们确实没有刷过算法，不知道那么多套路，通过题目和示例尽可能的获取到更多的信息就很重要了。

根据题目推断出：

  • 字符串s的长度一定是偶数，不可能是奇数(一对对匹配)。
  • 右括号前面一定跟着左括号，才符合匹配条件，具备对称性。
  • 右括号前面如果不是左括号，一定不是有效的括号。

暴力消除法

得到了以上这些信息后，胖头鱼想既然是[]、{}、()成对的出现，我能不能把他们都挨个消除掉，如果最后结果是空字符串，那不就意味着符合题意了吗？

举个例子：

输入：s = "{[()]}"

第一步：可以消除()这一对，结果s还剩{[]}

第二步: 可以消除[]这一对，结果s还剩{}

第三步: 可以消除{}这一对，结果s还剩'' 所以符合题意返回true

代码实现：

const isValid = (s) => {
  while (true) {
    let len = s.length
    // 将字符串按照匹配对，挨个替换为''
    s = s.replace('{}', '').replace('[]', '').replace('()', '')
    // 有两种情况s.length会等于len
    // 1. s匹配完了，变成了空字符串
    // 2. s无法继续匹配，导致其长度和一开始的len一样，比如({],一开始len是3，匹配完还是3，说明不用继续匹配了，结果就是false
    if (s.length === len) {
      return len === 0
    }
  }
}

暴力消除法最终还是可以通过leetcode的用例，就是性能差了点，哈哈

栈解题法

解题信息中的第2条强调对称性，而栈（后入先出）入栈和出栈恰好是反着来，形成了鲜明的对称性。

入栈：abc，出栈：cba

abc
cba

所以可以试试从栈的角度来解析：

输入：s = "{[()]}"

第一步：读取ch = {，属于左括号，入栈，此时栈内有{
第二步：读取ch = [，属于左括号，入栈，此时栈内有{[
第三步：读取ch = (，属于左括号，入栈，此时栈内有{[(
第四步：读取ch = )，属于右括号，尝试读取栈顶元素(和)正好匹配，将(出栈，此时栈内还剩{[
第五步：读取ch = ]，属于右括号，尝试读取栈顶元素[和]正好匹配，将[出栈，此时栈内还剩{
第六步：读取ch = }，属于右括号，尝试读取栈顶元素{和}正好匹配，将{出栈，此时栈内还剩''
第七步：栈内只能''，s = "{[()]}"符合有效的括号定义，返回true

代码实现：

const isValid = (s) => {
  // 空字符串符合条件
  if (!s) {
    return true
  }

  const leftToRight = {
    '(': ')',
    '[': ']',
    '{': '}'
  }
  const stack = []

  for (let i = 0, len = s.length; i < len; i++) {
    const ch = s[i]
    // 左括号
    if (leftToRight[ch]) {
      stack.push(ch)
    } else {
      // 右括号开始匹配
      // 1. 如果栈内没有左括号，直接false
      // 2. 有数据但是栈顶元素不是当前的右括号
      if (!stack.length || leftToRight[ stack.pop() ] !== ch) {
        return false
      }
    }
  }

  // 最后检查栈内还有没有元素，有说明还有未匹配则不符合
  return !stack.length
}

暴力解法虽然符合我们日常的思维，但是果然还是栈结构解法好了不少。

结尾

面试中，算法到底该不该成为考核候选人的重要指标咱们不吐槽，但是近几年几乎每个大厂都将算法放进了前端面试的环节，为了获得心仪的offer，重温数据结构，刷刷题还是很有必要的，愿你我都被算法温柔以待。

到此这篇关于JavaScript算法面试题汇总的文章就介绍到这了,更多相关JavaScript算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 如何通过JS实现日历简单算法

    最近有用到日历可需要编辑文本的日历,为了绑定数据的方便,所以用js写了一套日历,其实思想也是很简单.实现步骤如下: 1.首先取得处理月的总天数 js不提供此参数,我们需要计算.考虑到闰年问题会影响二月份的天数,我们先编写一个判断闰年的自编函数: function is_leap(year) { return (year%100==0?res=(year%400==0?1:0):res=(year%4==0?1:0)); } 2.接着定义一个包含十二个月在内的月份总天数的数组: m_days=ne

  • JavaScript编程通过Matlab质心算法定位学习

    JavaScript编程通过Matlab质心算法定位学习

    目录 Matlab质心算法 Matlab作为封闭的商业软件,受美国政府左右,无视商业道德,故不建议使用.如果喜欢Matlab语法,可移步开源的octave,其语法与matlab完全相同. Matlab质心算法 所谓质心,就是当密度作为像素点灰度值时的重心,例如其质心的x坐标为 最直观的方法就是下面的这种方式了. %%通过质心算法找到img的质心位置 function [x,y] = oCenter(img) img = double(img); [m,n] = size(img); x = 0;

  • JS面试题---关于算法台阶的问题

    有100格台阶,可以跨1步可以跨2步,那么一个有多少种走法: 今天电话面试.遇到一道算法问题,然后瞬间一脸懵逼: 然后机智的我,自作聪明的想到如果一个人每次都走1步,那么最多100步,每次走2步最少50步:然后明显跑题了...还好对方及时把我打断了...不然我估计要对着这玩意一直死脑经...一路走到黑.. 然后回到家了.拿着偶的mac,然后静静的思考,终于写出来了 var Stairs = new step(); function step(){ this.n1=1; this.n2=2; th

  • JS中多层次排序算法的实现代码

    JS中多层次排序算法的实现代码

    引子 排序在编程中随处可见,从开始学习变成,到项目开发,基本上或多或少会遇到一些排序问题,接下来我要写的是我在实际开发终于到的一个排序问题,一开始卡了我很久,后面随着知识积累,实践变多才解决掉了,不知道是不是我搜索关键字不对,还是其他原因,百度也没有找到这方面的内容. 数据结构和需求 var arr = [ { "soNumber" : "52085848", "item" : "313281", "amount&q

  • JavaScript实现的七种排序算法总结（推荐！）

    目录 前言 冒泡排序 基础算法 第二种写法是在基础算法的基础上改良而来的: 选择排序 基础算法 二元选择排序-优化 插入排序 交换法插入排序 移动法 希尔排序 堆排序 快速排序 归并排序 总结 前言 所谓排序算法,即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序.这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率.对于排序,我们首先要求其具有一定的稳定性,即当两个相同的元素同时出现于某个序列之中,则经过一定的排序算法之后,两者在排序前

  • 浅谈JavaScript构造树形结构的一种高效算法

    浅谈JavaScript构造树形结构的一种高效算法

    引言 我们经常会碰到树形数据结构,比如组织层级.省市县或者动植物分类等等数据.下面是一个树形结构的例子: 在实际应用中,比较常见的做法是将这些信息存储为下面的结构,特别是当存在1对多的父/子节点关系时: const data = [ { id: 56, parentId: 62 }, { id: 81, parentId: 80 }, { id: 74, parentId: null }, { id: 76, parentId: 80 }, { id: 63, parentId: 62 }, {

  • Vue中使用crypto-js AES对称加密算法实现加密解密

    Vue中使用crypto-js AES对称加密算法实现加密解密

    目录 下载crypto-js 加密解密数据 AES算法的ECB模式加密-设置秘钥 AES算法的CBC模式加密-设置秘钥和偏移量 参考: 在数字加密算法中,通过可划分为对称加密和非对称加密 对称加密:如AES,DES,3DES 含义:加密和解密使用的是同一把钥匙.密钥不能在网络中传输,避免被拦截.如果要传输,必须要对密钥进行非对称加密再加密一次. 优点:算法简单,加密解密容易,效率高,执行快. 缺点:相对来说不算特别安全,只有一把钥匙,密文如果被拦截,且密钥也被劫持,那么,信息很容易被破译. 非对

  • JavaScript算法面试题

    JavaScript算法面试题

    目录 有效的括号问题 解题信息 暴力消除法 栈解题法 结尾 前言: 现实总是残酷的,最近有个学妹在换工作,面试前什么手写Priomise.vue双向绑定原理,webpack优化方式,准备了一大堆,本以为成竹在胸,结果却在算法上吃了大亏,心仪的offer没有拿到,一度怀疑人生.到底是什么算法题能让面试官对妹子说出你都工作3年了,这个算法题都不会?这样的狠话? 有效的括号问题 这是一道leetcode上的原题,本意是在考察候选人对栈数据结构的掌握.来看看题目 给定一个只包括 '(',')','{',

  • 分享几道和「滑动窗口」有关的算法面试题

    前言科普:什么是滑动窗口算法 滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合. 假设有数组 [a b c d e f g h ],一个大小为 3 的 滑动窗口 在其上滑动,则有: [a b c] [b c d] [c d e] [d e f] [e f g] [f g h] 一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动,同时 动态地 记录一些有用的数据,很多情况下,能够极大地提高算法地效率. 1. 滑动窗口最大值 题目来源于 LeetCode

  • C#常见算法面试题小结

    本文实例汇总了C#面试常见的算法题及其解答.具有不错的学习借鉴价值.分享给大家供大家参考.具体如下: 1.写出冒泡,选择,插入排序算法. //冒泡排序 public class bubblesorter { public void sort(int[] list) { int i, j, temp; bool done = false; j = 1; while ((j < list.Length) && (!done)) { done = true; for (i = 0; i &

  • Java main 方法面试题的详细整理

    Java main 方法面试题的详细整理 1.不用main方法如何定义一个类? 不行,没有main方法我们不能运行Java类. 在java 7之前,你可以通过使用静态初始化运行Java类.但是,从Java 7开始就行不通了. 2.main()方法需要的参数不是字符串数组? 不是的,main()方法的参数必须是字符串数组. 但是,在引进变参时,你可以将字符串类型的变参作为参数传递给main()方法.变参一定得是数组. package com.instanceofjava; public class

  • 10个经典的Java main方法面试题

    分享给大家,如有错误,请指出. 1.不用main方法如何定义一个类? 不行,没有main方法我们不能运行Java类. 在Java 7之前,你可以通过使用静态初始化运行Java类.但是,从Java 7开始就行不通了. 2.main()方法需要的参数不是字符串数组? 不是的,main()方法的参数必须是字符串数组. 但是,在引进变参时,你可以将字符串类型的变参作为参数传递给main()方法.变参一定得是数组. package com.instanceofjava; public class Main

  • 5个JavaScript经典面试题

    1:Scope作用范围 复制代码 代码如下: (function() {     var a = b = 5;  })();  console.log(b); 什么会被打印在控制台上? 回答 上面的代码会打印 5. 这个问题的诀窍是,这里有两个变量声明,但 a 使用关键字var声明的.代表它是一个函数的局部变量.与此相反,b 变成了全局变量. 这个问题的另一个诀窍是,它没有使用严格模式 ('use strict';).如果启用了严格模式,代码就会引发ReferenceError的错误:B没有定义

  • Golang协程常见面试题小结

    目录 交替打印奇数和偶数 方法一:使用无缓冲的channel进行协程间通信 方法二:使用有缓冲的channel N个协程打印1到maxVal 交替打印字符和数字 交替打印字符串 方法一使用无缓冲的channel 三个协程打印ABC Channel练习 交替打印奇数和偶数 下面让我们一起来看看golang当中常见的算法面试题使用两个goroutine交替打印1-100之间的奇数和偶数, 输出时按照从小到大输出. 方法一:使用无缓冲的channel进行协程间通信 package main impor

  • 一篇有意思的技术文章php介绍篇

    身为一名中级PHPer菜鸟..无聊了就爱在各个PHP论坛瞎转.看到了好多PHP初学者都问到了很多相同的问题.而且我学PHP的时候也都遇到过.为了 让PHP初学者少走一些弯路.所以突然神经恍惚.决定写下此文章.仅供PHP初学者参考.如有错误.还望指出.不甚感激. PHP其实是一种很简单易学的语言.如果要精通PHP多则三年.少则一年就足够了.但是为什么三年之后我们照样是菜鸟? 不知道从什么开始.学习PHP我们不得不学习数据库.学习架构.学习面向对象.学习前端.学习linux.学习协议甚至美工等直接导

  • 深入理解redux之compose的具体应用

    应用 最近给自己的react项目添加redux的时候,用到了redux中的compose函数,使用compose来增强store,下面是我在项目中的一个应用: import {createStore,applyMiddleware,compose} from 'redux'; import createSagaMiddleware from 'redux-saga'; const sagaMiddleware = createSagaMiddleware(); const middlewares

  • Javascript前端经典的面试题及答案

    前言 如果面试题按类型来分,主要涉及到"技术"与"非技术"两大类,技术类别下涉及到的子类别有: 移动 & PC端布局类 JavaScript 核心基础类 衍生框架类 项目应用类 这四大类别的面试题若按出现频率来划分,则面试时 100% 会问到的题型有:"移动端&PC端布局类.JavaScript 核心基础类".本次选择这两类中难度更高一些的 "JavaScript 核心基础类" 面试题,进行了分析和解答,供面试

随机推荐