image frame

四月八日

栈

算法 / 数据结构

有两种类似于数组的数据结构在添加和删除元素时更为可控，它们就是栈和队列。

栈数据结构

栈是一种遵从后进先出（LIFO）原则的有序集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class stack {
    constructor() {
        this.items = [];
    }
    push(...elements) {
        return this.items.push(...elements)
    }
    pop() {
        return this.items.pop()
    }
    peek() {
        return this.items[this.items.length - 1];
    }
    isEmpty() {
        return Boolean(this.items.length)
    }
    clear() {
        this.items = [];
    }
    size() {
        return this.items.length;
    }
}

对于大量数据的使用使用一个对象来存储数据，查询效率更高

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
class stack {
    constructor() {
        this.count = 0;
        this.items = {};
    }
    push(...elements) {
        this.items[this.count] = elements;
        this.count++;
    }
    pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        this.count--;
        const element = this.items[this.count]
        delete this.items[this.count]
        return element;
    }
    peek() {
        if (isEmpty()) {
            return undefined;
        }
        return this.items[this.count - 1];
    }
    isEmpty() {
        return this.count === 0;
    }
    clear() {
        this.items = {};
        this.count = 0;
    }
    size() {
        return this.count + 1;
    }
    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let objString = `${this.items[0]}`; // {1}
        for (let i = 1; i < this.count; i++) { // {2}
            objString = `${objString},${this.items[i]}`; // {3}
        }
        return objString;
    }
}

私有属性/方法

新的提案通过#来声明私有属性

现阶段通过设置 Proxy 来禁止对类属性的访问

进制转换

十进制转二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function decimalToBinary(decNumber) {
  const remStack = new Stack();
  let number = decNumber;
  let rem;
  let binaryString = '';
  while (number > 0) { // {1}
    rem = Math.floor(number % 2); // {2}
    remStack.push(rem); // {3}
    number = Math.floor(number / 2); // {4}
  }
  while (!remStack.isEmpty()) { // {5}
    binaryString += remStack.pop().toString();
  }
  return binaryString;
}

和其他任意的进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function convert(decNumber, base) {
  const remStack = [];
  const digs = '0123456789abcdefghijklmnopqrstuvwxyz'
  let number = decNumber;
  let rem;
  let binaryString = '';
  while (number > 0) {
    rem = Math.floor(number % base);
    remStack.push(rem);
    number = Math.floor(number / base);
  }
  while (!remStack.isEmpty()) { // {5}
    binaryString += digs[remStack.pop()];

    return binaryString;
  }
}

Object新特性

JavaScript

属性的简洁表示法

1
2
const foo = 'bar';
const baz = {foo};

属性名表达式

性名表达式如果是一个对象，默认情况下会自动将对象转为字符串[object Object]

1
2
3
4
5
6
let propKey = 'foo';

let obj = {
  [propKey]: true,
  ['a' + 'bc']: 123
};

方法的 name 属性

函数的name属性，返回函数名。对象方法也是函数，因此也有name属性。

如果对象的方法使用了取值函数（getter）和存值函数（setter），则name属性不是在该方法上面，而是该方法的属性的描述对象的get和set属性上面，返回值是方法名前加上get和set。

1
2
3
4
5
6
7
8
9
10
11
12
const obj = {
  get foo() {},
  set foo(x) {}
};

obj.foo.name
// TypeError: Cannot read property 'name' of undefined

const descriptor = Object.getOwnPropertyDescriptor(obj, 'foo');

descriptor.get.name // "get foo"
descriptor.set.name // "set foo"

有两种特殊情况：bind方法创造的函数，name属性返回bound加上原函数的名字；Function构造函数创造的函数，name属性返回anonymous。

1
2
3
4
5
6
(new Function()).name // "anonymous"

var doSomething = function() {
  // ...
};
doSomething.bind().name // "bound doSomething"

如果对象的方法是一个 Symbol 值，那么name属性返回的是这个 Symbol 值的描述。

1
2
3
4
5
6
7
8
const key1 = Symbol('description');
const key2 = Symbol();
let obj = {
  [key1]() {},
  [key2]() {},
};
obj[key1].name // "[description]"
obj[key2].name // ""

属性的可枚举性和遍历

可枚举性

对象的每个属性都有一个描述对象（Descriptor），用来控制该属性的行为。Object.getOwnPropertyDescriptor方法可以获取该属性的描述对象。

1
2
3
4
5
6
7
8
let obj = { foo: 123 };
Object.getOwnPropertyDescriptor(obj, 'foo')
//  {
//    value: 123,
//    writable: true,
//    enumerable: true,
//    configurable: true
//  }

有四个操作会忽略enumerable为false的属性。

  • for...in循环：只遍历对象自身的和继承的可枚举的属性。

  • Object.keys()：返回对象自身的所有可枚举的属性的键名。

  • JSON.stringify()：只串行化对象自身的可枚举的属性。

  • Object.assign()： 忽略enumerable为false的属性，只拷贝对象自身的可枚举的属性。

Class 的原型的方法都是不可枚举的。

1
2
Object.getOwnPropertyDescriptor(class {foo() {}}.prototype, 'foo').enumerable
// false

操作中引入继承的属性会让问题复杂化，大多数时候，我们只关心对象自身的属性。所以，尽量不要用for...in循环，而用Object.keys()代替。

属性的遍历

  • for...in循环遍历对象自身的和继承的可枚举属性（不含 Symbol 属性）。

  • Object.keys返回一个数组，包括对象自身的（不含继承的）所有可枚举属性（不含 Symbol 属性）的键名。

  • Object.getOwnPropertyNames返回一个数组，包含对象自身的所有属性（不含 Symbol 属性，但是包括不可枚举属性）的键名。

  • Object.getOwnPropertySymbols返回一个数组，包含对象自身的所有 Symbol 属性的键名。

  • Reflect.ownKeys返回一个数组，包含对象自身的（不含继承的）所有键名，不管键名是 Symbol 或字符串，也不管是否可枚举。

以上的 5 种方法遍历对象的键名，都遵守同样的属性遍历的次序规则。

  • 首先遍历所有数值键，按照数值升序排列。

  • 其次遍历所有字符串键，按照加入时间升序排列。

  • 最后遍历所有 Symbol 键，按照加入时间升序排列。

super 关键字

super 指向当前对象的原型对象。

super关键字表示原型对象时，只能用在对象的方法之中，用在其他地方都会报错。

也不可以直接调用super对象，只能调用super下面的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 报错
const obj = {
  foo: super.foo
}

// 报错
const obj = {
  foo: () => super.foo
}

// 报错
const obj = {
  foo: function () {
    return super.foo
  }
}

//报错
const obj = {
    fn(){
        return super === obj.__proto__
    }
}
1
2
3
4
5
6
7
let obj = {
    fn() {
        return super.a === this.__proto__.a
    }
}
obj.__proto__.a = 1;
console.log(obj.fn()) //true

解构赋值

扩展运算符的解构赋值，不能复制继承自原型对象的属性。

1
2
3
4
5
6
7
8
const o = Object.create({ x: 1, y: 2 });
o.z = 3;

let { x, ...newObj } = o;
let { y, z } = newObj;
x // 1
y // undefined
z // 3

ES6 规定，变量声明语句之中，如果使用解构赋值，扩展运算符后面必须是一个变量名，而不能是一个解构赋值表达式

1
2
let { x, ...{ y, z } } = o;
// SyntaxError: ... must be followed by an identifier in declaration contexts

对象的扩展运算符

如果扩展运算符后面不是对象，则会自动将其转为对象。

扩展运算符后面是整数1，会自动转为数值的包装对象Number{1}。由于该对象没有自身属性，所以返回一个空对象。

1
2
// 等同于 {...Object(1)}
{...1} // {}

对象的扩展运算符等同于使用Object.assign()方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 写法一
const clone1 = {
  __proto__: Object.getPrototypeOf(obj),
  ...obj
};

// 写法二
const clone2 = Object.assign(
  Object.create(Object.getPrototypeOf(obj)),
  obj
);

// 写法三
const clone3 = Object.create(
  Object.getPrototypeOf(obj),
  Object.getOwnPropertyDescriptors(obj)
)

取值函数get在扩展a对象时会自动执行，导致报错。

1
2
3
4
5
6
7
let a = {
  get x() {
    throw new Error('not throw yet');
  }
}

let aWithXGetter = { ...a }; // 报错

链判断运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a?.b
// 等同于
a == null ? undefined : a.b

a?.[x]
// 等同于
a == null ? undefined : a[x]

a?.b()
// 等同于
a == null ? undefined : a.b()

a?.()
// 等同于
a == null ? undefined : a()
1
2
const firstName = message?.body?.user?.firstName || 'default';
const fooValue = myForm.querySelector('input[name=foo]')?.value

Null 判断运算符

ES2020 引入了一个新的 Null 判断运算符??。它的行为类似||，但是只有运算符左侧的值为null或undefined时，才会返回右侧的值。

1
const animationDuration = response.settings?.animationDuration ?? 300;

编码

JavaScript

计算机自己能理解的“语言”是二进制数，最小的信息标识是二进制位，8个二进制位表示一个字节；而我们人类所能理解的语言文字则是一套由英文字母、汉语汉字、标点符号字符、阿拉伯数字等等很多的字符构成的字符集

如果要让计算机来按照人类的意愿进行工作，则必须把人类所使用的这些字符集转换为计算机所能理解的二级制码，这个过程就是编码，他的逆过程称为解码。

最开始计算机在美国发明使用，需要编码的字符集,并不是很大，无外乎英文字母、数字和一些简单的标点符号，因此采用了一种单字节编码系统。在这套编码规则中，人们将所需字符集中的字符一一映射到128个二进制数上，这128个二进制数是最高位为0，利用剩余低7位组成00000000~01111111（0X00~0X7F）。0X00到0X1F共32个二进制数来对控制字符或通信专用字符（如LF换行、DEL删除、BS退格）编码，0X20到0X7F共96个二进制数来对阿拉伯数字、英文字母大小写和下划线、括号等符号进行编码。

将这套字符集映射到0X00~0X7F二进制码的过程就称为基础ASCII编码

通过这个编码过程，计算机就将人类的语言转化为自己的语言存储了起来，反之从磁盘中读取二级制数并转化为字母数字等字符以供显示的过程就是解码。

随着计算机被迅速推广使用，欧洲的非英语国家的人们发现这套由美国人设计的字符集不够用了，比如一些带重音的字符、希腊字母等都不在这个字符集中

于是扩充了ASCII编码规则，将原本为0的最高位改为1，因此扩展出了10000000~11111111（0X80~0XFF）这128个二进制数。

这其中，最优秀的扩展方案是ISO 8859-1，通常称之为Latin-1。Latin-1利用128~255这128个二进制数，包括了足够的附加字符集来涵盖基本的西欧语言，同时在0~127的范围内兼容ASCII编码规则。

随着使用计算机的国家越来越多，自然而然需要编码的字符集就越来越庞大，早先的ASCII编码字符集由于受到单字节的限制，其容量就远远不够了，比方说面对成千上万的汉字，其压力可想而知。

因此中国国家标准总局发布了一套《信息交换用汉字编码字符集》的国家标准，其标准号就是GB 2312—1980。

这个字符集共收入汉字6763个和非汉字图形字符682个，采用两个字节对字符集进行编码，并向下兼容ASCII编码方式。简言之，整个字符集分成94个区，每区有94个位，分别用一个字节对应表示相应的区和位。每个区位对应一个字符，因此可用所在的区和位来对汉字进行两字节编码。

再后来生僻字、繁体字及日韩汉字也被纳入字符集，就又有了后来的GBK字符集及相应的编码规范，GBK编码规范也是向下兼容GBK2312的。

在中国发展的同时，计算机在全世界各个国家不断普及，不同的国家地区都会开发出自己的一套编码系统，因此编码系统五花八门，这时候问题就开始凸显了，特别是在互联网通信的大环境下，装有不同编码系统的计算机之间通信就会彼此不知道对方在“说”些什么，按照A编码系统的编码方式将所需字符转换成二进制码后，在B编码系统的计算机上解码是无法得到原始字符的，相反会出现一些出人意料的古怪字符，这就是所谓的

为了实现跨语言、跨平台的文本转换和处理需求，ISO国际标准化组织提出了Unicode的新标准，这套标准中包含了Unicode字符集和一套编码规范。Unicode字符集涵盖了世界上所有的文字和符号字符，Unicode编码方案为字符集中的每一个字符指定了统一且唯一的二进制编码，这就能彻底解决之前不同编码系统的冲突和乱码问题。这套编码方案简单来说是这样的：编码规范中含有17个组（称为平面），每一个组含有65536个码位（例如组0就是0X0000~0XFFFF），每一个码位就唯一对应一个字符，大部分的字符都位于字符集平面0的码位中，少量位于其他平面。

既然提到了Unicode编码，那么常常与之相伴的UTF-8，UTF-16编码方案又是什么？

其实到目前为止我们都一致混淆了两个概念，即字符代码和字符编码，字符代码是特定字符在某个字符集中的序号，而字符编码是在传输、存储过程当中用于表示字符的以字节为单位的二进制序列。ASCII编码系统中，字符代码和字符编码是一致的，比如字符A，在ASCII字符集中的序号，也就是所谓的字符代码是65，存储在磁盘中的二进制比特序列是01000001（0X41，十进制也是65），另外的，如在GB2312编码系统中字符代码和字符编码的值也是一致的，所以无形之中我们就忽略了二者的差异性。而在Unicode标准中，我们目前使用的是UCS-4，即字符集中每一个字符的字符代码都是用4个字节来表示，其中字符代码0~127兼容ASCII字符集，一般的通用汉字的字符代码也都集中在65535之前，使用大于65535的字符代码，即需要超过两个字节来表示的字符代码是比较少的。因此，如果仍然依旧采用字符代码和字符编码相一致的编码方式，那么英语字母、数字原本仅需一个字节编码，目前就需要4个字节进行编码，汉字原本仅需两个字节进行编码，目前也需要4个字节进行编码，这对于存储或传输资源而言是很不划算的。

因此就需要在字符代码和字符编码间进行再编码，这样就引出了UTF-8、UTF-16等编码方式

基于上述需求，UTF-8就是针对位于不同范围的字符代码转化成不同长度的字符编码，同时这种编码方式是以字节为单位，并且完全兼容ASCII编码，即0X00-0X7F的字符代码和字符编码完全一致，也是用一个字节来编码ASCII字符集，而常用汉字在Unicode中的字符代码是4E00-9FA5，在文末的对应关系中我们看到是用三个字节来进行汉字字符的编码。UTF-16同理，就是以16位二进制数为基本单位对Unicode字符集中的字符代码进行再编码，原理和UTF-8一致。

文末的对应关系中我们看到是用三个字节来进行汉字字符的编码。UTF-16同理，就是以16位二进制数为基本单位对Unicode字符集中的字符代码进行再编码，原理和UTF-8一致。

字符串

JavaScript

字符的 Unicode 表示法

ES6 加强了对 Unicode 的支持，允许采用\uxxxx形式表示一个字符，其中xxxx表示字符的 Unicode 码点。 "\u0061"==="a"

这种表示法只限于码点在\u0000~\uFFFF之间的字符，对双字节的文字 𠮷 不能解析"\u20BB7",因为对于超出范围的文字会解析成\u20BB 和 7，ES6 对这一点做出了改进,通过使用大括号的方式 "\u{20BB7}"==="𠮷"

  • 中文转Unicode的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
function toUnicode(str) {
    if (typeof str !== 'string') {
        throw new Error()
    }
    if (str === '') {
        return;
    }
    var res = '';
    for (var i = 0; i < str.length; i++) {
        res += '\\u' + str[i].charCodeAt().toString(16)
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
function toUnicode(str) {
    if (typeof str !== 'string') {
        throw new Error()
    }
    if (str === '') {
        return;
    }
    let res = '';
    for (let s of str) {
        res += `\\u{${s.codePointAt().toString(16)}}`
    }
    return res;
}
  • Unicode转中文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function toCh(str) {
    if (typeof str !== 'string') {
        throw new Error()
    }
    if (str === '') {
        return;
    }
    var reg = /\\u{([a-f0-9A-F]+)}/g;
    var res = '';

    while (reg.exec(str)) {
        res += String.fromCodePoint(parseInt(RegExp.$1, 16));
    }
    return res;
}

fromCodePoint codePointAt

ES5 提供String.fromCharCode()方法，用于从 Unicode 码点返回对应字符，但是这个方法不能识别码点大于0xFFFF的字符。

1
2
String.fromCharCode(0x20BB7)
// "ஷ"

上面代码中，如果String.fromCodePoint方法有多个参数，则它们会被合并成一个字符串返回。

1
2
3
4
String.fromCodePoint(0x20BB7)
// "𠮷"
String.fromCodePoint(0x78, 0x1f680, 0x79) === 'x\uD83D\uDE80y'
// true

注意，fromCodePoint方法定义在String对象上，而codePointAt方法定义在字符串的实例对象上

JavaScript 内部，字符以 UTF-16 的格式储存，每个字符固定为2个字节。对于那些需要4个字节储存的字符（Unicode 码点大于0xFFFF的字符），JavaScript 会认为它们是两个字符。

1
2
3
4
5
6
7
var s = "𠮷";

s.length // 2
s.charAt(0) // ''
s.charAt(1) // ''
s.charCodeAt(0) // 55362
s.charCodeAt(1) // 57271

codePointAt()方法的参数，仍然是不正确的。比如，上面代码中，字符a在字符串s的正确位置序号应该是 1，但是必须向codePointAt()方法传入 2。解决这个问题的一个办法是使用for…of循环，因为它会正确识别 32 位的 UTF-16 字符。

1
2
3
4
5
6
let s = '𠮷a';
for (let ch of s) {
  console.log(ch.codePointAt(0).toString(16));
}
// 20bb7
// 61

另一种方法也可以，使用扩展运算符（…）进行展开运算。

1
2
3
4
5
6
let arr = [...'𠮷a']; // arr.length === 2
arr.forEach(
  ch => console.log(ch.codePointAt(0).toString(16))
);
// 20bb7
// 61

codePointAt()方法是测试一个字符由两个字节还是由四个字节组成的最简单方法。

1
2
3
4
5
6
function is32Bit(c) {
  return c.codePointAt(0) > 0xFFFF;
}

is32Bit("𠮷") // true
is32Bit("a") // false

字符串的遍历器接口

ES6 为字符串添加了遍历器接口，使得字符串可以被for…of循环遍历。

除了遍历字符串，这个遍历器最大的优点是可以识别大于0xFFFF的码点，传统的for循环无法识别这样的码点。

1
2
3
4
5
6
7
8
9
10
11
let text = String.fromCodePoint(0x20BB7);

for (let i = 0; i < text.length; i++) {
  console.log(text[i]);
}
// " "
// " "
for (let i of text) {
  console.log(i);
}
// "𠮷"

需要转移的字符

码点 字符
U+005C 反斜杠（reverse solidus)
U+000D 回车（carriage return）
U+2029 段分隔符（paragraph separator）
U+000A 换行符（line feed）

JSON.stringify()

具体来说，UTF-8 标准规定，0xD800到0xDFFF之间的码点，不能单独使用，必须配对使用。比如，\uD834\uDF06是两个码点，但是必须放在一起配对使用，代表字符𝌆。这是为了表示码点大于0xFFFF的字符的一种变通方法。单独使用\uD834和\uDFO6这两个码点是不合法的，或者颠倒顺序也不行，因为\uDF06\uD834并没有对应的字符。

JSON.stringify()的问题在于，它可能返回0xD800到0xDFFF之间的单个码点。

为了确保返回的是合法的 UTF-8 字符，ES2019 改变了JSON.stringify()的行为。如果遇到0xD800到0xDFFF之间的单个码点，或者不存在的配对形式，它会返回转义字符串，留给应用自己决定下一步的处理。

1
2
JSON.stringify('\u{D834}') // ""\\uD834""
JSON.stringify('\uDF06\uD834') // ""\\udf06\\ud834""

模板字符串

  • 如果在模板字符串中需要使用反引号，则前面要用反斜杠转义。

  • 如果使用模板字符串表示多行字符串，所有的空格和缩进都会被保留在输出之中。

  • 模板字符串中嵌入变量，需要将变量名写在${}之中。

  • 通过模板字符串编译模板

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
let template = `
    <ul>
        <% for(let i=0; i < data.supplies.length; i++) { %>
            <li><%= data.supplies[i] %></li>
        <% } %>
    </ul>
`;

function complie(template) {
    let evalExpr = /<%=(.+?)%>/g;
    let expr = /<%([\s\S]+?)%>/g;

    template = template
        .replace(evalExpr, '`); \n  echo( $1 ); \n  echo(`')
        .replace(expr, '`); \n $1 \n  echo(`');
    template = 'echo(`' + template + '`);';
    
    const excu = `
        'use strict;'
        let html = '';
        function echo(exp) {
            html += exp
        }
        ${template}
        return html;
    `
    return function (data) {
        return Function('data',excu)(data);
    }
}
console.log(complie(template)({
    supplies: [1, 2, 3]
}))

标签模板

它可以紧跟在一个函数名后面，该函数将被调用来处理这个模板字符串。这被称为“标签模板”功能（tagged template）。

1
2
3
4
5
6
let a = 5;
let b = 10;

tag`Hello ${ a + b } world ${ a * b }`;
// 等同于
tag(['Hello ', ' world ', ''], 15, 50);
1
2
3
4
5
6
7
8
9
10
function passthru(literals, ...values) {
  let output = "";
  let index;
  for (index = 0; index < values.length; index++) {
    output += literals[index] + values[index];
  }

  output += literals[index]
  return output;
}
  • 过滤 HTML 字符串，防止用户输入恶意内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let message =
  SaferHTML`<p>${sender} has sent you a message.</p>`;

function SaferHTML(templateData) {
  let s = templateData[0];
  for (let i = 1; i < arguments.length; i++) {
    let arg = String(arguments[i]);

    // Escape special characters in the substitution.
    s += arg.replace(/&/g, "&amp;")
            .replace(/</g, "&lt;")
            .replace(/>/g, "&gt;");

    // Don't escape special characters in the template.
    s += templateData[i];
  }
  return s;
}
  • 多语言转换（国际化处理）。
1
2
i18n`Welcome to ${siteName}, you are visitor number ${visitorNumber}!`
// "欢迎访问xxx，您是第xxxx位访问者！"

raw属性

tag函数的第一个参数strings，有一个raw属性，也指向一个数组。该数组的成员与strings数组完全一致。比如，strings数组是[“First line\nSecond line”]，那么strings.raw数组就是[“First line\nSecond line”]。两者唯一的区别，就是字符串里面的斜杠都被转义了。比如，strings.raw 数组会将\n视为\和n两个字符，而不是换行符。这是为了方便取得转义之前的原始模板而设计的。

1
2
3
4
5
6
7
tag`First line\nSecond line`

function tag(strings) {
  console.log(strings.raw[0]);
  // strings.raw[0] 为 "First line\\nSecond line"
  // 打印输出 "First line\nSecond line"
}

String.raw()

ES6 还为原生的 String 对象，提供了一个raw()方法。该方法返回一个斜杠都被转义（即斜杠前面再加一个斜杠）的字符串，往往用于模板字符串的处理方法。

1
2
3
4
String.raw`Hi\\n`
// 返回 "Hi\\\\n"

String.raw`Hi\\n` === "Hi\\\\n" // true
1
2
3
// `foo${1 + 2}bar`
// 等同于
String.raw({ raw: ['foo', 'bar'] }, 1 + 2) // "foo3bar"

实例方法：includes(), startsWith(), endsWith()

  • includes()：返回布尔值，表示是否找到了参数字符串。

  • startsWith()：返回布尔值，表示参数字符串是否在原字符串的头部。

  • endsWith()：返回布尔值，表示参数字符串是否在原字符串的尾部。

三个方法都支持第二个参数，表示开始搜索的位置。

endsWith的行为与其他两个方法有所不同。它针对前n个字符，而其他两个方法针对从第n个位置直到字符串结束。

1
2
3
4
5
let s = 'Hello world!';

s.startsWith('world', 6) // true
s.endsWith('Hello', 5) // true
s.includes('Hello', 6) // false

repeat()

参数如果是小数，会被取整。如果repeat的参数是负数或者Infinity，会报错。参数NaN等同于 0。repeat的参数是字符串，则会先转换成数字。

1
'x'.repeat(3) // "xxx"

实例方法：padStart()，padEnd()

padStart()和padEnd()一共接受两个参数，第一个参数是字符串补全生效的最大长度，第二个参数是用来补全的字符串。

如果原字符串的长度，等于或大于最大长度，则字符串补全不生效，返回原字符串。

如果用来补全的字符串与原字符串，两者的长度之和超过了最大长度，则会截去超出位数的补全字符串。

如果省略第二个参数，默认使用空格补全长度。

1
2
3
4
5
6
7
8
'xxx'.padStart(2, 'ab') // 'xxx'

'abc'.padStart(10, '0123456789')
// '0123456abc'

'x'.padStart(4) // '   x'
'x'.padEnd(4) // 'x   '

常见用途，补全字符串，提示时间格式

1
2
3
'1'.padStart(10, '0') // "0000000001"

'12'.padStart(10, 'YYYY-MM-DD') // "YYYY-MM-12"

trimStart()，trimEnd()

ES2019 对字符串实例新增了trimStart()和trimEnd()这两个方法。它们的行为与trim()一致，trimStart()消除字符串头部的空格，trimEnd()消除尾部的空格。它们返回的都是新字符串，不会修改原始字符串。

解构赋值

JavaScript

数组的解构赋值

  • 如果解构不成功，变量的值就等于undefined

  • 对于 Set 结构，也可以使用数组的解构赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let [foo, [[bar], baz]] = [1, [[2], 3]];
foo // 1
bar // 2
baz // 3

let [ , , third] = ["foo", "bar", "baz"];
third // "baz"

let [x, , y] = [1, 2, 3];
x // 1
y // 3

let [head, ...tail] = [1, 2, 3, 4];
head // 1
tail // [2, 3, 4]


let [x, y, ...z] = ['a'];
x // "a"
y // undefined
z // []

let [x, y, z] = new Set(['a', 'b', 'c']);
  • 如果等号的右边是可遍历的结构（Iterator），会报错
1
2
3
4
5
6
7
// 报错
let [foo] = 1;
let [foo] = false;
let [foo] = NaN;
let [foo] = undefined;
let [foo] = null;
let [foo] = {};
1
2
3
4
5
6
7
8
9
10
11
function* fibs() {
  let a = 0;
  let b = 1;
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

let [first, second, third, fourth, fifth, sixth] = fibs();
sixth // 5
  • 默认值， 只有结构元素严格等于undefined才会使用默认值
1
2
3
4
5
let [x = 1] = [undefined];
x // 1

let [x = 1] = [null];
x // null

如果默认值是表达式，只有赋值时才会执行

1
2
3
4
5
6
7
8
9
10
11
12
13
function f() {
  console.log('aaa');
}
//f不会执行
let [x = f()] = [1];

//等价于
let x;
if ([1][0] === undefined) {
  x = f();
} else {
  x = [1][0];
}

可以使用其他变量但这个变量必须已经声明

1
let [x = 1, y = x] = [];     // x=1; y=1

对象的解构赋值

对象的解构与数组有一个重要的不同。数组的元素是按次序排列的，变量的取值由它的位置决定；而对象的属性没有次序，变量必须与属性同名，才能取到正确的值。

对象的解构赋值是下面形式的简写,真正被赋值的是后者，而不是前者。

1
2
3
let { foo: baz } = { foo: 'aaa', bar: 'bbb' };
baz // "aaa"
foo // error: foo is not defined
  • 注意模式和变量的区别， 这时p是模式，不是变量，因此不会被赋值。如果p也要作为变量赋值，可以写成下面这样。
1
2
3
4
5
6
7
8
9
10
11
let obj = {
  p: [
    'Hello',
    { y: 'World' }
  ]
};

let { p, p: [x, { y }] } = obj;
x // "Hello"
y // "World"
p // ["Hello", {y: "World"}]
  • 嵌套赋值
1
2
3
4
5
6
7
8
9
10
11
let obj = {};
let arr = [];

({ foo: obj.prop, bar: arr[0] } = { foo: 123, bar: true });

obj // {prop:123}
arr // [true]


// 报错
let {foo: {bar}} = {baz: 'baz'};
  • 对象的解构赋值可以取到继承的属性。
1
2
3
4
5
6
const obj1 = {};
const obj2 = { foo: 'bar' };
Object.setPrototypeOf(obj1, obj2);

const { foo } = obj1;
foo // "bar"
  • 如果要将一个已经声明的变量用于解构赋值，必须非常小心。
1
2
3
4
5
6
7
8
// 错误的写法
let x;
{x} = {x: 1};
// SyntaxError: syntax error

// 正确的写法
let x;
({x} = {x: 1});
  • 由于数组本质是特殊的对象，因此可以对数组进行对象属性的解构。
1
2
3
4
let arr = [1, 2, 3];
let {0 : first, [arr.length - 1] : last} = arr;
first // 1
last // 3

字符串结构赋值

  • 字符串被转换成了一个类似数组的对象。

  • 还可以对这个属性解构赋值。

1
2
3
const [a, b, c, d, e] = 'hello';

let {length : len} = 'hello';

数值和布尔值的解构赋值

  • 解构赋值的规则是，只要等号右边的值不是对象或数组，就先将其转为对象。
1
2
3
4
5
let {toString: s} = 123;
s === Number.prototype.toString // true

let {toString: s} = true;
s === Boolean.prototype.toString // true
  • 由于undefined和null无法转为对象，所以对它们进行解构赋值，都会报错。
1
2
let { prop: x } = undefined; // TypeError
let { prop: y } = null; // TypeError

函数参数的解构赋值

注意默认值的设置方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function move({x = 0, y = 0} = {}) {
  return [x, y];
}

move({x: 3, y: 8}); // [3, 8]
move({x: 3}); // [3, 0]
move({}); // [0, 0]
move(); // [0, 0]

function move({x, y} = { x: 0, y: 0 }) {
  return [x, y];
}

move({x: 3, y: 8}); // [3, 8]
move({x: 3}); // [3, undefined]
move({}); // [undefined, undefined]
move(); // [0, 0]

圆括号问题

变量声明语句，模式不能使用圆括号。

1
let {x: (c)} = {};//错误

函数参数不能使用圆括号

1
2
// 报错
function f([(z)]) { return z; }

赋值语句的模式报错

1
2
3
4
5
// 全部报错
({ p: a }) = { p: 42 };
([a]) = [5];
// 报错
[({ p: a }), { x: c }] = [{}, {}];

可以使用圆括号的情况只有一种：赋值语句的非模式部分，可以使用圆括号。

1
2
3
[(b)] = [3]; // 正确
({ p: (d) } = {}); // 正确
[(parseInt.prop)] = [3]; // 正确

常见使用方式

  • 交换变量的值
1
2
3
4
let x = 1;
let y = 2;

[x, y] = [y, x];

  • 从函数返回多个值

  • 函数参数的定义

  • 提取 JSON 数据

  • 函数参数的默认值

  • 遍历 Map 结构

1
2
3
4
5
6
7
8
9
const map = new Map();
map.set('first', 'hello');
map.set('second', 'world');

for (let [key, value] of map) {
  console.log(key + " is " + value);
}
// first is hello
// second is world
  • 获取引入模块的方法

let const

JavaScript

let

  • 只在let命令所在的代码块内有效
1
2
3
4
5
6
7
{
  let a = 10;
  var b = 1;
}

a // ReferenceError: a is not defined.
b // 1
  • for循环还有一个特别之处，就是设置循环变量的那部分是一个父作用域，而循环体内部是一个单独的子作用域。
1
2
3
4
5
6
for (let i = 0; i < 10; i++) {
  // ...
}

console.log(i);
// ReferenceError: i is not defined

  • 不存在变量提升

    声明的变量一定要在声明后使用，否则报错。

1
2
3
4
5
6
7
// var 的情况
console.log(foo); // 输出undefined
var foo = 2;

// let 的情况
console.log(bar); // 报错ReferenceError
let bar = 2;

  • 暂时性死区

    只要块级作用域内存在let命令，它所声明的变量就“绑定”（binding）这个区域，不再受外部的影响。

    如果要使用let声明的变量无论读取还是赋值，都要在声明之后

    在代码块内，使用let命令声明变量之前，该变量都是不可用的。这在语法上，称为“暂时性死区”（temporal dead zone，简称 TDZ）。

1
2
3
4
5
6
var tmp = 123;

if (true) {
  tmp = 'abc'; // ReferenceError
  let tmp;
}

对typeof的使用有影响，生命前使用会报错，没有声明的反而不会报错

1
2
3
4
5
typeof x; // ReferenceError
let x;

typeof undeclared_variable // "undefined"

暂时性死区的本质就是，只要一进入当前作用域，所要使用的变量就已经存在了，但是不可获取，只有等到声明变量的那一行代码出现，才可以获取和使用该变量。

  • 不允许重复声明

    不能在函数内部重新声明参数。

1
2
3
4
5
6
7
8
9
10
11
function func(arg) {
    let arg;
}
func() // 报错

function func(arg) {
    {
        let arg;
    }
}
func() // 不报错

块级作用域

没有块级作用域，这带来很多不合理的场景。

  • 内层变量可能会覆盖外层变量。
1
2
3
4
5
6
7
8
9
10
var tmp = new Date();

function f() {
  console.log(tmp);
  if (false) {
    var tmp = 'hello world';
  }
}

f(); // undefined
  • 用来计数的循环变量泄露为全局变量。
1
2
3
4
5
6
7
var s = 'hello';

for (var i = 0; i < s.length; i++) {
  console.log(s[i]);
}

console.log(i); // 5

ES6 的块级作用域

  • let实际上为 JavaScript 新增了块级作用域。
1
2
3
4
5
6
7
function f1() {
  let n = 5;
  if (true) {
    let n = 10;
  }
  console.log(n); // 5
}
  • 块级作用域的出现，实际上使得获得广泛应用的匿名立即执行函数表达式（匿名 IIFE）不再必要了。
1
2
3
4
5
6
7
8
9
10
11
// IIFE 写法
(function () {
  var tmp = ...;
  ...
}());

// 块级作用域写法
{
  let tmp = ...;
  ...
}

  • 在块级作用域中声明函数

    ES5 的规定都是非法的。ES6 引入了块级作用域，明确允许在块级作用域之中声明函数。ES6 规定，块级作用域之中，函数声明语句的行为类似于let，在块级作用域之外不可引用。

1
2
3
4
5
6
7
8
9
10
11
12
// 浏览器的 ES6 环境
function f() { console.log('I am outside!'); }

(function () {
  if (false) {
    // 重复声明一次函数f
    function f() { console.log('I am inside!'); }
  }

  f();
}());
// Uncaught TypeError: f is not a function

理论上上面的代码在ES6浏览器会报错，但在真实浏览器环境中还是会执行方法，如果改变了块级作用域内声明的函数的处理规则，显然会对老代码产生很大影响。为了减轻因此产生的不兼容问题，ES6 在附录 B里面规定，浏览器的实现可以不遵守上面的规定，有自己的行为方式。

1.允许在块级作用域内声明函数。

2.函数声明类似于var，即会提升到全局作用域或函数作用域的头部。

3.同时，函数声明还会提升到所在的块级作用域的头部。

应该避免在块级作用域内声明函数。如果确实需要，也应该写成函数表达式，而不是函数声明语句。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 块级作用域内部的函数声明语句，建议不要使用
{
  let a = 'secret';
  function f() {
    return a;
  }
}

// 块级作用域内部，优先使用函数表达式
{
  let a = 'secret';
  let f = function () {
    return a;
  };

ES6 的块级作用域必须有大括号，如果没有大括号，JavaScript 引擎就认为不存在块级作用域。

let只能出现在当前作用域的顶层

1
2
3
4
5
6
7
// 第一种写法，报错
if (true) let x = 1;

// 第二种写法，不报错
if (true) {
  let x = 1;
}

严格模式下，函数只能声明在当前作用域的顶层。

1
2
3
4
5
6
7
8
9
10
// 不报错
'use strict';
if (true) {
  function f() {}
}

// 报错
'use strict';
if (true)
  function f() {}

const

const声明一个只读的常量。一旦声明，常量的值就不能改变。

const一旦声明变量，就必须立即初始化，不能留到以后赋值。

其他特性与let相同

const实际上保证的，并不是变量的值不得改动，而是变量指向的那个内存地址所保存的数据不得改动。对于简单类型的数据（数值、字符串、布尔值），值就保存在变量指向的那个内存地址，因此等同于常量。但对于复合类型的数据（主要是对象和数组），变量指向的内存地址，保存的只是一个指向实际数据的指针，const只能保证这个指针是固定的（即总是指向另一个固定的地址），至于它指向的数据结构是不是可变的，就完全不能控制了。因此，将一个对象声明为常量必须非常小心。

1
2
3
4
const a = [];
a.push('Hello'); // 可执行
a.length = 0;    // 可执行
a = ['Dave'];    // 报错

如果不想让对象的属性可操作，应该使用Object.freeze方法。

1
2
3
4
5
6
7
8
var constantize = (obj) => {
  Object.freeze(obj);
  Object.keys(obj).forEach( (key, i) => {
    if ( typeof obj[key] === 'object' ) {
      constantize( obj[key] );
    }
  });
};

ES6 声明变量的六种方法

var,function,let,const,import,class

顶层对象的属性

是没法在编译时就报出变量未声明的错误，只有运行时才能知道（因为全局变量可能是顶层对象的属性创造的，而属性的创造是动态的）

为了保持兼容性，var命令和function命令声明的全局变量，依旧是顶层对象的属性；另一方面规定，let命令、const命令、class命令声明的全局变量，不属于顶层对象的属性。也就是说，从 ES6 开始，全局变量将逐步与顶层对象的属性脱钩。

globalThis 对象

JavaScript 语言存在一个顶层对象，它提供全局环境（即全局作用域），所有代码都是在这个环境中运行。但是，顶层对象在各种实现里面是不统一的。

  • 浏览器里面，顶层对象是window，但 Node 和 Web Worker 没有window。

  • 浏览器和 Web Worker 里面，self也指向顶层对象，但是 Node 没有self。

  • Node 里面，顶层对象是global，但其他环境都不支持。

同一段代码为了能够在各种环境，都能取到顶层对象，现在一般是使用this变量，但是有局限性。

  • 全局环境中，this会返回顶层对象。但是，Node.js 模块中this返回的是当前模块，ES6 模块中this返回的是undefined。

  • 函数里面的this，如果函数不是作为对象的方法运行，而是单纯作为函数运行，this会指向顶层对象。但是，严格模式下，这时this会返回undefined。

  • 不管是严格模式，还是普通模式，new Function(‘return this’)()，总是会返回全局对象。但是，如果浏览器用了 CSP（Content Security Policy，内容安全策略），那么eval、new Function这些方法都可能无法使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 方法一
(typeof window !== 'undefined'
   ? window
   : (typeof process === 'object' &&
      typeof require === 'function' &&
      typeof global === 'object')
     ? global
     : this);

// 方法二
var getGlobal = function () {
  if (typeof self !== 'undefined') { return self; }
  if (typeof window !== 'undefined') { return window; }
  if (typeof global !== 'undefined') { return global; }
  throw new Error('unable to locate global object');
};

O11.旋转数字最小数字

算法 / 关联题目
LeetCode

二分查找

通过上图直观的分析出旋转数字的一些特点

  • 最右边的值只能小于等于最左边的值

  • 如果一个值比最右边的值小，那么最小值一定在这个值左边或是这个值本身

  • 如果最左边的值比其中一个值大，那么最小值一定在这个值右边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 var minArray = function (numbers) {
  var left = 0,
      right = numbers.length - 1,
      mid = Math.floor(right / 2);
  while (left < right) {
      if (numbers[mid] < numbers[right]) {
          right = mid;
      } else if (numbers[mid] === numbers[right]) {
          right--;
      } else if (numbers[mid] > numbers[right]) {
          left = mid + 1;
      }
      mid = Math.floor((left + right) / 2)
  }
  return numbers[left];
};

  • 什么左边的值比其中一个值大的时候，这个值不能是最小值

    因为我们先处理了右半区的比较，会使得最右边值先到达最小值

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

46.全排列

算法 / 关联题目
LeetCode

回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function permute(nums) {
  const res = [];
  const  set = new Set();
  function dfs(set){
      if(set.size===nums.length){
          res.push([...set]);
      }
      for(let k of nums){
          if(set.has(k)){
              continue;
          }
          set.add(k);
          dfs(set);
          set.delete(k)
      }
  }
  dfs(set);
  return res;
};

位置交换

回溯法在进入下一次递归时，并没有标注循环位置，所以nums中的元素每一个都要通过Set集合判断一次

如果不使用Set数据结构，时间复杂度更高

位置交换，是通过在一次循环把第一个元素更换为其他剩余元素，在第一个元素固定下来后，后面的元素进行全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
function permute(nums) {
    const res = [];
    function dfs(n) {
        if (n === nums.length - 1) {
            res.push([...nums]);
        }
        for (let i = n; i < nums.length; i++) {
            swap(nums, i, n)
            dfs(n + 1);
            swap(nums, i, n)
        }
    }
    dfs(0);
    return res;
};

位置交换稍微调整

发现在最后只有一个元素的时候，还是进行了递归

所以提前判断剩余数组是否满足递归条件，如果只剩下一个元素就结束递归

使用一下es6数组元素交换的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function permute(nums) {
  const res = [];
  function dfs(n) {
      for (let i = n; i < nums.length; i++) {
          [nums[i], nums[n]] = [nums[n], nums[i]];
          if (n + 1 > nums.length - 1) {
              res.push([...nums]);
              continue;
          }
          dfs(n + 1);
          [nums[i], nums[n]] = [nums[n], nums[i]];
      }
  }
  dfs(0);
  return res;
};

复杂度分析

  • 时间复杂度：

  • 空间复杂度：

图

算法 / 数据结构

图的相关术语

图是网络结构的抽象模型。是一组由边连接的节点（或顶点）

任何二元关系都可以用图来表示。

数学上表示为 , 表示一组顶点， 表示一组边，连接中的顶点

相关概念

  • 由一条边连接在一起的顶点称为相邻顶点。比如，A 和B 是相邻的，A 和D 是相邻的，A 和C 是相邻的，A 和E 不是相邻的。

  • 一个顶点的度是其相邻顶点的数量。比如，A 和其他三个顶点相连接，因此A 的度为3；E和其他两个顶点相连，因此E 的度为2。

  • 路径是顶点v1, v2, …, vk 的一个连续序列，其中vi 和vi+1 是相邻的。以上一示意图中的图为例，其中包含路径A B E I 和A C D G。

  • 简单路径要求不包含重复的顶点。举个例子，A D G 是一条简单路径。除去最后一个顶点（因为它和第一个顶点是同一个顶点），环也是一个简单路径，比如A D C A（最后一个顶点重新回到A）

  • 如果图中不存在环，则称该图是无环的。如果图中每两个顶点间都存在路径，则该图是连通的。

有向图 无向图

图可以是无向的（边没有方向）或是有向的（有向图）。第一张图是无向图，下面这张是有向图

如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。例如，C 和D 是强连通的，而A 和B 不是强连通的。

图还可以是未加权的（目前为止我们看到的图都是未加权的）或是加权的。如下图所示，加权图的边被赋予了权值。

应用

  • 搜索图中的一个特定顶点或搜索一条特定边

  • 寻找图中的一条路径（从一个顶点到另一个顶点

  • 寻找两个顶点之间的最短路径，以及环检测。

图的表示

邻接矩阵

每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接。

如果索引为i 的节点和索引为 j 的节点相邻，则 array[i][j] === 1，否则array[i][j] === 0，如下图所示。

由于不是强连通图（每两个节点间都存在路径），所以数组中有大量的0

给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，我们也不得不迭代一整行。

邻接矩阵表示法不够好的另一个理由是，图中顶点的数量可能会改变，修改二维数组不够灵活。

邻接表

邻接表由图中每个顶点的相邻顶点列表所组成。

存在好几种方式来表示这种数据结构。我们可以用列表（数组）、链表，甚至是散列表或是字典来表示相邻顶点列表。

对大多数问题来说都是更好的选择

但要找出顶点 v 和 w 是否相邻，使用邻接矩阵会比较快

关联矩阵

关联矩阵中，矩阵的行表示顶点，列表示边。如下图所示，

使用二维数组来表示两者之间的连通性，如果顶点 v 是边 e 的入射点，则 array[v][e] === 1

否则，array[v][e] === 0

关联矩阵通常用于边的数量比顶点多的情况，以节省空间和内存。

创建Graph 类

类的结构

  • 图是否有向，默认无无向图 ①

  • 使用一个数组来储存顶点的名字 ②

  • 使用一个字典来储存邻接表，字典将会使用顶点的名字作为键，邻接顶点列表作为值 ③

1
2
3
4
5
6
7
class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // ①
    this.vertices = []; // ②
    this.adjList = new Map(); // ③
  }
}

插入顶点方法

  • 如果顶点不存 ④ 在顶点列表中添加节点 ⑤

  • 在邻接表中为该顶点创建空数组 ⑥

1
2
3
4
5
6
addVertex(v) {
  if (!this.vertices.has(v)) { // ④
    this.vertices.push(v); // ⑤ 
    this.adjList.add(v, []); // ⑥
  }
}

建立链接方法

  • 如果建立链接的两个点不在顶点列表中，要先填入顶点列表

  • 将 w 加入到 v 的邻接表中，表示添加了一条自顶点 v 到顶点 w 的边

  • 无向图需要添加一条自 w 到 v 的边

1
2
3
4
5
6
7
8
9
10
11
12
addEdge(v, w) {
  if (!this.adjList.has(v)) {
    this.addVertex(v);
  }
  if (!this.adjList.has(w)) {
    this.addVertex(w);
  }
  this.adjList.get(v).push(w);
  if (!this.isDirected) {
    this.adjList.get(w).push(v);
  }
}

请注意我们只是往数组里新增元素，因为数组已经在行 ⑥ 被初始化了

取值

一个返回顶点列表，另一个返回邻接表

1
2
3
4
5
6
getVertices() {
  return this.vertices;
}
getAdjList() {
  return this.adjList;
}

测试

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
52
53
54
55
56
57
58
59
60
61
class Graph {
  constructor(isDirected = false) {
    this.isDirected = isDirected; // {1}
    this.vertices = []; // {2}
    this.adjList = new Map(); // {3}
  }
  addVertex(v) {
    if (!this.vertices.includes(v)) { // {5}
      this.vertices.push(v); // {6}
      this.adjList.set(v, []); // {7}
    }
  }
  addEdge(v, w) {
    if (!this.adjList.has(v)) {
      this.addVertex(v);
    }
    if (!this.adjList.has(w)) {
      this.addVertex(w);
    }
    this.adjList.get(v).push(w);
    if (!this.isDirected) {
      this.adjList.get(w).push(v);
    }
  }
  getVertices() {
    return this.vertices;
  }
  getAdjList() {
    return this.adjList;
  }
  toString() {
    let s = '';
    for (let i = 0; i < this.vertices.length; i++) { // {15}
      s += `${this.vertices[i]} -> `;
      const neighbors = this.adjList.get(this.vertices[i]); // {16}
      for (let j = 0; j < neighbors.length; j++) { // {17}
        s += `${neighbors[j]} `;
      }
      s += '\n'; // {18}
    }
    return s;
  }
}
const graph = new Graph();
const myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']; // {12}
for (let i = 0; i < myVertices.length; i++) { // {13}
  graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B'); // {14}

graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString());

图的遍历

有两种算法可以对图进行遍历：广度优先搜索（breadth-first search，BFS） 和 深度优先搜索（depth-first search，DFS）

图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环，等等。

图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。

完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点，将其标注为被发现的，并将其加进待访问顶点列表中。

为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。

广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点列表的数据结构，如下表所示。

算法 数据结构 描述
深度优先搜索 栈 将顶点存入栈，顶点是沿着路径被探索的，存在新的相邻顶点就去访问
广度优先搜索 队列 将顶点存入队列，最先入队列的顶点先被探索

广度优先遍历

队列结构是广度优先遍历的精髓

从起点节点开始相邻的节点会被添加到队列中

因为队列有先进先出的性质，所以相邻的节点在遍历队列的时候会先被拿到，从而是实现了广度优先遍历

下一个关键点是如何知道节点没有被重复访问，解决办法是给访问过的节点打一个标记，如果下次访问相同的节点就跳过

WHITE: 表示没有被访问过 GARY: 访问过但是没有遍历子节点 BALCK: 节点和子结点都被访问过

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
// startVertex 指定遍历的起点
function breadthFirstSearch(graph, startVertex, callback) {
  // 拿到节点列表
  const vertices = graph.getVertices()
  // 拿到邻接表结构
  const adjList = graph.getAdjList();
  //标记是否访问过 默认所有节点都是白色没有访问过
  const color = {}
  for (var i = 0; i < vertices.length; i++) {
    color[vertices[i]] = "WHITE"
  }
  // 创建一个队列
  const queue = [];
  queue.push(startVertex);

  while (queue.length) {
    const node = queue.shift();
    const nabor = adjList.get(node)
    color[node] = 'GARY';
    for (let v of nabor) {
      if(color[v] === 'WHITE'){
        color[v] = "GARY"
        queue.push(v);
      }
    }
    color[v] = "BLACK"
    console.log(node);
  }
}
breadthFirstSearch(graph,myVertices[0])
使用广度优先寻找最短路径

因为使用了广度优先，所以会先访问距离为1的节点，然后是距离为2的节点，路径长的那一条线路，因为同一个节点被访问过，所以不会被记录，从而记录的都是每个节点到起点的最短路径

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
// startVertex 指定遍历的起点
function breadthFirstSearch(graph, startVertex, callback) {
  // 拿到节点列表
  const vertices = graph.getVertices()
  // 拿到邻接表结构
  const adjList = graph.getAdjList();
  //标记是否访问过 默认所有节点都是白色没有访问过
  const color = {}
  // 距离
  const distance = {};
  // 回溯节点 标识上一个节点是什么
  const predecessors = {}
  for (let i = 0; i < vertices.length; i++) {
    color[vertices[i]] = "WHITE"
  }
  // 创建一个队列
  const queue = [];
  queue.push(startVertex);

  // 初始化默认距离，和回溯节点
  for(let i = 0; i < vertices.length; i++){
    distance[vertices[i]] = 0;
    predecessors[vertices[i]] = null
  }

  while (queue.length) {
    const node = queue.shift();
    const nabor = adjList.get(node)
    color[node] = 'GARY';
    for (let v of nabor) {
      if (color[v] === 'WHITE') {
        // 上级节点的最短路进
        distance[v] = distance[node] + 1;
        // 指定当前节点的上级节点
        predecessors[v] = node;
        color[v] = "GARY"
        queue.push(v);
      }
    }
  }
  console.log(
    distance,
    predecessors
  )
}
breadthFirstSearch(graph, myVertices[0])

通过生成的前溯表以及所有的节点我们可以生成每个节点到头节点的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 遍历每一个节点
for (let v of myVertices) {
  const path = [];
  // 如果当前节点不是头节点，就存入上一个节点
  for (let w = v; w !== null; w = shortestPathA.predecessors[w]) {
    path.push(w);
  }
  let s = path.pop();
  //反向拼接每一个节点
  while (path.length) {
    s += '-' + path.pop()
  }
  console.log(s);
}

深度优先遍历

因为深度优先需要把一条路径遍历到底，所以拿到的节点需要继续遍子结点

所以深度优先的精髓就是栈的结构，拿到的子结点加入栈中，由于栈先进先出可以继续访问下层的子结点

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
const fn = function (graph) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  for (let v of vertices) {
    color[v] = "WHITE";
  }
  // 栈结构
  const stack = [];
  stack.unshift(vertices[0]);
  // 如果栈不为空就继续遍历
  while (stack.length) {
    const v = stack.shift();
    // 如果没有访问过就访问子结点
    if (color[v] === "WHITE") {
      color[v] = 'GARY';
      // 获取到子结点 放入栈中
      const nabor = adjList.get(v);
      for (let vn of nabor.reverse()) {
        stack.unshift(vn);
      }
    }
  }
}
fn(graph)

这种写法可以实现遍历，但是不方便统计某个节点的子结点是否全部遍历，也就是置成BLACK

另一个关键点，函数递归调用也可以调用栈，保存每个函数的调用帧, 所以深度优先也常用递归来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const fn = function (graph) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  for (let v of vertices) {
    color[v] = "WHITE";
  }
  depthFirstSearch(vertices[0], adjList, color);
}
const depthFirstSearch = function (v, adjList, color) {
  const nabor = adjList.get(v);
  if (color[v] === 'WHITE') {
  console.log(v);

    color[v] = 'GARY'
    for (let vn of nabor) {
      depthFirstSearch(vn, adjList, color);
    }
    // 子结点遍历完成之后标记为黑色
    color[v] === 'BLACK'
  }
}
fn(graph)
加入节点信息

在遍历图的时候加入更多的节点信息

1.每个节点的发现时间，到达某个节点经历的步数
2.每个节点的访问时间，某个节点所有子结点都被访问过的步数
3.节点的前溯节点表

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
const depthFirstSearch = function (v, adjList, color, find, visit, back, time) {
  const nabor = adjList.get(v);
  if (color[v] === 'WHITE') {
    find[v] = ++(time.t);
    color[v] = 'GARY'
    for (let vn of nabor) {
      back[vn] = v;
      depthFirstSearch(vn, adjList, color, find, visit, back, time);
    }
    color[v] === 'BLACK'
    visit[v] = ++(time.t);
  }
}
const fn = function (graph,) {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = {};
  const find = {};// 发现时间
  const visit = {};// 访问时间
  const back = {};// 回溯时间
  const time = { t: 0 }//用于计时
  for (let v of vertices) {
    color[v] = "WHITE";
    //初始化
    find[v] = 0;
    visit[v] = 0;
    back[v] = null;
  }
  depthFirstSearch(vertices[0], adjList, color, find, visit, back, time);
  return {
    find, visit, back, time
  }
}
fn(graph)
通过深度优先搜索拓扑排序

有些任务需要按顺序执行，而且不同的任务会公用一些子任务，编排这些有序任务被成为拓扑排序

这些任务形成了有向无环图，通过上面一节添加的节点信息，生成这些任务的执行顺序

首先生成图

1
2
3
4
5
6
7
8
9
10
11
graph = new Graph(true); // 有向图
myVertices = ['A', 'B', 'C', 'D', 'E', 'F'];
for (i = 0; i < myVertices.length; i++) {
    graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('F', 'E');

添加节点信息

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
const depthFirstSearch = function (v, adjList, color, find, visit, back, time) {
      const nabor = adjList.get(v);
      if (color[v] === 'WHITE') {
        find[v] = ++(time.t);
        color[v] = 'GARY'
        for (let vn of nabor) {
          back[vn] = v;
          depthFirstSearch(vn, adjList, color, find, visit, back, time);
        }
        color[v] === 'BLACK'
        visit[v] = ++(time.t);
      }
    }
    const fn = function (graph,) {
      const vertices = graph.getVertices();
      const adjList = graph.getAdjList();
      const color = {};
      const find = {};// 发现时间
      const visit = {};// 访问时间
      const back = {};// 回溯时间
      const time = { t: 0 }//用于计时
      for (let v of vertices) {
        color[v] = "WHITE";
        //初始化
        find[v] = 0;
        visit[v] = 0;
        back[v] = null;
      }
      // 因为有向图，每个节点不一定能到达其他节点
      for(let v of vertices){
        depthFirstSearch(v, adjList, color, find, visit, back, time);
      }
      return {
        find, visit, back, time
      }
    }
    fn(graph)

通过节点信息经行拓扑排序,按照访问时间从大到小

1
Object.entries(visit).sort((it, it2) => it2[1] - it1[1])

152.乘积最大子数组

算法 / 关联题目
LeetCode

动态规划

确定状态

最后一步

只考虑最后一步，为 ，很好理解，就是最后一个元素，稍稍复杂一点

因为本题不是求和，较小的值在下一次计算后（加上一个数或减去一个数）仍然是较小的值，但是乘法收到正负符号的影响，一个负数乘以另一个负数，可以是一个正数，所以这个 应该考虑正负的情况

子问题

由上面的分析，原问题为数组 子数组城际的最大值，除去最后一步之后子问题为 子数组的乘积最大值

所以用 来表示子数组乘积最大值

转移方程

根据确定状态的分析 ， 为上一步的最大值，考虑到正负符号的影响，应该同时保存最大值和最小值，因为最小值乘以 可能变为最大值

初始条件和边界情况

初始化

用于记录最大值

计算顺序

，， 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 var maxProduct = function (nums) {
    var n = nums.length,
        // 初始化第一个
        // 考虑到f[1]依赖f[0]的结果至少要初始化一组数据
        f = [
            [nums[0], nums[0]]
        ],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
        if (f[i - 1][0] == 0) {
            f[i] = [nums[i], nums[i]]
        } else {
            var min = Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            var max = Math.max(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            f[i] = [min, max];
        }
        if (f[i][1] > res) res = f[i][1];
    }
    return res
};

优化

  • 删除无用的代码
1
2
3
if (f[i - 1][0] == 0) {
    f[i] = [nums[i], nums[i]]
}

最初考虑到num[i+1]===0的情况，会将f[i+1]最小值，最大值都变为0，会使后面的循环计算都为0，但无需有这种担心，因为Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]); 最大值最小值的计算都有nums[i]的比较，并不会使后面的运算一直为0

这里还需要考虑为什么需要用nums[i]，对于数组[-2,-3,0,2-2]

循环 值
初始化 f[0] = [-2,-2]，最大值最小值都为第一个数
1 f[1] = [6,-3]，有最小值并不是乘积得出的情况，而是元素本身就是最小值
2 f[2] = [0,0]，遇到零的情况
3 f[3] = [2,0]，最大值为元素本身，并不是乘积
4 f[4] = [0,-4] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxProduct = function (nums) {
    var n = nums.length,
        f = [
            [nums[0], nums[0]]
        ],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
            var min = Math.min(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            var max = Math.max(f[i - 1][0] * nums[i], f[i - 1][1] * nums[i], nums[i]);
            f[i] = [min, max];
        if (f[i][1] > res) res = f[i][1];
    }
    return res
};
  • 优化数储存，可以发现我们每次存下来的最大值最小值，只会用在下一次的计算中，所以并不需要额外的空间把每一个结果保存下来，只需要三个变量
变量 作用
max 临时储存上一次的最大值
min 临时储存上一次的最小值
res 保存最终结果的最大值 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxProduct = function (nums) {
    var n = nums.length,
        max = nums[0],
        min = nums[0],
        i = 1,
        res = nums[0];
    for (; i < n; i++) {
        var _min = Math.min(min * nums[i], max * nums[i], nums[i]);
        var _max = Math.max(min * nums[i], max * nums[i], nums[i]);
        // 防止相互影响
        min = _min;
        max = _max;
        if (max > res) res = max;
    }
    return res
};

  • 通过判断是否负数，交换两个元素

    初始化时min=1,max=1,巧妙的从下表为0的位置遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var maxProduct = function (nums) {
    var n = nums.length,
        max = 1,
        min = 1,
        res=-Infinity;
    for (var i=0; i < n; i++) {
        if(nums[i]< 0){
            var temp = max;
            max = min;
            min = temp;
        }
        var min = Math.min(min* nums[i], nums[i]);
        var max = Math.max(max*nums[i], nums[i]);
        if (max > res) res = max;
    }
    return res
};

复杂度分析

  • 时间复杂度：程序一次循环遍历了 ，故渐进时间复杂度为 。

  • 空间复杂度：优化后只使用常数个临时变量作为辅助空间，与 无关，故渐进空间复杂度为

  • Copyrights © 2015-2025 SunZhiqi

此时无声胜有声！

支付宝
微信