My Front End Blog

From Flower-F

0%

发表于 更新于 阅读量： Valine：
本文字数： 877

常见的继承主要有三种：

  • 组合继承
  • 寄生组合继承
  • ES6 的 class

组合继承

  • 子类的构造函数中通过 Parent.call(this) 继承父类的属性
  • 改变子类的原型为 new Parent() 来继承父类的函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Parent(val) {
    this.val = val;
}
Parent.prototype.getValue() = function() {
    return this.value;
}

function Child(val) {
    Pareng.call(this, val);
}
Child.prototype = new Parent();

const child = new Child(1);
console.log(child);
console.log(child instanceof Parent);

缺点：

  • 使用组合继承时，父类构造函数会被调用两次
  • 生成了两个实例，但是子类实例中的属性和方法会覆盖子类原型(父类实例)上的属性和方法，所以造成了子类的原型中多了一些不必要的属性，增加了不必要的内存

寄生组合继承

1
2
3
// 只要修改一行代码即可
// Child.prototype = new Parent();
Child.proptotype = Object.create(Parent.prototype);

class 继承

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Parent {
    constructor(val) {
        this.val = val;
    }
    getValue() {
        return this.val;
    }
}

class Child extends Parent {
    constructor(val) {
        super(val);
    }
}

const child = new Child(1);
console.log(child.getValue());
console.log(child instanceof Parent);

发表于 更新于 阅读量： Valine：
本文字数： 1.8k

call

  • 获取第一个参数，若不存在则为 window
  • 执行 & 删除这个函数
  • 指定 this 到函数并传入给定参数执行函数
  • 如果不传入参数，默认指向为 window
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Function.prototype.myCall = function (context, ...args) {
    // 若第一个参数传入 null 或 undefined，this 指向 window
    if (context === undefined || context === null) {
        context = window;
    }
    // 在 context 上加一个唯一值，避免影响 context 上的属性
    const key = Symbol('key');
    // 此处的 this 指的是传入的函数
    context[key] = this;
    // 调用函数
    const result = context[key](...args);
    // 删除副作用，避免 context 的属性越来越多
    delete context[key];

    return result;
}

function f(a, b) {
    console.log(a, b)
    console.log(this.name)
}
let obj = {
    name: '张三'
}
f.myCall(obj, [1, 2]);

apply

apply 与 call 几乎完全一样，只是传入的参数形式不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Function.prototype.myApply = function (context, args) {
    // 若第一个参数传入 null 或 undefined，this 指向 window
    if (context === undefined || context === null) {
        context = window;
    }
    // 在context上加一个唯一值，避免影响 context 上的属性
    const key = Symbol('key');
    // 此处的 this 指的是传入的函数
    context[key] = this;
    // 调用函数
    const result = context[key](...args);
    // 删除副作用，避免 context 的属性越来越多
    delete context[key];

    return result;
}

function f(a, b) {
    console.log(a, b)
    console.log(this.name)
}
let obj = {
    name: '张三'
}
f.myApply(obj, [1, 2]);

bind

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Function.prototype.myBind = function (context, ...args) {
    if (typeof (this) !== 'function') {
        throw new TypeError('The bound object needs to be a function');
    }
    const _this = this;

    return function newFunction() {
        // 使用了 new
        if (this instanceof newFunction) {
            return new _this(...args);
        } else {
            return _this.call(context, ...args);
        }
    }
}

let a = {
    name: 'poetries',
    age: 12
}
function foo(a, b) {
    console.log(this.name);
    console.log(this.age);
    console.log(a);
    console.log(b);
}
foo.myBind(a, 1, 2)(); // => 'poetries'

发表于 更新于 阅读量： Valine：
本文字数： 6.5k

为什么需要 Promise

JavaScript 是一门单线程编程语言，这意味着一次只能发生一件事情。在 ES6 之前，我们使用回调函数来处理异步任务，例如网络请求。使用 promise，我们可以避免臭名昭著的回调地狱，使得我们的代码更简洁、可读性更高、更容易理解。

假设我们要从服务器获取一些异步数据，使用回调函数来处理，我们可能会遇到这种情况：

1
2
3
4
5
6
7
8
9
getData(function(x){
    console.log(x);
    getMoreData(x, function(y){
        console.log(y); 
        getSomeMoreData(y, function(z){ 
            console.log(z);
        });
    });
});

这就是回调地狱，每一个回调都被嵌套在另一个回调之中，除了最外层之外，其余所有的回调函数都依赖于它们父级回调函数。

我们可以使用 Promise 重写上面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
getData()
    .then((x) => {
        console.log(x);
        return getMoreData(x);
    })
    .then((y) => {
        console.log(y);
        return getSomeMoreData(y);
    })
    .then((z) => {
        console.log(z);
    });

我们可以看到代码变得更简洁、更清晰也更易于理解了。

什么是 Promise

Promise 对象用于表示一个异步操作的最终完成（或失败）及其结果值。比如我们需要从服务器获取数据，Promise 承诺（promise）会帮我们在将来使用的时候获取到数据。

在我们讨论技术相关的问题之前，让我们先了解一下 Promise 的相关术语。

Promise 的状态

Promise 有三种状态：

  • pending：初始状态，承诺既没有被兑现，也没有被拒绝。
  • resolved / fulfilled：意味着操作成功完成。
  • rejected：意味着操作失败。

Promise 的创建

1
2
3
const promise = new Promise((resolve, reject) => {
    // ...
});

我们可以使用 Promise 构造函数来创建对象，该构造函数的参数只有一个，它是一个执行器函数，其中包括两个回调函数 resolve 和 reject。

执行器函数会在 promise 对象创建的时候就直接执行。我们可以使用 resolve 当操作成功，使用 reject 当操作失败。如下所示：

1
2
3
4
5
6
7
const promise = new Promise((resolve, reject) => {
    if (allWentWell) {
        resolve('All things went well!');
    } else {
        reject('Something went wrong');
    }
});

resolve 和 reject 可以传入一个参数，类型为 string、number、boolean、array 或 object。

我们来通过另一个例子彻底弄明白 promise 的创建。

1
2
3
4
5
6
7
8
9
10
const promise = new Promise((resolve, reject) => {
    const randomNumber = Math.random();
    setTimeout(() => {
        if (randomNumber < 0.6) {
            resolve('All things went well!');
        } else {
            reject('Something went wrong');
        }
    }, 2000);
});

在这里，我使用 Promise 构造函数创建一个新的 promise。promise 创建 2 秒后 resolve 或 reject。如果随机数小于 0.6，则 resolved，否则就 rejected。

当 promise 创建的时候，它会位于 pending 状态。

2s 后当定时器结束，根据随机数情况，promise 要么会 resolved，要么会 rejected。
resolved 的情况：

rejected 的情况：

注意：一个 promise 只能被 resolve 或者 reject 一次。多余的 resolve 或 reject 操作将不起作用。比如：

1
2
3
4
const promise = new Promise((resolve, reject) => {
    resolve('Promise resolved');  // Promise is resolved
    reject('Promise rejected');   // Promise can't be rejected
});

Promise 的使用

我们通过调用 then 和 catch 方法来使用 promise。
语法为：
.then(): promise.then(successCallback, failureCallback)
成功的时候会调用 successCallback，失败的时候会调用 failureCallback。

举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
const promise = new Promise((resolve, reject) => {
    const randomNumber = Math.random();
    if (randomNumber < 0.7) {
        resolve('All things went well!');
    } else {
        reject(new Error('Something went wrong'));
    }
});
promise.then((data) => {
    console.log(data);  // prints 'All things went well!'
}, (error) => {
    console.log(error); // prints Error object
});

.catch(): promise.catch(failureCallback)
我们可以使用 catch 来捕获错误，它的可读性要强于前面使用的 failureCallback。

1
2
3
4
5
6
7
8
9
10
const promise = new Promise((resolve, reject) => {
    reject(new Error('Something went wrong'));
});
promise
    .then((data) => {
        console.log(data);
    })
    .catch((error) => {
        console.log(error); // prints Error object
    });

链式调用

then 和 catch 函数会返回一个新的 promise 对象，所以它可以继续被捕获，从而形成链式调用。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const promise1 = new Promise((resolve, reject) => {
    resolve('Promise1 resolved');
});
const promise2 = new Promise((resolve, reject) => {
    resolve('Promise2 resolved');
});
const promise3 = new Promise((resolve, reject) => {
    reject('Promise3 rejected');
});
promise1
    .then((data) => {
        console.log(data);  // Promise1 resolved
        return promise2;
    })
    .then((data) => {
        console.log(data);  // Promise2 resolved
        return promise3;
    })
    .then((data) => {
        console.log(data);
    })
    .catch((error) => {
        console.log(error);  // Promise3 rejected
    });

解析上述代码：

  • When promise1 is resolved, the then() method is called which returns promise2.
  • The next then() is called when promise2 is resolved which returns promise3.
  • Since promise3 is rejected, the next then() is not called instead catch() is called which handles the promise3 rejection.

常见错误

很多的新手会错误地嵌套 promise，这样做依然可以正常运行，但是代码不利于阅读。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const promise1 = new Promise((resolve, reject) => {
    resolve('Promise1 resolved');
});
const promise2 = new Promise((resolve, reject) => {
    resolve('Promise2 resolved');
});
const promise3 = new Promise((resolve, reject) => {
    reject('Promise3 rejected');
});

promise1.then((data) => {
    console.log(data);  // Promise1 resolved
    promise2.then((data) => {
        console.log(data);  // Promise2 resolved

        promise3.then((data) => {
            console.log(data);
        }).catch((error) => {
            console.log(error);  // Promise3 rejected
        });
    }).catch((error) => {
        console.log(error);
    })
}).catch((error) => {
    console.log(error);
});

Promise.all()

Promise.all() 可以将多个 Promise 实例包装成一个新的 Promise 实例。同时，成功和失败的返回值是不同的，成功的时候返回的是一个结果数组，而失败的时候则返回最先被 reject 变为失败状态的值，并且 reject 的是第一个抛出的错误信息。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
const promise1 = new Promise((resolve, reject) => {
    setTimeout(() => {
        resolve('Promise1 resolved');
    }, 2000);
});
const promise2 = new Promise((resolve, reject) => {
    setTimeout(() => {
        resolve('Promise2 resolved');
    }, 1500);
});
Promise.all([promise1, promise2])
    .then((data) => console.log(data[0], data[1]))
    .catch((error) => console.log(error));

当您有多个 promise，并且希望知道所有 promise 何时可以 resolved，这个方法非常有用。例如，如果您正在从不同的 API 请求数据，并且仅当所有请求都成功时才希望对数据执行某些操作。

Promise.race()

Promise.race() 方法返回一个 promise，一旦迭代器中的某个 promise 解决或拒绝，返回的 promise 就会解决或拒绝。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
const promise1 = new Promise((resolve, reject) => {
    setTimeout(() => {
        resolve('Promise1 resolved');
    }, 1000);
});
const promise2 = new Promise((resolve, reject) => {
    setTimeout(() => {
        reject('Promise2 rejected');
    }, 1500);
});
Promise.race([promise1, promise2])
    .then((data) => console.log(data))  // Promise1 resolved
    .catch((error) => console.log(error));

Promise.any()

这个方法用于返回第一个成功的 promise 。只要有一个 promise 成功此方法就会终止，它不会等待其他的 promise 全部完成。
Promise.any() 与 Promise.race() 的区别：
不像 Promise.race() 总是返回第一个结果值（resolved / reject）那样，这个方法返回的是第一个成功的值。这个方法将会忽略掉所有被拒绝的 promise，直到第一个 promise 成功。

Promise.allSettled()

Promise.allSettled() 与 Promise.all () 的区别：

  • 它们所返回的数据不太一样，Promise.all() 返回一个直接包裹 resolve 内容的数组，则 Promise.allSettled() 返回一个包裹着对象的数组。
  • 对于 Promise.all() 来说，如果有一个 Promise 对象报错了，则 Promise.all() 无法执行，会直接报错，无法获得其他成功的数据。而 Promise.allSettled() 方法是不管有没有报错，把所有的 Promise 实例的数据都返回回来，放入到一个对象中。如果是 resolve 的数据则 status 值为 fulfilled，否则为 rejected。

原文：
https://blog.bitsrc.io/understanding-promises-in-javascript-c5248de9ff8f
参考资料：
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Promise
https://blog.csdn.net/iloveyu123/article/details/116588214

发表于 更新于 阅读量： Valine：
本文字数： 4.2k

this

如果您正在学习 JavaScript，您可能已经了解到了 this 关键字。JavaScript 中的 this 关键字的行为与其他编程语言不同，这给不少程序员带来了困惑。
在其他面向对象编程语言中，this 关键字总是指向类的当前实例。而在 JavaScript 中，它的值取决于函数的调用方式。
我们来通过一些例子说明一下 JavaScript 中的 this。

Example1

1
2
3
4
5
6
7
8
9
const person = {
    firstName: 'John',
    lastName: 'Doe',
    printName: function() {
        console.log(this.firstName + ' ' + this.lastName);
    }
};

person.printName(); // John Doe

此处因为我通过 person 对象来调用 printName 函数，所以 this 指向 person 对象。

我们在刚才的代码片段后面添加下面两行代码：

1
2
const printFullName = person.printName;
printFullName(); // undefined undefined

我们惊奇地发现打印结果是两个 undefined。

原因是什么？
此处我们把 person.printName 的引用存储到了变量 printFullName 中。此后，我们调用它，且没有指明调用它的对象。这种情况下，this 会指向 window 或 undefined（严格模式下）。

因此会输出两个 undefined；若是在严格模式下则会报错。

Example 2

1
2
3
4
5
6
7
8
const counter = {
    count: 0,
    incrementCounter: function() {
        console.log(this);
        this.count++;
    }
}
document.querySelector('.btn').addEventListener('click', counter.incrementCounter);

incrementCounter 中的 this 将会指向谁呢？
事实上，在上面的代码中，this 关键字会指向 event 对象，而不是 counter 对象。

根据前面所举的例子，我们可以发现函数中的 this 关键字指向根据函数的调用情况决定。有时候我们会一不小心丢失掉 this。那么我们如何才能防止这种情况的发生呢？

call、bind、apply

我们知道在 JavaScript 中函数是一种特殊的对象，所以我们可以获取它的方法和属性。为了证明函数也是对象，我们可以做一些诸如下面这样的操作：

1
2
3
4
5
6
function greeting() {
    console.log('Hello World');
}
greeting.lang = 'English';
// Prints 'English'
console.log(greeting.lang);

JavaScript 也提供了一些特殊的方法和属性给每一个函数对象。所以 JavaScript 中的每个函数都继承了一些方法，其中就包括 call、apply、bind。

bind

bind 创建一个新的函数，并把 this 指向传入的对象。
语法为：

1
function.bind(thisArg, arg1, arg2, ...)

举个例子，假如我们有两个人物对象。

1
2
3
4
5
6
7
8
9
10
11
12
const john = {
    name: 'John',
    age: 24,
};
const jane = {
    name: 'Jane',
    age: 22,
};

function greeting() {
  console.log(`Hi, I am ${this.name} and I am ${this.age} years old`);
}

我们可以使用 bind 方法来让 this 指向 john 和 jane 对象。

1
2
3
4
5
6
const greetingJohn = greeting.bind(john);
// Hi, I am John and I am 24 years old
greetingJohn();
const greetingJane = greeting.bind(jane);
// Hi, I am Jane and I am 22 years old
greetingJane();

此处 greeting.bind(john) 创建了一个新的函数，且 this 指向了传入的 john 对象，接着把它赋值给了变量 greetingJohn

我们也可以使用 bind 来 DOM 操作的情况，比如：

1
2
3
4
5
6
7
8
const counter = {
    count: 0,
    incrementCounter: function() {
        console.log(this);
        this.count++;
    }
}
document.querySelector('.btn').addEventListener('click', counter.incrementCounter.bind(counter));

在上面的例子中，this 会正确地指向 counter 对象而不是 event 对象。

注意：多次 bind() 是无效的，只会绑定到第一次调用的对象上

bind 接收多个参数

bind 可以接收多个参数。

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
function greeting(lang) {
    console.log(`${lang}: I am ${this.name}`);
}
const john = {
    name: 'John'
};
const jane = {
    name: 'Jane'
};
const greetingJohn = greeting.bind(john, 'en');
greetingJohn();
const greetingJane = greeting.bind(jane, 'es');
greetingJane();

在上面的例子中，我们把参数 en 传递给了 greeting 函数。

call

call 会将 this 指向对象，并立即执行。
call 和 bind 的区别在于，call 会使函数立即执行，而 bind 会创建一个新的函数，不会马上执行。

语法：

1
function.call(thisArg, arg1, arg2, ...)

举个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function greeting() {
    console.log(`Hi, I am ${this.name} and I am ${this.age} years old`);
}
const john = {
    name: 'John',
    age: 24,
};
const jane = {
    name: 'Jane',
    age: 22,
};
// Hi, I am John and I am 24 years old
greeting.call(john);
// Hi, I am Jane and I am 22 years old
greeting.call(jane);

上面例子我们可以看出 call 的结果是立即执行该函数。

call 接收多个参数

call 可以接收多个参数。

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function greet(greeting) {
    console.log(`${greeting}, I am ${this.name} and I am ${this.age} years old`);
}
const john = {
    name: 'John',
    age: 24,
};
const jane = {
    name: 'Jane',
    age: 22,
};
// Hi, I am John and I am 24 years old
greet.call(john, 'Hi');
// Hello, I am Jane and I am 22 years old
greet.call(jane, 'Hello');

apply

apply 和 call 非常相像，不同之处在于 apply 的参数是一个数组，而 call 的参数是分散开的。

示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function greet(greeting, lang) {
    console.log(lang);
    console.log(`${greeting}, I am ${this.name} and I am ${this.age} years old`);
}
const john = {
    name: 'John',
    age: 24,
};
const jane = {
    name: 'Jane',
    age: 22,
};
// Hi, I am John and I am 24 years old
greet.apply(john, ['Hi', 'en']);
// Hello, I am Jane and I am 22 years old
greet.apply(jane, ['Hello', 'es']);

原文：
https://blog.bitsrc.io/understanding-call-bind-and-apply-methods-in-javascript-33dbf3217be

发表于 更新于 阅读量： Valine：
本文字数： 4.2k

什么是作用域

JavaScript 中的作用域是指变量的可访问性或可见性。也就是说，程序的哪些部分可以访问变量。

作用域的重要性

  • 作用域的主要好处是具有安全性。也就是说，变量只能从程序的某些区域访问。通过作用域，我们可以避免对程序其他部分的变量进行意外的修改。
  • 作用域可以减小命名空间的冲突。也就是说，在不同的作用域中，我们可以使用同名的变量。

作用域的种类

作用域有三种类型：

  • 全局作用域
  • 函数作用域
  • 块级作用域

全局作用域

不在任何函数或块（一对花括号）内的变量都在全局作用域内。全局作用域内的变量可以从程序中的任何位置访问。例如：

1
2
3
4
5
6
var greeting = 'Hello World!';
function greet() {
    console.log(greeting);
}
// Prints 'Hello World!'
greet();

函数作用域

函数中声明的变量在函数作用域内，这些变量只能从该函数的内部访问，不能从外部区域访问。例如：

1
2
3
4
5
6
7
8
function greet() {
    var greeting = 'Hello World!';
    console.log(greeting);
}
// Prints 'Hello World!'
greet();
// Uncaught ReferenceError: greeting is not defined
console.log(greeting);

块级作用域

对于 ES6 的 let 和 const 关键字声明的变量，不像 var 声明的变量，它们可以通过最近的一对花括号形成块级作用域。也就是说，在花括号外部不能访问花括号里面声明的变量。例如：

1
2
3
4
5
6
7
8
9
{
    let greeting = 'Hello World!';
    var lang = 'English';
    console.log(greeting); // Prints 'Hello World!'
}
// Prints 'English'
console.log(lang);
// Uncaught ReferenceError: greeting is not defined
console.log(greeting);

作用域的嵌套

就像 JavaScript 的函数一样，一个作用域可以被另一个作用域包裹。例如：

1
2
3
4
5
6
7
8
9
var name = 'Peter';
function greet() {
    var greeting = 'Hello';
    {
        let lang = 'English';
        console.log(`${lang}: ${greeting} ${name}`);
    }
}
greet();

这里有三个彼此嵌套的作用域，包括前面所说的全局作用域、块级作用域、函数作用域。

词法作用域

词法作用域（又称静态作用域）的字面意思是在词法分析时（通常称为编译）而不是在运行时确定作用域。例如：

1
2
3
4
5
6
7
8
9
10
let number = 42;
function printNumber() {
    console.log(number);
}
function log() {
    var number = 54;
    printNumber();
}
// Prints 42
log();

这里 console.log(number) 会始终打印出 42，不管函数 printNumber 在什么时候被调用。这与具有动态作用域的语言不同，支持动态作用域的语言中函数的执行结果可能会受其它函数调用的影响。比如上面的代码中，如果是用一种支持动态作用域的语言编写的话，那么 console.log(number) 的输出结果应该是 54。
使用词法作用域，我们可以通过查看源代码来确定变量的作用域。然而，在动态作用域的情况下，只有执行代码才能确定作用域。
大多数编程语言支持静态作用域，如C、C++、java、JavaScript。Perl 支持静态和动态两种作用域。

什么是作用域链

在 JavaScript 中使用变量时，JavaScript 引擎将尝试在当前作用域内查找变量的值。如果找不到变量，它将查看外部的作用域，并将继续这样做，直到找到变量或到达全局作用域。
如果仍然找不到变量，它将在全局作用域内隐式声明变量（如果不是在严格模式下），或者返回错误（严格模式下）。

1
2
3
4
5
6
7
8
9
10
11
12
let foo = 'foo';
function bar() {
    let baz = 'baz';
    // Prints 'baz'
    console.log(baz);
    // Prints 'foo'
    console.log(foo);
    number = 42;
    console.log(number);  // Prints 42
}
bar();
console.log(number); // 42

当函数 bar 被执行时，JavaScript 引擎会去寻找变量 baz，然后在当前作用域找到了。接着，它会去寻找变量 foo，然后发现无法在当前作用域中找到。所以它会去外部的作用域中寻找，然后成功找到了该变量。
之后，JavaScript 会在当前作用域和外部作用域中寻找 number 变量，但是发现找不到。此时如果是非严格模式，会在全局声明一个变量 number 并给它赋值 42；若是在严格模式下，将会报错。
总而言之，当一个变量被使用的时候，JavaScript 引擎会沿着作用域链去遍历这个变量直到找到或到达全局作用域。

作用域和作用域链的工作原理

为了理解作用域和作用域链的作用原理，我们必须先理解词法环境的概念。

什么是词法环境

词法环境是用于保存 标识符-变量 的映射的结构。这里标识符是指变量/函数的名称，变量是对实际对象（包括函数对象和数组对象）或基本类型的引用。

简而言之，词法环境是存储变量和对象引用的地方。

注意：不要混淆词法作用域和词法环境，词法作用域是在编译时确定的一个范围，词法环境是在程序执行期间存储变量的地方。

一个词法环境可以被抽象地表示如下：

1
2
3
4
lexicalEnvironment = {
    a: 25,
    obj: <ref. to the object>
}

当词法作用域中的代码执行时，每个词法作用域中会创建一个新的词法环境。词法环境也有对外部词法环境（即外部作用域）的引用。例如：

1
2
3
4
5
lexicalEnvironment = {
    a: 25,
    obj: <ref. to the object>
    outer: <outer lexical environemt>
}

JavaScript 引擎如何进行变量的查找

现在我们知道了什么是作用域、作用域链和词法环境，下面让我们了解 JavaScript 引擎如何使用词法环境来确定作用域和作用域链。以下面代码为例：

1
2
3
4
5
6
7
8
9
10
let greeting = 'Hello';
function greet() {
    let name = 'Peter';
    console.log(`${greeting} ${name}`);
}
greet();
{
    let greeting = 'Hello World!'
    console.log(greeting);
}

加载上述脚本时，将创建一个全局词法环境，其中包含在全局作用域内定义的变量和函数。如下所示：

1
2
3
4
5
globalLexicalEnvironment = {
    greeting: 'Hello'
    greet: <ref. to greet function>
    outer: <null>
}

外部作用域设置为 null 的原因是没有全局作用域外部没有别的作用域了。

此后遇到了一个 greet 函数的调用。所以 greet 函数的词法环境会被创建。如下所示：

1
2
3
4
functionLexicalEnvironment = {
    name: 'Peter'
    outer: <globalLexicalEnvironment>
}

此后，JavaScript 引擎会执行 console.log(${greeting} ${name}) 语句。
JavaScript 引擎尝试在函数的词法环境中查找变量 greeting 和 name。它在当前词法环境中找到了 name 变量，但在当前词法环境中找不到 greeting 变量。

所以它去外部的词法环境（此处指全局词法环境）寻找 greeting 变量，并成功找到。

接下来，JavaScript 引擎要执行块内的代码。因此，它为该块创建了一个新的词法环境。如下所示：

1
2
3
4
blockLexicalEnvironment = {
    greeting: 'Hello World',
    outer: <globalLexicalEnvironment>
}

接着 console.log(greeting) 语句被执行，JavaScript 引擎会在当前此法环境找到 greeting 变量。

注意：新的词法环境只会被 let 和 const 声明创建，而不会被 var 声明创建。var 声明会被添加到当前的词法环境中（全局词法环境或函数词法环境）

总而言之，当在程序中使用变量时，JavaScript 引擎将尝试在当前词法环境中查找该变量，如果在当前词法环境中找不到该变量，它将在外部词法环境中查找该变量。这就是 JavaScript 引擎执行变量查找的方法。

原文：
https://blog.bitsrc.io/understanding-scope-and-scope-chain-in-javascript-f6637978cf53

发表于 更新于 阅读量： Valine：
本文字数： 5.4k

JavaScript 是一种单线程编程语言，这意味着每次只能做一件事情。也就是说，JavaScript 引擎在每个线程中一次只能处理一条语句。虽然单线程语言简化了代码的编写，因为您不必担心并发性问题，但这也意味着您无法在不阻塞主线程的情况下执行长时间操作，如网络访问。

JavaScript 同步工作原理

在深入研究异步 JavaScript 之前，让我们首先了解同步 JavaScript 代码在 JavaScript 引擎中是如何执行的。举个例子：

1
2
3
4
5
6
7
8
9
const second = () => {
    console.log('Hello there!');
}
const first = () => {
    console.log('Hi there!');
    second();
    console.log('The End');
}
first();

为了理解上面的代码在 JavaScript 引擎中是如何执行的，我们必须要理解执行上下文和调用栈（又称执行栈）的概念

执行上下文

执行上下文是一个关于解析和执行 JavaScript 代码的环境的抽象概念。任何代码在 JavaScript 中运行时，实际上都是在执行上下文中运行。函数代码在函数执行上下文中执行，全局代码在全局执行上下文中执行。每个函数都有自己的执行上下文。

调用栈

调用栈是一个具有后进先出结构的栈，用于存储代码执行期间创建的所有执行上下文。
JavaScript 只有一个单调栈，因为它是一门单线程编程语言。调用栈具有后进先出结构，这意味着只能从栈顶进行添加或删除操作。
我们重新理解一下上面给出的代码片段：

1
2
3
4
5
6
7
8
9
const second = () => {
    console.log('Hello there!');
}
const first = () => {
    console.log('Hi there!');
    second();
    console.log('The End');
}
first();

上述代码的调用栈

JavaScript 异步工作原理

现在我们已经了解了调用栈的基本概念，以及同步 JavaScript 的工作原理，现在让我们再回到异步 JavaScript。

什么是阻塞

现在假设我们的图片加载和网络请求操作是同步进行，就像下面的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const processImage = (image) => {
    /**
    * doing some operations on image
    **/
    console.log('Image processed');
}
const networkRequest = (url) => {
    /**
    * requesting network resource
    **/
    return someData;
}
const greeting = () => {
    console.log('Hello World');
}
processImage(logo.jpg);
networkRequest('www.somerandomurl.com');
greeting();

进行图像处理和网络请求需要时间。因此，当调用 processImage 函数时，需要花费一些时间，具体取决于图像的大小。
当 processImage 函数完成时，它将从调用栈中删除。然后调用 networkRequest 函数并将其压入栈中。同样，它的执行也需要一些时间。
最后，当 networkRequest 函数完成时，会调用 greeting 函数，因为它只包含一条 console.log 语句，而且 console.log 语句执行得通常很快，因此会接着立即执行 greeting 函数。
因此，我们必须等到函数 processImage 和 networkRequest 完成。这意味着这些函数将会阻塞调用栈，也即是阻塞主线程。因此，在执行上述代码时，我们不能执行任何其他操作，这是不理想的，因为会造成不好的用户体验。

解决方案

最简单普遍的一种方法是使用异步的调用栈。我们通过使用异步的调用栈来使得我们的代码不会阻塞。比如：

1
2
3
4
5
6
7
const networkRequest = () => {
    setTimeout(() => {
        console.log('Async Code');
    }, 2000);
};
console.log('Hello World');
networkRequest();

这里我用 setTimeout 函数来模拟网络请求。请牢记 setTimeout 不是 Javascript 引擎的一部分，而是 web API 的一部分。（在 Nodejs 中，web API 被 C/C++ API 所取代）
为了理解这段代码是如何执行的，我们需要了解更多的相关概念，比如事件循环和任务队列（也叫消息队列）。

JavaScript 运行时环境的概述

事件循环、web API 和任务队列不是 JavaScript 引擎的一部分，而是浏览器 JavaScript 运行时环境或 Nodejs 的 JavaScript 运行时环境的一部分。（在 Nodejs 中，web API 被 C/C++ API 所取代）

现在让我们回到上面的代码，看看它是如何以异步方式执行的。

1
2
3
4
5
6
7
8
const networkRequest = () => {
    setTimeout(() => {
        console.log('Async Code');
    }, 2000);
};
console.log('Hello World');
networkRequest();
console.log('The End');

当上述代码被加载到浏览器中时，console.log(‘Hello World’) 被压入执行栈，并在完成执行后弹出执行栈。接下来，遇到了一个 networkRequest 函数的调用，所以它的执行上下文被压入栈中。
接着 setTimeout函数被调用了，所以它被压入栈中。setTimeout 函数有两个参数，第一个是回调函数，第二个是延迟的时间（单位是 ms）。
setTimeout 函数在 web API 环境下开启了一个时长 2s 的定时器。此时，setTimeout 函数已经执行完成并从栈中弹出。此后，console.log('The End') 被压入调用栈，执行完成后从栈中移出。
接着，当定时器计时时间到达，回调函数被压入到任务队列中。但是任务队列中的回调函数不会被立即执行，这时候事件循环开始起作用了。

事件循环

事件循环的任务是查看调用栈并确定调用栈是否为空。如果调用栈为空，它将查看任务队列，查看是否有任何回调函数在等待执行。
在这个例子中，任务队列中有一个回调函数，而且调用栈是空的，所以事件循环会把这个回调函数压入调用栈中，也就是把 console.log(‘Async Code’) 压入调用栈，执行并从栈中弹出。此后，全局代码调用结束，全局执行上下文从栈中弹出，然后程序运行完成。

DOM 事件

任务队列中也包含 DOM 中的事件操作，比如点击事件、键盘事件等。比如：

1
2
3
document.querySelector('.btn').addEventListener('click',(event) => {
    console.log('Button Clicked');
});

在这个例子中，事件监听器位于 web API 环境中，并等待某个事件（在本例中为点击事件）发生。当该事件发生时，回调函数会被存储进消息队列中等待执行。事件循环会检查调用栈是否为空，如果为空，则将任务队列中事件的回调函数压入栈中并执行。

ES6 的微任务队列

ES6 引入了微任务队列的概念，用于 Promise 的相关操作。宏任务队列和微任务队列之间的区别在于，微任务队列的优先级高于宏任务队列，这意味着微任务队列中的回调函数执行将优先于宏任务队列中的回调函数。

举个例子：

1
2
3
4
5
6
7
8
9
console.log('Script start');
setTimeout(() => {
    console.log('setTimeout');
}, 0);
new Promise((resolve) => {
    resolve('Promise resolved');
}).then(res => console.log(res))
    .catch(err => console.log(err));
console.log('Script End');

输出如下：

1
2
3
4
Script start
Script End
Promise resolved
setTimeout

可见 promise 是先于 setTimeout 函数执行的，因为 promise 的 response 会被存储在微任务队列，优先级高于宏任务队列。

我们来看第二个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
console.log('Script start');
setTimeout(() => {
    console.log('setTimeout 1');
}, 0);
setTimeout(() => {
    console.log('setTimeout 2');
}, 0);
new Promise((resolve) => {
    resolve('Promise 1 resolved');
}).then(res => console.log(res))
    .catch(err => console.log(err));
new Promise((resolve) => {
    resolve('Promise 2 resolved');
}).then(res => console.log(res))
    .catch(err => console.log(err));
console.log('Script End');

输出为

1
2
3
4
5
6
Script start
Script End
Promise 1 resolved
Promise 2 resolved
setTimeout 1
setTimeout 2

我们可以看到，这两个 promise 是在 setTimeout 中的回调函数之前执行的，因为事件循环认为微任务队列中的任务优先于宏任务队列中的任务。
当事件循环执行微任务队列中的任务时，如果在此期间存在一个 promise 已经 resolve 了，它将被添加到同一个微任务队列的末尾，并且无论回调等待执行的时间有多长，它都将在宏任务队列中的回调执行之前执行。

比如下面这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
console.log('Script start');
setTimeout(() => {
    console.log('setTimeout');
}, 0);
new Promise((resolve) => {
    resolve('Promise 1 resolved');
}).then(res => console.log(res));
new Promise((resolve) => {
    resolve('Promise 2 resolved');
}).then(res => {
    console.log(res);
    return new Promise((resolve) => {
        resolve('Promise 3 resolved');
    })
}).then(res => console.log(res));
console.log('Script End');

执行结果为

1
2
3
4
5
6
Script start
Script End
Promise 1 resolved
Promise 2 resolved
Promise 3 resolved
setTimeout

因此，微任务队列中的所有任务都将在宏任务队列中的任务之前执行。也就是说，在执行宏任务队列中的任何回调函数之前，事件循环将首先清空微任务队列。

原文：
https://blog.bitsrc.io/understanding-asynchronous-javascript-the-event-loop-74cd408419ff

发表于 更新于 阅读量： Valine：
本文字数： 1.3k

题目链接：
https://leetcode-cn.com/problems/edit-distance/

定义 dp[i][j] 的含义为：word1 的前 i 个字符和 word2 的前 j 个字符的编辑距离。意思就是 word1 的前 i 个字符，变成 word2 的前 j 个字符，最少需要这么多步。

边界：如果其中一个字符串是空串，那么编辑距离是另一个字符串的长度。比如空串 “” 和 “ro” 的编辑距离是 2（做两次“插入”操作）。再比如 “hor” 和空串 “” 的编辑距离是 3（做三次 “删除” 操作）。

状态转移：
对于每对字符 s1[i] 和 s2[j]，可以有四种操作：

1
2
3
4
5
6
7
8
if s1[i] == s2[j]:
    啥都别做（skip）
    i, j 同时向前移动
else:
    三选一：
        插入（insert）
        删除（delete）
        替换（replace）
  • word1 执行插入操作：在 s1[i] 插入一个和 s2[j] 一样的字符，那么 s2[j] 就被匹配了。然后移动 j，让 i 和下一个 j 匹配。dp[i][j] = dp[i][j - 1] + 1
  • word1 执行删除操作：直接把 s1[i] 字符删除，那么 s2[j] 就被匹配了。然后继续移动 i，让新的 i 与原来的 j 匹配。dp[i][j] = dp[i - 1][j] + 1
  • word1 执行替换操作：直接把 s1[i] 替换成 s2[j]，这样它们就匹配了。然后 i 和 j 同时移动，进行下一个字符的比较。dp[i][j] = dp[i - 1][j - 1] + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

    // 边界
    for (let i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = j;
    }

    // dp
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1);
            }
        }
    }

    return dp[m][n];
};

参考题解：

  1. https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
  2. https://labuladong.gitee.io/algo/3/23/73/

发表于 更新于 阅读量： Valine：
本文字数： 4.9k

复习手写排序

冒泡排序

冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function bubbleSort(arr) {
    const len = arr.length;
    if (!Array.isArray(arr) || len <= 1) {
        return arr;
    }

    for (let i = 0; i < len; i++) {
        let flag = false; // 标记是否发生了交换
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                flag = true;
            }
        }
        if (!flag) {
            return arr;
        }
    }
    return arr;
}

为什么第二层循环的结束下标是 len - 1 - i？
随着外层循环的进行，数组尾部的元素会渐渐变得有序当我们走完第 1 轮循环的时候，最大的元素被排到了数组末尾；走完第 2 轮循环的时候，第 2 大的元素被排到了数组倒数第 2 位；走完第3轮循环的时候，第 3 大的元素被排到了数组倒数第 3 位……以此类推，走完第 n 轮循环的时候，数组的后 n 个元素就已经是有序的，所以后面的部分就不需要再排序了。

选择排序

选择排序的基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量 min，每一次比较仅存储较小元素的数组下标，当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function selectSort(arr) {
    const len = arr.length;
    if (!Array.isArray(arr) || len <= 1) {
        return arr;
    }

    let minIndex;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

插入排序

直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function insertSort(arr) {
    const len = arr.length;
    if (!Array.isArray(arr) || len <= 1) {
        return arr;
    }

    for (let i = 1; i < len; i++) {
        let j = i;
        let temp = arr[i];

        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--;
        }

        arr[j] = temp;
    }

    return arr;
}

归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。递归的将数组两两分开直到只包含一个元素，然后将数组排序合并，最终合并为排序好的数组。
模拟过程

  • 递归分割
  • [8, 7, 6, 5, 4, 3, 2, 1]
  • [8, 7, 6, 5,| 4, 3, 2, 1]
  • [8, 7,| 6, 5,| 4, 3,| 2, 1]
  • [8,| 7,| 6,| 5,| 4,| 3,| 2,| 1]
  • 合并
  • [7, 8,| 5, 6,| 3, 4,| 1, 2]
  • [5, 6, 7, 8,| 1, 2, 3, 4]
  • [1, 2, 3, 4, 5, 6, 7, 8]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function mergeSort(arr) {
    const len = arr.length;
    if (len <= 1) {
        if (!Array.isArray(arr) || len <= 1) return arr;
    }
    // 分割点
    const mid = Math.floor(len / 2);
    // 递归分割左子数组
    const left = mergeSort(arr.slice(0, mid));
    // 递归分割右子数组
    const right = mergeSort(arr.slice(mid, len));
    // 合并左右两个有序数组
    arr = merge(left, right);

    return arr;
}

function merge(arr1, arr2) {
    let i = 0, j = 0;
    const res = [];
    const len1 = arr1.length, len2 = arr2.length;
    while (i < len1 && j < len2) {
        if (arr1[i] < arr2[j]) {
            res.push(arr1[i]);
            i++;
        } else {
            res.push(arr2[j]);
            j++;
        }
    }

    // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
    if (i < len1) {
        return res.concat(arr1.slice(i));
    } else {
        return res.concat(arr2.slice(j));
    }
}

快速排序

快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function quickSort(arr, left = 0, right = arr.length - 1) {
  const len = arr.length;
  if (!Array.isArray(arr) || len <= 1) {
    return arr;
  }
  if (left < right) {
    const index = partion(arr, left, right);
    quickSort(arr, left, index - 1);
    quickSort(arr, index + 1, right);
  }

  return arr;
}

// 以基准值为轴心，划分左右子数组的过程
function partion(arr, left, right) {
  if (right > left) {
    // 随机快排，防止遇到有序数组导致复杂度降到 n 方
    let randomIndex = Math.floor(Math.random() * (right - left)) + left + 1;
    [arr[left], arr[randomIndex]] = [arr[randomIndex], arr[left]];
  }

  const pivot = arr[left];
  let i = left, j = right;

  while (i < j) {
    // 此处必须先移动 j 后移动 i
    while (i < j && arr[j] >= pivot) j--;
    while (i < j && arr[i] <= pivot) i++;

    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  [arr[i], arr[left]] = [arr[left], arr[i]];
  return i;
}

const ans = quickSort([5, 1, 1, 2, 0, 0]);

console.log(ans);

堆排序

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余 n - 1 个元素重新构造成一个堆，这样会得到 n 个元素的次小值。如此反复执行，便能得到一个有序序列了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function heapSort(arr) {
    const len = arr.length;

    if (!Array.isArray(arr) || len <= 1) return arr;

    buildMaxHeap(arr); // 将传入的数组建立为大根堆

    // 每次循环，将首个元素（即最大元素）与末尾元素交换，然后剩下的元素重新构建为大根堆
    for (let i = len - 1; i >= 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        adjustMaxHeap(arr, 0, i);
    }

    return arr;
}

function adjustMaxHeap(arr, root, heapSize) {
    let maxIndex, lchild, rchild;
    while (true) {
        maxIndex = root; // 根所在值即最大值
        lchild = root * 2 + 1; // 左孩子下标
        rchild = root * 2 + 2; // 右孩子下标

        // 如果左子元素存在，且左子元素大于最大值，则更新最大值索引
        if (lchild < heapSize && arr[maxIndex] < arr[lchild]) {
            maxIndex = lchild;
        }

        // 如果右子元素存在，且右子元素大于最大值，则更新最大值索引
        if (rchild < heapSize && arr[maxIndex] < arr[rchild]) {
            maxIndex = rchild;
        }

        // 如果最大元素被更新了，则交换位置，以保证根的值最大，同时还要更新根的值
        if (maxIndex !== root) {
            [arr[root], arr[maxIndex]] = [arr[maxIndex], arr[root]];
            root = maxIndex;
        } else {
            // 如果未被更新，说明该子树满足大根堆的要求，退出循环
            break;
        }
    }
}

function buildMaxHeap(arr) {
    const len = arr.length, lastElem = len >> 1 - 1; // 数组长度，最后一个非叶子元素

    for (let i = len; i >= 0; i--) {
        adjustMaxHeap(arr, i, len);
    }
}

参考资料：
https://juejin.cn/book/6844733800300150797/section/6844733800367439885
https://www.kancloud.cn/pillys/qianduan/2051370

发表于 更新于 阅读量： Valine：
本文字数： 1.1k

题目链接：
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

解法分析：快排变种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    let left = 0, right = nums.length - 1;
    let target = nums.length - k;
    while (left <= right) {
        const index = partition(nums, left, right);
        if (index === target) {
            return nums[index];
        } else if (index < target) {
            left = index + 1;
        } else if (index > target) {
            right = index - 1;
        }
    }
    return -1;

    function partition(nums, left, right) {
        if (right > left) {
            let randomIndex = Math.floor(Math.random() * (right - left)) + left + 1;
            [nums[left], nums[randomIndex]] = [nums[randomIndex], nums[left]];
        }

        const pivot = nums[left];
        let i = left, j = right;

        while (i < j) {
            while (nums[j] >= pivot && i < j) j--;
            while (nums[i] <= pivot && i < j) i++;

            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
        [nums[i], nums[left]] = [nums[left], nums[i]];

        return i;
    }
};

参考题解：
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/

发表于 更新于 阅读量： Valine：
本文字数： 1.1k

题目链接：
https://leetcode-cn.com/problems/permutations/
解法分析：
解决一个回溯问题，实际上就是一个决策树的遍历过程。只需要思考 3 个问题：

  • 路径：也就是已经做出的选择
  • 选择列表：也就是你当前可以做的选择
  • 结束条件：也就是到达决策树底层，无法再做选择的条件

比如：

回溯的通用解法:

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

核心可以用一句话总结：在递归之前做出选择，在递归之后撤销刚才的选择。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const res = [];
    const set = new Set(); // set 用于记录是否访问过，也可以开一个 vis 数组标记
    backtrack([]);
    return res;

    function backtrack(path) {
        // 回溯边界
        if (path.length === nums.length) {
            res.push(path.concat());
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (!set.has(i)) {
                path.push(nums[i]); // 做选择
                set.add(i); // 标记

                backtrack(path);

                path.pop(); // 撤销选择
                set.delete(i); // 取消标记
            }
        }        
    }
};

参考题解：

  1. https://labuladong.gitee.io/algo/1/5/
  2. https://gitee.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3%E4%BF%AE%E8%AE%A2%E7%89%88.md#javascript