一：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 结构：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)
}
三：专业盗贼
你是一个盗窃专家，某一天晚上你要去盗窃某一条街道的一排房子。这些房子都有相连的防盗系统，如果你把相邻的两家都偷了那么就会触发报警器。用一个数组来表示这些房子的金钱数量，请你完成 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 // 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 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] 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 let k = 2 * j
if (k if (q[k] 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] 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 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 结构来表示一头猪的子子孙孙：每个 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 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 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))
}
十：你会被Google拒绝吗？
Max Howell 参加了Google的面试，出题人竟然要求 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 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 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/05f416aefbe190后前端妹子，爱程式设计，爱运营，文艺与程式码齐飞，魅力与智慧共存的程式媛一枚。
