美文网首页创业前端之美
JavaScript经典面试题之简单算法

JavaScript经典面试题之简单算法

作者: 祈澈菇凉 | 来源:发表于2018-09-28 17:19 被阅读234次

    一:Virtual DOM(二)

    在 Virtual DOM 的基础上给 VNode 类添加 render 方法,render 方法把一个虚拟的 DOM 节点渲染成真正的 DOM 节点,例如:

    const ul = h('ul', {id: 'list', style: 'color: red'}, [
      h('li', {class: 'item'}, ['Item 1']),
      h('li', {class: 'item'}, ['Item 2']),
      h('li', {class: 'item'}, ['Item 3'])
    ]
    
    const urlDom = ul.render() // 渲染 DOM 节点和它的子节点
    ulDom.getAttribute('id') === 'list' // true
    ulDom.querySelectorAll('li').length === 3 // true
    

    答案:

    class VNode {
      constructor (tagName, props, children) {
        this.tagName = tagName
        this.props = props
        this.children = children
      }
      render () {
        // 根据 tagName 构建 DOM 节点
        const el = document.createElement(this.tagName)
        // 设置 DOM 节点属性
        Object.entries(this.props).forEach(([key, value]) => el.setAttribute(key, value))
        var children = this.children || []
        /* 渲染子节点 */
        children.forEach((child) => {
          var childNode = (child instanceof VNode)
            ? child.render() // 如果子节点也是虚拟DOM,递归构建DOM节点
            : document.createTextNode(child) // 如果字符串,只构建文本节点
          el.appendChild(childNode)
        })
        return el
      }
    }
    
    const h = (tagName, props, children) => {
      return new VNode(tagName, props, children)
    }
    

    二:Virtual DOM

    大家都知道,React、Vue 内部都采用了 Virtual DOM 的技术。简而言之,就是用普通的 JavaScript 对象来表示 DOM 的结构和信息。例如下面的 DOM 结构:

    <ul id='list' style='color: red'>
      <li class='item'>Item 1</li>
      <li class='item'>Item 2</li>
      <li class='item'>Item 3</li>
    </ul>
    

    可以用 JavaScript 的对象表示为:

    const ul = {
      tagName: 'ul', // 节点标签名
      props: { // DOM的属性,用一个对象存储键值对
        id: 'list',
        style: 'color: red'
      },
      children: [ // 该节点的子节点
        {tagName: 'li', props: {class: 'item'}, children: ["Item 1"]},
        {tagName: 'li', props: {class: 'item'}, children: ["Item 2"]},
        {tagName: 'li', props: {class: 'item'}, children: ["Item 3"]},
      ]
    }
    

    每个代表 DOM 节点的对象有三个属性:

    tagName:代表 DOM 节点的标签名。
    props:这个 DOM 节点的属性,用一个对象表示。
    children:这个 DOM 节点的子节点,是一个数组;数组的元素可以是 字符串 或者 对象。如果是字符串就表示这个子节点是文本节点,否则就表示是另外一个 DOM 节点。
    

    请你完成 h 函数,可以通过 h 函数生成上面的结果,例如:

    const ul = h('ul', {id: 'list', style: 'color: red'}, [
      h('li', {class: 'item'}, ['Item 1']),
      h('li', {class: 'item'}, ['Item 2']),
      h('li', {class: 'item'}, ['Item 3'])
    ])
    
    ul.props.id === 'list' // => true
    

    h 函数需要返回的实例是属于 VNode 这个类的:

    ul instanceof VNode // => true

    请你完成 h 函数和 VNode 的实现。

    答案:

    class VNode {
      constructor (tagName, props, children) {
        this.tagName = tagName
        this.props = props
        this.children = children
      } 
    }
    
    const h = (tagName, props, children) => {
      return new VNode(tagName, props, children)
    }
    

    三:专业盗贼

    你是一个盗窃专家,某一天晚上你要去盗窃某一条街道的一排房子。这些房子都有相连的防盗系统,如果你把相邻的两家都偷了那么就会触发报警器。

    用一个数组来表示这些房子的金钱数量,请你完成 rob 函数,计算出在不触发报警器的情况下最多能偷多少钱。例如:

    rob([1, 2, 3]) // => 4

    答案:

    // const rob = (nums) => {
    //   const cache = new Map()
    //   const robIt = (i) => {
    //     if (i >= nums.length) return 0
    //     if (cache.has(i)) return cache.get(i);
    //     const cur = i < 0 ? 0 : nums[i]
    //     const max = cur + Math.max(
    //       robIt(i + 2), // 隔一个房子偷
    //       robIt(i + 3) // 或者隔两个房子偷
    //     )
    //     cache.set(i, max) /* 存储记忆化数据 */
    //     return max
    //   }
    //   return robIt(-2) // -2 + 2 = 0 偷第一所房子, -2 + 3 = 1 不偷第一所房间
    // }
    
    const rob = (nums) => {
      let i = 0;
      let e = 0;
      for (let k = 0; k < nums.length; k++) {
        let tmp = i;
        i = nums[k] + e;
        e = Math.max(tmp, e);
      }
      return Math.max(i, e);
    }
    
    

    四:优先队列

    优先队列是一种元素带权重的队列,你可以往队列中添加和删除元素,但是删除元素的时候会把优先级最高的元素删除。例如:

    const pq = new PriorityQueue()
    pq.add(1)
    pq.add(2)
    pq.add(3)
    
    pq.remove() // => 3
    pq.remove() // => 2
    pq.remove() // => 1
    

    remove 方法每次删除的时候都会把最大的元素删除掉,并且返回被删除元素。请你完成 PriorityQueue 的实现。

    服务器运行时间限制:20ms。

    答案:

    /* 经典的二叉堆实现优先队列 */
    class PriorityQueue {
      constructor () {
        this.q = []
        this.n = 0
      }
    
      _exch (i, j) {
        const q = this.q
        const tmp = q[i]
        q[i] = q[j]
        q[j] = tmp
      }
    
      add (item) {
        this.n += 1
        const q = this.q
        let n = this.n
        q[n] = item
        let j = n / 2 | 0
        while (j > 0 && q[j] < q[n]) {
          this._exch(j, n)
          n = j
          j = n / 2 | 0
        }
      }
    
      remove () {
        if (this.n === 0) return
        const q = this.q
        const item = q[1]
        this._exch(1, this.n--)
        q.pop()
        let n = this.n
        let j = 1
        while (2 * j <= n) {
          let k = 2 * j
          if (k < n && q[k] < q[k + 1]) k++
          if (q[k] <= q[j]) break
          this._exch(k, j)
          j = k
        }
        return item
      }
    }
    

    五: 数组中的数据划分

    完成一个函数 partition,它接受一个数组作为参数。它会搬动数组中的元素,使得所有小于第一个项的元素都搬动到它的左边,所有大于第一个项的元素都搬动到右边。例如:

    const arr = [3, 1, 6, 2, 4, 5]
    partition(arr)
    console.log(arr) // => [2, 1, 3, 6, 4, 5]
    

    输入的数组的第一个项是 3,所以最后小于 3 的 1、2 的都到了左边,大于 3 的 4, 5, 6 都到了右边。

    请你在不能使用任何数组原生方法,只能使用循环和赋值的情况下完成 partition 函数。

    答案:

    /* 这题考察的其实是快速排序里面的数据归类*/
    const partition = (arr) => {
      const exch = (i, j) => { let t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
      const v = arr[0]
      let i = 0
      let j = arr.length
      while (true) {
        while (arr[++i] <= v && i < arr.length);
        while (arr[--j] >= v && j > 0);
        if (i >= j) break
        exch(i, j)
      }
      exch(0, j)
    }
    

    六:数组中数据归并

    有一个数组,这个数组从两个地方开始升序,一个是开始,一个是中间。例如:

    [10, 21, 32, 11, 16, 40] // 从 0 和 3 开始升序
    [1, 5, 10, 11, 3, 4, 8, 12, 30] // 0 和 4 开始升序
    

    请你完成 merge 函数,可以把类似上面的数组变成一个完全升序的数组(直接修改原来的数组)。你不能用 sort 方法,并且只能使用一次循环。

    答案:

    /* 这题就是考归并排序里面的归并方法 */
    const merge = (arr) => {
      const aux = [...arr]
      const mid = Math.floor(arr.length / 2)
      let i = 0
      let j = mid
      for (let k = 0, len = arr.length; k < len; k++) {
        if (i >= mid) arr[k] = aux[j++]
        else if (j >= len) arr[k] = aux[i++]
        else if (aux[i] > aux[j]) arr[k] = aux[j++]
        else arr[k] = aux[i++]
      }
    }
    

    七:最高产的猪

    我们用一个 HTML 结构来表示一头猪的子子孙孙:

    <div class="pig">
      <div class="pig">
        <div class="pig">
          <div class="pig"></div>
        </div>
        <div class="pig">
          <div class="pig"></div>
        </div>
        <div class="pig">
          <div class="pig"></div>
        </div>
      </div>
      <div class="pig">
        <div class="pig"></div>
        <div class="pig"></div>
      </div>
      <div class="pig">
        <div class="pig">
          <div class="pig"></div>
          <div class="pig"></div>
          <div class="pig"></div>
          <div class="pig"></div>
          <div class="pig"></div>
        </div>
      </div>
    </div>
    

    每个 DOM 节点都是一头猪,子节点就是这头猪的孩子。

    请你完成一个函数 findMostProductivePigChildrenCount 它接受一个 DOM 节点作为参数,返回一个数组。存放同代猪最高产的猪的孩子的数量。例如:

    1: o
    2: o o o
    3: o o o o o o
    4: o o o ooooo

    上面的结果是 [3, 3, 5, 0],解释如下:

    第一代猪有三个孩子,所以数组第一项是 3。

    第二代的三头猪中,第一头猪生了 3 个,第二头猪生了 2 个,第三头猪生了 1 个。最高产的是第一头猪,它的孩子数是 3,所以数组第二项为 3。

    第三代的前三头猪都有一个后代,中间两头猪绝后,而最后一头猪惊人地生出了 5 头猪。这一代最高产的猪的孩子数是 5,所以数组项是 5。

    最后一代无后,所以是 0。

    答案:

    /* 其实这道题就是非常常用的广度优先搜索算法,这种题目一般用一个队列
     * 来把从广度上属于同一个层级的节点进行存储,然后再逐层访问。
     */
    
    const findMostProductivePigChildrenCount = (dom) => {
      const queue = []
      const ret = []
      queue.push(dom)
      while (queue.length > 0) {
        let size = queue.length
        let max = 0
        while (size--) {
          const pig = queue.shift()
          console.log(pig.children.length)
          max = Math.max(pig.children.length, max)
          queue.push(...pig.children)
        }
        ret.push(max)
      }
      return ret
    }
    
    // or
    // const findMostProductivePigChildrenCount = (dom) => {
    // const queue = [[dom]]
    // while (queue[0].length)
    //   queue.unshift(queue[0].reduce((p, c) => [...p, ...c.children], []))
    // queue.shift()
    // return queue.reverse().map(x => x.reduce((p, c) => c.childElementCount > p ? c.childElementCount : p, 0))
    // }
    

    八: 爬楼梯

    有一个楼梯,你一次只能往上走一阶或者两阶。请编写函数 climbStairs,它接受一个整数 n 作为参数,表示这个楼梯有多少阶。请你返回一个整数,表示这个楼梯一共有多少种走法。例如:

    climbStairs(1) // => 1
    climbStairs(2) // => 2
    climbStairs(3) // => 3
    climbStairs(10) // => 89
    

    答案:

    // const memorize = [0, 1, 2]
    // const climbStairs = n => n in memorize ? memorize[n] : (memorize[n] = climbStairs(n - 1) + climbStairs(n - 2))
    
    const map = new Map();
    const climbStairs = (n) => {
      if (n <= 2) return n;
      if (map.has(n)) return map.get(n);
      const stairs = climbStairs(n - 1) + climbStairs(n - 2)
      map.set(n, stairs);
      return stairs;
    }
    

    九:奇怪的表达式

    我们来定义一种新的表达式来表示二元操作:(操作符 操作数 操作数)。例如原来的 1 + 2 现在我们写成 (+ 1 2);原来的 2 / 1 写成 (/ 2 1)。表达式里面的操作数可以是另外一个表达式,例如:(* 3 (+ 2 1)) 相当于 3 * (2 + 1)。

    请你完成一个函数 runExpression 它可以分析 + - * / 四种简单的二元操作(只操作正整数)并且返回表达式执行的结果。例如:

    runExpression('(+ 1 2)') // => 3
    runExpression('(+ (- 2 1) (* 3 (/ 2 1)))') // => 7
    

    遇到无法分析情况返回 null 即可,例如 runExpression('Hello World') 和 runExpression('5') 则返回 null

    答案:

    const LEFT_PARENT = 0
    const RIGHT_PARENT = 1
    const OPERATOR = 2
    const OPERANT = 3
    
    function runExpression (exp) {
      try {
        return run(parse(tokenize(exp)))
      } catch (e) {
        return null
      }
    }
    
    function tokenize(exp) {
      const tokens = []
      let i = 0
      let numStr = ''
      let isNum = false
      while (i < exp.length) {
        const char = exp[i++]
        if (char.match(/\d/)) {
          numStr = isNum ? numStr + char : char
          isNum = true
          continue
        } else if (isNum) {
          tokens.push({ type: OPERANT, value: numStr * 1 })
          isNum = false
          numStr = ''
        }
        if (char === '(') {
          tokens.push({ type: LEFT_PARENT, value: char })
        } else if (char === ')') {
          tokens.push({ type: RIGHT_PARENT, value: char })
        } else if (char.match(/[\+\-\*/]/)) {
          tokens.push({ type: OPERATOR, value: char })
        } else if (char.match(/\s/)) {
          continue
        } else {
          throw new Error(`Unexpected token ${char}`)
        }
      }
      if (numStr) tokens.push({ type: OPERANT, value: numStr * 1 })
      return tokens
    }
    
    function parse (tokens) {
      let i = 0
    
      function parseExpression () {
        /* 仍然是表达式 */
        eat(LEFT_PARENT)
        const node = {}
        node.operator = parseOperator()
        node.left = parseOperant()
        node.right = parseOperant()
        eat(RIGHT_PARENT)
        return node
      }
    
      function parseOperant () {
        /* 最底层数组 */
        const current = tokens[i]
        if (current.type === OPERANT) {
          eat(OPERANT)
          return current.value
        } else {
          return parseExpression()
        }
      }
    
      function parseOperator () {
        const token = eat(OPERATOR)
        return token.value
      }
    
      function eat (type) {
        const token = tokens[i]
        if (token.type !== type) {
          throw new Error(`Parse error: Unexpected token ${token.value}`)
        }
        i++
        return token
      }
    
      /* 分析根结点 */
      const root = parseExpression()
    
      /* 有剩余 token,表达式不正确 */
      if (i !== tokens.length) {
        const token = tokens[i]
        throw new Error(`Parse error: Unexpected token ${token.value}`)
      }
      return root
    }
    
    function run (ast) {
      if (typeof ast === 'number') return ast
      const ops = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => a / b
      }
      return ops[ast.operator](run(ast.left), run(ast.right))
    }
    

    十:你会被谷歌拒绝吗?

    Max Howell 参加了谷歌的面试,出题人竟然要求 Max Howell 在白板上作出解答,Max Howell 当然愤怒地拒绝了,回家以后马上在微博上跟我们分享他的吐槽:

    Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
    

    看来在白板上作出反转二叉树的解答并不容易呢?那么在 ScriptOJ 有上 OJ 系统会不会更方便一些呢?

    假如有这样一个二叉树,

              4
            /   \
          3      2
        /  \    / \
      7     1  2   3
     / \   /   
    6   5 9
    

    使用广度优先的原则用数组的表示就是 [4, 3, 2, 7, 1, 2, 3, 6, 5, 9, null, null, null, null, null],二叉树中的空位用 null 表示。

    进行反转以后会变成

              4
            /   \
          2      3
        /  \    /  \
      3     2  1     7
                \   /  \  
                 9 5    6
    

    使用广度优先的原则用数组的表示就是 [4, 2, 3, 3, 2, 1, 7, null, null, null, null, null, 9, 5, 6]。

    请实现函数 invertTree,它接受一个表示二叉树的数组,返回表示这个反转二叉树的数组。

    请注意,提交后提示中显示的 1,2,3,,,4,5 表示的是 1, 2, 3, null, null, 4, 5。

    答案:

    const parseTree = (tree) => {
      if(tree.length <= 3) {
        const [root, left, right] = tree
        return [root, [right], [left]]
      }
      const left = []
      const right = []
      let floor
      tree.slice(1).forEach((value, index) => {
        floor = ~~(Math.log(index + 2) / Math.LN2)
        if (left.length < Math.pow(2, floor) - 1) {
          left.push(value)
        } else {
          right.push(value)
        }
      })
      return [tree[0], parseTree(right), parseTree(left)]
    }
    
    const flatTree = (tree) => {
      if (tree.every(node => !Array.isArray(node))) return tree
      const roots = tree.filter(node => !Array.isArray(node))
      const children = tree.filter(node => Array.isArray(node)).reduce(
        (children, child) => children.concat(child), [])
      return roots.concat(flatTree(children))
    }
    
    const invertTree = (tree) => {
      const parsedInvertedTree = parseTree(tree)
      return flatTree(parsedInvertedTree)
    }
    

    十一:同字母异序

    同字母异序指的是两个字符串字母种类和字母的数量相同,但是顺序可能不同。

    完成 isAnagram,接受两个字符串作为参数,返回true 或者 false 表示这两个字符串是否同字母异序。例如:

    isAnagram("anagram", "nagaram") // => return true.
    isAnagram("rat", "car") // => return false.
    

    (本题来源:github, LeetCode)

    答案:

    const isAnagram = (str1, str2) => /* TODO */ {
     return !str1.split('').sort().join('').replace(str2.split('').sort().join(''), '');
    }
    

    原文作者:祈澈姑娘
    技术博客:https://www.jianshu.com/u/05f416aefbe1
    90后前端妹子,爱编程,爱运营,爱折腾。坚持总结工作中遇到的技术问题,坚持记录工作中所所思所见,欢迎大家一起探讨交流。

    相关文章

      网友评论

      • 舟可度:你是前端工程师吧?我对Javascript只会API里基本的功能。
        舟可度:@祈澈菇凉 看来你是一个很有开发经验的工程师。
        祈澈菇凉:@舟可度 是的

      本文标题:JavaScript经典面试题之简单算法

      本文链接:https://www.haomeiwen.com/subject/ahulzxtx.html