懂这10道JS经典算法题，你就是前端大神！

[h2]一：Virtual DOM（二）[/h2]在 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' // trueulDom.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)}

复制代码

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

Item 1 Item 2 Item 3

复制代码

可以用 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)}

复制代码

[h2]三：专业盗贼[/h2]你是一个盗窃专家，某一天晚上你要去盗窃某一条街道的一排房子。这些房子都有相连的防盗系统，如果你把相邻的两家都偷了那么就会触发报警器。
用一个数组来表示这些房子的金钱数量，请你完成 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);}

复制代码

[h2]四：优先队列[/h2]优先队列是一种元素带权重的队列，你可以往队列中添加和删除元素，但是删除元素的时候会把优先级最高的元素删除。例如：

const pq = new PriorityQueue()pq.add(1)pq.add(2)pq.add(3)pq.remove() // => 3pq.remove() // => 2pq.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 { 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 && j > 0); if (i >= j) break exch(i, j) } exch(0, j)}

复制代码

[h2]六：数组中数据归并[/h2]有一个数组，这个数组从两个地方开始升序，一个是开始，一个是中间。例如：

[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++] }}

复制代码

[h2]七：最高产的猪[/h2]我们用一个 HTML 结构来表示一头猪的子子孙孙：

复制代码

每个 DOM 节点都是一头猪，子节点就是这头猪的孩子。
请你完成一个函数 findMostProductivePigChildrenCount 它接受一个 DOM 节点作为参数，返回一个数组。存放同代猪最高产的猪的孩子的数量。例如：
1: o2: o o o3: o o o o o o4: 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))// }

复制代码

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

climbStairs(1) // => 1climbStairs(2) // => 2climbStairs(3) // => 3climbStairs(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 3runExpression('(+ (- 2 1) (* 3 (/ 2 1)))') // => 7

复制代码

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

const LEFT_PARENT = 0const RIGHT_PARENT = 1const OPERATOR = 2const OPERANT = 3function 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))}

复制代码

[h2]十：你会被谷歌拒绝吗？[/h2]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 { 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)}

复制代码

[h2]十一：同字母异序[/h2]同字母异序指的是两个字符串字母种类和字母的数量相同，但是顺序可能不同。
完成 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后前端妹子，爱编程，爱运营，文艺与代码齐飞，魅力与智慧共存的程序媛一枚。

知识小金库