簡單算法 · web前端

### 一：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(''), ''); } ~~~