Codog

理解迭代

发表于 2021-08-14

堆与最大（小）K问题

发表于 2021-08-14

堆

堆，即完全二叉树，按左右节点顺序填充，可以不完整，但必须按顺序

比如 [1, 2, 3], [1, 2, 3, 4, 5]

最小堆与最大堆：

所有节点的左右子节点都大于等于当前节点的为最小堆，反之，所有节点的左右子节点值都小于等于当前节点值为最大堆。

最小堆：

最大堆：

最值问题

比如最大的第K个元素

新建大小为K的最小堆，遍历完成后，返回堆顶的元素即位最大的第K个元素（通俗掉就是第K大的元素）。

Q:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

A:
最小堆，堆大小为k，返回heap.pop()

[3,2,1,5,6,4]. => [5, 6] => 5

实现instanceof和new方法

发表于 2021-08-12

instanceof

原型链：

function myInstanceof(a, b) {
    let p = a;
    while (p) {
        if (p === b.prototype) {
            return true
        }
        p = p.__proto__
    }
    return false
}

测试一下：

myInstanceof([], Array)
true

myInstanceof([], Object)
true

myInstanceof({}, Array)
false

new

MDN上关于new的操作：

创建一个空的简单JavaScript对象（即{}）；
为步骤1新创建的对象添加属性__proto__，将该属性链接至构造函数的原型对象；
将步骤1新创建的对象作为this的上下文；
如果该函数没有返回对象，则返回this。

我们的函数也可以按照这个步骤来：

function myNew(Constructor, ...args) {
    // 1. 创建空对象
    const obj = {};

    // 2. 添加原型
    obj.__proto__ = Constructor.prototype;

    // 3. 调用构造函数，并指定this
    const res = Constructor.apply(obj, args);

    // 4. 如果构造函数返回为对象则使用之，否则返回本地对象。
    return typeof res === 'object' ? res : obj;
}