一：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/05f416aefbe190后前端妹子，愛編程，愛運營，文藝與代碼齊飛，魅力與智慧共存的程序媛一枚。
