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

2022-04-02 JS

const pq = new PriorityQueue()pq.add(1)pq.add(2)pq.add(3)pq.remove() // => 3pq.remove() // => 2pq.remove() // => 1remove 方法每次删除的时候都会把最大的元素删除掉，并且返回被删除元素。请你完成 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))// }

推荐阅读

上一篇：排序算法相关知识点

下一篇：34岁的杨幂为何不再婚杨幂多大了