七：最高产的猪
我们用一个 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(''), ''); }
