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经典面试题之简单算法

一：Virtual DOM（二）

二：Virtual DOM

三：专业盗贼

四：优先队列

五：数组中的数据划分

六：数组中数据归并

七：最高产的猪

八：爬楼梯

九：奇怪的表达式

十：你会被谷歌拒绝吗？

十一：同字母异序

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

创业

前端之美

JavaScript经典面试题之简单算法

一：Virtual DOM（二）

二：Virtual DOM

三：专业盗贼

四：优先队列

五： 数组中的数据划分

六：数组中数据归并

七：最高产的猪

八： 爬楼梯

九：奇怪的表达式

十：你会被谷歌拒绝吗？

十一：同字母异序

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

创业

前端之美

五：数组中的数据划分

八：爬楼梯