Jiez19971225‘s Blog

锁机制

• mysql 里面的锁可以大致分成全局锁，表级锁和行锁

全局锁

全局锁对整个数据库实例加锁
Flush tables with read lock(FTWRL)
当使用这个命令后，其他线程的一下语句会被阻塞：数据更新语句，数据定义语句和更新类事务的提交语句
典型使用场景是做全局逻辑备份

• 主库上备份，业务会停摆
• 从库上备份，备份期间不能执行主库同步过来的 binlog，导致主从延迟
  官方自带的逻辑备份工具是 mysqldump，当使用参数-single-transaction 的时候，导数据之前就会启动一个事务，确保拿到一致性视图
• myisam 不支持事务的引擎，这时就需要使用 FTWRL
• 不建议使用 set global readonly = true

表级锁

lock tables … read/write
可以使用 unlock 主动释放，也可以在客户端断开的时候自动释放

count(*)

• MyiSAM 把表的总行数存在了磁盘上，因此效率很高
• innodb 需要一行一行统计
• 在保证逻辑正确的前提下 尽量减少扫描的数据量 是数据库系统设计的通用法则之一
• show table status 返回很快 但是不准确
• innodb 可以将计数保存到一张表中，使用事务，保持了一致性
• count(id) innodb 会遍历整张表，把每一行的 id 都取出来，返回给 server 层，server 层拿到 id 后，判断是不可能为空的，就按行累加
• count(1) innodb 引擎便利整张表，但不取值，server 层对返回的每一行，放一个数字 1 进去，判断是不可能为空的，按行累加
• count(字段)
  • 如果是 not null 就一行行独读出，判断不能为 null，按行累加
  • 如果允许为 null，不是 null 才累加
• count(*)做了优化，按行累加

答疑 1

• insert on duplicate 确保了在事务内部，执行 SQL 后占住了这个行锁

order by 是怎么工作的

• mysql 的外部排序采用归并排序，将排序数据分成多个保存到临时文件中，最后合并为一个大文件
• mysql 有两种排序方式 全字段排序和 rowid 排序，mysql 的设计思想是，如果内存够，就要多利用内存，尽量减少磁盘访问
• rc 模式下 for update 对所有行加了 X 锁 没有上 gap 锁 rr 模式下，也加了 X 锁
• 幻读是指一个事务在前后两次查询同一个范围的时候，后一次查询到了前一次没看到的行
• 加上 forupdate 是当前读

查询过程

查询缓存

Mysql 拿到一个查询请求后，会先到查询缓存看是否执行过该语句。缓存可能会以 key-value 对形式直接缓存在内存，如果能直接在缓存中找到结果，就直接返回 value 给客户端，否则，就继续后面的执行阶段。执行完成后，执行结果被存入查询缓存。

但是查询缓存的失效非常频繁，只要对一个表有更新，这个表上所有查询缓存都会被清空。从 mysql8.0 版本，查询缓存的功能被删除了。

日志系统

redolog

WAL 技术全称是 Write-Ahead Logging 先写日志，再写磁盘，当有一条记录需要更新的时候，innodb 会把记录写到 redo log，并更新内存，并在适当的时候，将这个操作记录更新到磁盘。redolog 的大小是固定的，写到末尾又会回到开头覆写。
因为 redolog，innodb 可以保证数据库异常重启后，之前提交的记录不会丢失，称为 crash-safe。

binlog

redolog 是 innodb 特有的 log，而 server 层也有自己的日志，称为 binlog（归档日志）
redolog 是物理日志，记录在某个数据页做了什么修改，binlog 是逻辑日志，记录的是语句的原始逻辑
binlog 采用追加写，写到一定大写后会创建新的 binlog，不会覆盖之前的日志

两阶段提交

浅色表示在 innoDB 内部执行，深色表示在执行器中执行

redolog 的写入拆分成 parpare 和 commit 两步，保证两个日志逻辑上的一致，这给了 binlog 和 redolog 一个同时说 ok 的机会

崩溃恢复原则

redo log 和 binlog 有一个共同的数据字段，叫 XID。崩溃恢复的时候，会按顺序扫描 redo log：

1. 如果碰到既有 prepare、又有 commit 的 redo log，就直接提交；
2. 如果碰到只有 parepare、而没有 commit 的 redo log，就拿着 XID 去 binlog 找对应的事务。
   • binlog 无记录，回滚事务
   • binlog 有记录，提交事务。

其他

set innodb_flush_log_at_trx_commit = 1 将每次事务都持久化到磁盘
set sync_binlog = 1 将每次事务的 binlog 都持久化到磁盘

事务隔离

读未提交，一个事务还没提交时，它做的变更就能被别的事务看到
读提交，一个事务提交之后，他做的变更才会被其他事务看到
可重复读是，一个事务执行过程中看到的数据，总是跟这个事务在启动时看到的数据是一样的，未提交的变更对其他事务是不可见的
串行化，对于同一行记录，写会加写锁，读会加读锁，当出现读写锁冲突的时候，后访问的事务必须等前一个事务执行完成后才能继续执行
配置方式 将启动参数 transaction_isolation 的值设置成 READ-COMMITTED，可以用 show variables 查看当期数值

数据库内会创建一个视图，访问的时候以视图的逻辑结果为准。在可重复读隔离级别下，这个视图是在事务启动的时候创建的，整个事务存在期间都用这个事务。在读提交级别下，这个视图是在每个 sql 语句开始执行的时候创建的。读未提交没有视图概念，串行化直接用加锁的方式避免并行访问。

事务隔离的实现

可重复读 每条记录在更新的时候都会同时记录一条回滚操作，记录上的最新值，通过回滚操作，可以得到前一个状态的值
不同时刻启动的事务会有不同的 read-view,同一个记录的值分别是 1,2,3,4，同一个记录在系统中可以存在多个版本，这是数据库的多版本并发控制 mvcc。对于 read-view A，要得到更新后的值，就必须将当前数值依次执行所有回滚操作
回滚日志会一直保留到没有比这个更早的 read-view 的时候，因此尽量不要使用长事务

事务的启动方式

显式启动事务 begin 或 start transaction 提交使用 commit 回滚使用 rollback
set autocommit=0 会将线程的自动提交关掉，这意味着事务不会自动提交，知道主动执行 commit 或者 rollback 或者断开连接，建议总是设置 autocommit 为 1
可以在 informatino_schema 库的 innodb_trx 表中查询长事务

索引

• 三种数据结构
  • 哈希表 优点是增加新的 user 时速度很快，只需要往后追加，但缺点是，因为不是有序的，哈希索引做区间查询速度很慢
  • 有序数组 在等值查询和范围查询场景的性能非常优秀，但是需要插入的时候成本太高，只适用于静态存储引擎
  • 搜索树 目前数据库中使用的是 N 叉数

innodb 的索引模型

• innodb 中，表都是根据主键顺序以索引的形式存放的，这种方式称为索引组织表，使用 B+树索引模型，所有数据存储在 B+树中。
• 主键索引的叶子节点存的是整行数据，在 innodb 中，主键索引也被称为聚簇索引，非主键索引的叶子节点的内容是主键的数值，非主键索引也被称为二级索引
• 使用二级索引查表需要先找到主键的值，再在主键的索引书搜索一次，这个过程称为回表

索引维护

• 主键索引树需要保持树的有序性，自增主键的插入数据模式的耗时很低，而有业务逻辑的字段作主键，往往不容易保证有序插入，这样写数据的成本相对较高
• 而且从空间角度，使用 int 型作为主键，占用的空间也较小，主键索引越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小
• 直接用业务字段作主键
  • 只有一个索引
  • 该索引必须是唯一索引

覆盖索引

如果在某个查询里面，索引 k 已经覆盖了我们的查询需求，我们称其为覆盖索引。覆盖索引可以减少树的搜索次数，显著提升查询性能

最左索引

• 不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以使联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

下推优化

mysql5.6 之后，可以在索引遍历的过程中，对索引包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表的次数

重建索引

重建主键索引会将整个表重建

• 普通索引与唯一索引的性能差距
  对于普通索引，查找到满足条件的第一条记录后，还需要继续查找知道碰到第一个不满足条件的记录，对于唯一索引，由于定义了唯一性，查找到第一个满足条件的记录后就会停止继续检索，这带来的性能差距呢是微乎其微，innodb 是按照页读写的，当找到记录的时候，他所在的数据页也都在内存中，因此下一次查找的消耗很低
• change buffer
  当需要更新一个数据页时，如果数据页在内存中就直接更新，如果不再，在不影响数据一致性的前提下，innodb 会将更新操作缓存在 changer buffer 中，当下一次查询需要访问这个页面的时候，将数据读入内存，然后执行 change buffer 中与这个页有关的操作。很像操作系统中的页面交换。
• 将 change buffer 中的操作应用到原数据页，得到最新结果的过程称为 purge，除了访问这个数据页会触发 purge，还有后台线程会定期 purge，在数据库正常关闭的过程中，也会执行 purge
• 对于唯一索引，所有更新操作都先判断这个操作是否违反唯一约数，要将数据页读入内存才能判断，没必要使用 change buffer 实际上只有普通索引可以使用
• change buffer 用的是 buffer pool 里的内存，可通过 innodb_change_buffer_max_size 来动态设置
• 对于写多读少的业务，比较适合使用 change buffer，如果业务写入之后立即查询，由于会频繁触发 purge 过程，增加了 change buffer 的维护代价，反而起到了副作用

mysql 选择了错误的索引

• 可以使用 force index 强制选取使用的索引

let const

let

它的用法类似于 var，但是所声明的变量，只在 let 命令所在的代码块内有效

不存在变量提升

var 命令会发生“变量提升”现象，即变量可以在声明之前使用，let 命令改变了语法行为，它所声明的变量一定要在声明后使用，否则报错

暂时性死区

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

1
2
3
4
5
6

var tmp = 123;

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

存在全局变量 tmp，但是块级作用域内 let 又声明了一个局部变量 tmp，导致后者绑定这个块级作用域，所以在 let 声明变量前，对 tmp 赋值会报错

不允许重复声明

块级作用域

ES6 引入了块级作用域，明确允许在块级作用域之中声明函数。ES6 规定，块级作用域之中，函数声明语句的行为类似于 let，在块级作用域之外不可引用 但是浏览器的实现与规范不同，应避免使用该写法

const

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

如果真的想将对象冻结，应该使用 Object.freeze 方法

变量的解构赋值

基本用法

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

事实上，只要某种数据结构具有 Iterator 接口，都可以采用数组形式的解构赋值。

默认值

解构赋值允许指定默认值。

ES6 内部使用严格相等运算符（===），判断一个位置是否有值。所以，只有当一个数组成员严格等于 undefined，默认值才会生效

对象的解构赋值

如果解构失败，变量的值等于 undefined

对象的属性没有次序，变量必须与属性同名，才能取到正确的值

如果变量名与属性名不一致，必须写成下面这样。

1
2
3
4
5
6
7

let { foo: baz } = { foo: 'aaa', bar: 'bbb' };
baz // "aaa"

let obj = { first: 'hello', last: 'world' };
let { first: f, last: l } = obj;
f // 'hello'
l // 'world'

字符串的解构赋值

• 字符串也可以解构赋值。这是因为此时，字符串被转换成了一个类似数组的对象

数值和布尔值的解构赋值

解构赋值时，如果等号右边是数值和布尔值，则会先转为对象

函数参数的解构赋值

函数的参数也可以使用解构赋值

用途

交换变量的值 从函数返回多个值 函数参数的定义 提取 JSON 数据 函数参数的默认值 遍历 Map 结构 输入模块的指定方法

字符串的扩展

字符的 Unicode 表示法

允许采用\uxxxx形式表示一个字符，其中 xxxx 表示字符的 Unicode 码点 可将码点放入大括号

ES6 为字符串添加了遍历器接口（详见《Iterator》一章），使得字符串可以被 for…of 循环遍历。这个遍历器最大的优点是可以识别大于 0xFFFF 的码点，传统的 for 循环无法识别这样的码点。

JSON.stringify() 的改造

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

模板字符串

反引号（`）标识。它可以当作普通字符串使用，也可以用来定义多行字符串，或者在字符串中嵌入变量

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

模板字符串之中可以放入表达式，还能调用函数

如果大括号中的值不是字符串，将按照一般的规则转为字符串。比如，大括号中是一个对象，将默认调用对象的 toString 方法

字符串的新增方法

String.fromCodePoint()

用于从 Unicode 码点返回对应字符，但是这个方法不能识别码点大于 0xFFFF 的字符

String.raw()

该方法返回一个斜杠都被转义（即斜杠前面再加一个斜杠）的字符串，往往用于模板字符串的处理方法

codePointAt()

能够正确处理 4 个字节储存的字符，返回一个字符的码点

normalize()

用来将字符的不同表示方法统一为同样的形式，这称为 Unicode 正规化

includes(), startsWith(), endsWith()

includes()：返回布尔值，表示是否找到了参数字符串。
startsWith()：返回布尔值，表示参数字符串是否在原字符串的头部。
endsWith()：返回布尔值，表示参数字符串是否在原字符串的尾部。

repeat()

repeat 方法返回一个新字符串，表示将原字符串重复 n 次

padStart()，padEnd()

padStart()用于头部补全，padEnd()用于尾部补全

trimStart()，trimEnd()

trimStart()消除字符串头部的空格，trimEnd()消除尾部的空格。它们返回的都是新字符串，不会修改原始字符串。

matchAll()

matchAll()方法返回一个正则表达式在当前字符串的所有匹配

数值的扩展

二进制和八进制表示

ES6 提供了二进制和八进制数值的新的写法，分别用前缀 0b（或 0B）和 0o（或 0O）表示。

Number.isFinite(), Number.isNaN()

判断是否为极限和 NaN

Number.isFinite(), Number.isNaN()

ES6 将全局方法 parseInt()和 parseFloat()，移植到 Number 对象上面，行为完全保持不变

Number.isInteger()

Number.isInteger()用来判断一个数值是否为整数

Number.EPSILON

一个极小的常量 Number.EPSILON。根据规格，它表示 1 与大于 1 的最小浮点数之间的差

安全整数和 Number.isSafeInteger()

ES6 引入了 Number.MAX_SAFE_INTEGER 和 Number.MIN_SAFE_INTEGER 这两个常量
Number.isSafeInteger()则是用来判断一个整数是否落在这个范围之内

Math 对象的扩展

Math.trunc 方法用于去除一个数的小数部分，返回整数部分
Math.sign 方法用来判断一个数到底是正数、负数、还是零。对于非数值，会先将其转换为数值
Math.cbrt 方法用于计算一个数的立方根

函数的扩展

基本用法

ES6 允许为函数的参数设置默认值，即直接写在参数定义的后面

参数变量是默认声明的，所以不能用 let 或 const 再次声明

与解构赋值默认值结合使用

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 m1({x = 0, y = 0} = {}) {
  return [x, y];
}

// 写法二
function m2({x, y} = { x: 0, y: 0 }) {
  return [x, y];
}
// 函数没有参数的情况
m1() // [0, 0]
m2() // [0, 0]

// x 和 y 都有值的情况
m1({x: 3, y: 8}) // [3, 8]
m2({x: 3, y: 8}) // [3, 8]

// x 有值，y 无值的情况
m1({x: 3}) // [3, 0]
m2({x: 3}) // [3, undefined]

// x 和 y 都无值的情况
m1({}) // [0, 0];
m2({}) // [undefined, undefined]

m1({z: 3}) // [0, 0]
m2({z: 3}) // [undefined, undefined]

参数默认值的位置

通常情况下，定义了默认值的参数，应该是函数的尾参数。因为这样比较容易看出来，到底省略了哪些参数。如果非尾部的参数设置默认值，实际上这个参数是没法省略的。如果传入 undefined，将触发该参数等于默认值，null 则没有这个效果。

函数的 length 属性

指定了默认值以后，函数的 length 属性，将返回没有指定默认值的参数个数。也就是说，指定了默认值后，length 属性将失真。

作用域

一旦设置了参数的默认值，函数进行声明初始化时，参数会形成一个单独的作用域（context）。等到初始化结束，这个作用域就会消失。这种语法行为，在不设置参数默认值时，是不会出现的。

应用

利用参数默认值，可以指定某一个参数不得省略，如果省略就抛出一个错误

1
2
3
4
5
6
7
8

function throwIfMissing() {
  throw new Error('Missing parameter');
}

function foo(mustBeProvided = throwIfMissing()) {
  return mustBeProvided;
}
foo()

rest 参数

ES6 引入 rest 参数（形式为…变量名），用于获取函数的多余参数，这样就不需要使用 arguments 对象了 sort 默认是按照 unicode 码点顺序排序

1
2

const sortNumber = (...number) => number.sort()
console.log(sortNumber(3, 2, 1))

rest 参数之后不能再有其他参数

name 属性

函数的 name 属性，返回该函数的函数名

箭头函数

函数体内的 this 对象，就是定义时所在的对象，而不是使用时所在的对象，在箭头函数中，它是固定的

不可以当作构造函数，也就是说，不可以使用 new 命令，否则会抛出一个错误

不可以使用 arguments 对象，该对象在函数体内不存在。如果要用，可以用 rest 参数代替。

不可以使用 yield 命令，因此箭头函数不能用作 Generator 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function Timer() {
  this.s1 = 0;
  this.s2 = 0;
  // 箭头函数
  setInterval(() => this.s1++, 1000);
  // 普通函数
  setInterval(function () {
    this.s2++;
  }, 1000);
}

var timer = new Timer();

setTimeout(() => console.log('s1: ', timer.s1), 3100);
setTimeout(() => console.log('s2: ', timer.s2), 3100);
// s1: 3
// s2: 0

上面代码中，Timer 函数内部设置了两个定时器，分别使用了箭头函数和普通函数。前者的 this 绑定定义时所在的作用域（即 Timer 函数），后者的 this 指向运行时所在的作用域（即全局对象）。所以，3100 毫秒之后，timer.s1 被更新了 3 次，而 timer.s2 一次都没更新。

不能用 call()、apply()、bind()这些方法去改变 this 的指向

不适用场合

由于箭头函数使得 this 从“动态”变成“静态”，下面两个场合不应该使用箭头函数。

第一个场合是定义对象的方法，且该方法内部包括 this。

1
2
3
4
5
6

const cat = {
  lives: 9,
  jumps: () => {
    this.lives--;
  }
}

上面代码中，cat.jumps()方法是一个箭头函数，这是错误的。调用 cat.jumps()时，如果是普通函数，该方法内部的 this 指向 cat；如果写成上面那样的箭头函数，使得 this 指向全局对象，因此不会得到预期结果。这是因为对象不构成单独的作用域，导致 jumps 箭头函数定义时的作用域就是全局作用域。

第二个场合是需要动态 this 的时候，也不应使用箭头函数。

函数式相关

省略

数组的扩展

扩展运算符

扩展运算符（spread）是三个点（…）。它好比 rest 参数的逆运算，将一个数组转为用逗号分隔的参数序列。该运算符主要用于函数调用。替代函数的 apply 方法

扩展运算符的应用

• 复制数组
• 合并数组
• 与解构赋值结合
• 任何定义了遍历器（Iterator）接口的对象（参阅 Iterator 一章），都可以用扩展运算符转为真正的数组。

Array.from

Array.from 方法用于将两类对象转为真正的数组
类似数组的对象（array-like object）和可遍历（iterable）的对象（包括 ES6 新增的数据结构 Set 和 Map）所谓类似数组的对象，本质特征只有一点，即必须有 length 属性。因此，任何有 length 属性的对象，都可以通过 Array.from 方法转为数组，而此时扩展运算符就无法转换。

Array.from 还可以接受第二个参数，作用类似于数组的 map 方法，用来对每个元素进行处理，将处理后的值放入返回的数组。

Array.of()

Array.of 方法用于将一组值，转换为数组。这个方法的主要目的，是弥补数组构造函数 Array()的不足。因为参数个数的不同，会导致 Array()的行为有差异。

copyWithin()

在当前数组内部，将指定位置的成员复制到其他位置（会覆盖原有成员），然后返回当前数组。也就是说，使用这个方法，会修改当前数组。

find() 和 findIndex()

数组实例的 find 方法，用于找出第一个符合条件的数组成员。它的参数是一个回调函数，所有数组成员依次执行该回调函数，直到找出第一个返回值为 true 的成员，然后返回该成员。如果没有符合条件的成员，则返回 undefined

数组实例的 findIndex 方法的用法与 find 方法非常类似，返回第一个符合条件的数组成员的位置，如果所有成员都不符合条件，则返回-1。

fill

fill 方法使用给定值，填充一个数组。fill 方法还可以接受第二个和第三个参数，用于指定填充的起始位置和结束位置

数组实例的 entries()，keys() 和 values()

keys()是对键名的遍历、values()是对键值的遍历，entries()是对键值对的遍历。

数组实例的 includes()

Array.prototype.includes 方法返回一个布尔值，表示某个数组是否包含给定的值，与字符串的 includes 方法类似

数组实例的 flat()，flatMap()

flat()默认只会“拉平”一层，如果想要“拉平”多层的嵌套数组，可以将 flat()方法的参数写成一个整数，表示想要拉平的层数，默认为 1。

flatMap()方法对原数组的每个成员执行一个函数（相当于执行 Array.prototype.map()），然后对返回值组成的数组执行 flat()方法。

数组的空位

不建议保留空位，es6 对于空位设置文 undefined

对象的扩展

属性的简洁表示

ES6 允许直接写入变量和函数，作为对象的属性和方法。这样的书写更加简洁

属性名表达式

ES6 允许字面量定义对象时，用方法二（表达式）作为对象的属性/方法名，即把表达式放在方括号内。

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

方法的 name 属性

函数的 name 属性，返回函数名

如果对象的方法使用了取值函数（getter）和存值函数（setter），则 name 属性不是在该方法上面，而是该方法的属性的描述对象的 get 和 set 属性上面，返回值是方法名前加上 get 和 set。有两种特殊情况：bind 方法创造的函数，name 属性返回 bound 加上原函数的名字；Function 构造函数创造的函数，name 属性返回 anonymous。

属性的可枚举性和遍历

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

enumerable 属性，称为“可枚举性”目前，有四个操作会忽略 enumerable 为 false 的属性。只有 for…in 会返回继承的属性，其他三个方法都会忽略继承的属性，只处理对象自身的属性。另外，ES6 规定，所有 Class 的原型的方法都是不可枚举的。大多数时候，我们只关心对象自身的属性。所以，尽量不要用 for…in 循环，而用 Object.keys()代替。

• for…in 循环：只遍历对象自身的和继承的可枚举的属性。
• Object.keys()：返回对象自身的所有可枚举的属性的键名。
• JSON.stringify()：只串行化对象自身的可枚举的属性。
• Object.assign()： 忽略 enumerable 为 false 的属性，只拷贝对象自身的可枚举的属性

super 关键字

super，指向当前对象的原型对象 目前，只有对象方法的简写法可以让 JavaScript 引擎确认，定义的是对象的方法 avaScript 引擎内部，super.foo 等同于 Object.getPrototypeOf(this).foo（属性）或 Object.getPrototypeOf(this).foo.call(this)（方法）。

对象的解构赋值

由于解构赋值要求等号右边是一个对象，所以如果等号右边是 undefined 或 null，就会报错，因为它们无法转为对象

解构赋值必须是最后一个参数

扩展运算符

• 对象的扩展运算符（…）用于取出参数对象的所有可遍历属性，拷贝到当前对象之中。
• 由于数组是特殊的对象，所以对象的扩展运算符也可以用于数组。
• 如果扩展运算符后面是一个空对象，则没有任何效果。
• 如果扩展运算符后面不是对象，则会自动将其转为对象。
• 如果扩展运算符后面是字符串，它会自动转成一个类似数组的对象
• 对象的扩展运算符等同于使用 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)
)

• 修改现有对象部分的属性

1
2
3
4

let newVersion = {
  ...previousVersion,
  name: 'New Name' // Override the name property
};

• 与数组的扩展运算符一样，对象的扩展运算符后面可以跟表达式
• 扩展运算符的参数对象之中，如果有取值函数 get，这个函数是会执行的

对象的新增方法

Object.is()

它用来比较两个值是否严格相等，与严格比较运算符（===）的行为基本一致

Object.assign()

Object.assign 方法用于对象的合并，将源对象（source）的所有可枚举属性，复制到目标对象（target）。浅拷贝，同名属性的替换 ，可以用来处理数组，但是会把数组视为对象，如果要复制的值是一个取值函数，那么将求值后再复制。

Object.getOwnPropertyDescriptors

返回指定对象所有自身属性（非继承属性）的描述对象。

Object.getOwnPropertyDescriptors()方法的另一个用处，是配合 Object.create()方法，将对象属性克隆到一个新对象。这属于浅拷贝。

1
2
3
4
5
6
7
8
9

const clone = Object.create(Object.getPrototypeOf(obj),
  Object.getOwnPropertyDescriptors(obj));

// 或者

const shallowClone = (obj) => Object.create(
  Object.getPrototypeOf(obj),
  Object.getOwnPropertyDescriptors(obj)
);

proto

proto属性 用来读取或设置当前对象的 prototype 对象 建议使用下面的 Object.setPrototypeOf()（写操作）、Object.getPrototypeOf()（读操作）、Object.create()（生成操作）代替

如果一个对象本身部署了proto属性，该属性的值就是对象的原型。

Object.fromEntries()

Object.fromEntries()方法是 Object.entries()的逆操作，用于将一个键值对数组转为对象。

一致性 要求和建议

CSS 渲染模型中不考虑替换元素的内容。

在 CSS 2.1 中，只有替换元素才能具有内在维度。对于没有可靠分辨率信息的光栅图像，必须假设每个图像源像素的大小为 1 像素单位。

HTML 的元素名是大小写不敏感的 但是在 XML 中是大小写敏感的

0 长度单位后的单位是可选的

选择器

E[foo] 匹配设置了”foo”属性（无论值是什么）的 E 元素

E[foo=”warning”] 匹配所有”foo”属性值恰好是”wraning”的 E 元素

E[foo~=”warning”] 匹配所有”foo”属性值为一列空格分隔的值，且其中之一恰好是”warning”的 E 元素

E[lang|=”en”] 匹配所有”lang”属性值为一列以”en”开头（从左向右）用连字符分隔的值的 E 元素

link 伪类：:link 与:visited

动态伪类： :hover，:active 与:focus

:first-line 伪元素对段落内容的第一个格式化行应用特殊样式(选择器”P:first-line”不会匹配任何真实 HTML 元素。它匹配一个（与 CSS 规范）一致的用户代理将在每个段落的开头插入的伪元素) :first-line 伪元素只能用于块容器元素

:first-letter 伪元素必须选择一个块的第一行的第一个字母

当:first-letter 和:first-line 伪元素被应用在一个具有使用:before 和:after 生成内容的元素，它们应用于元素包括生成的内容在内的首字母或首行

层叠和继承

为了让用户代理能够避免为不支持的媒体类型检索资源，编写者可以指定带媒体依赖（media-dependent）的@import 规则。

1

@import url("fineprint.css") print;

• 用户样式表，简单来说就是浏览器的使用者自己编写的一份默认样式表，编写者样式表，是网页的编写者编写的样式表，第一次听说这种说法

视觉格式化模型

Block-level 块级元素 包含以下类型 block list-item table list-item 会生成附加的盒子，相对于主盒子放置

block container box 只包含块级元素或者内联块级元素，

匿名块级盒子 当块级盒子同时包含内联的文本和块级元素时，我们认为这里有一个匿名的盒子包围了这些文本，如果一个块级盒子包含了块级盒子，我们强制让他只包含块级盒子

以@开头的规则（At-rules）需要以分号来结尾

CSS 2.1 用户代理必须忽略在块内或在除@cherset 或@import 规则之外的任何非忽略语句之后发生的任何“@import”规则。一下是非法的，解决方法是将样式的语法放在 At-rules 之后

1
2
3

@import "subs.css";
h1 { color: blue }
@import "list.css";

盒模型

‘margin-top’, ‘margin-bottom’ 这两个属性对非替换的行内元素无效

两个 margin 是相邻的，当且仅当

都属于流内（in-flow）块级盒，处于同一个块格式化上下文

• 没有行框（line box），空隙，内边距和边框把它们隔开（注意，因此某些 0 高度行框（见 9.4.2）会被忽略）
• 都属于垂直相邻框边界（vertically-adjacent box edges），即形成下列某一对：
  • 盒的上边距与其第一个流内（in-flow）孩子的上边距
  • 盒的下边距与其下一个流内紧挨着的兄弟的上边距
  • 最后一个流内孩子的下边距与其 height 计算值为’auto’的父元素的下边距
  • 盒的上边距和下边距，要求该盒没有建立新的块格式化上下文，并且’min-height’计算值为 0，’height’计算值为 0 或’auto’，还没有流内孩子
• margin 和 padding 的百分比数值都相对于包含块，border 不能设置百分比数值

块格式化上下文

以下方式会创建块格式化上下文

• 根元素或包含根元素的元素
• 浮动元素（元素的 float 不是 none）
• 绝对定位元素（元素的 position 为 absolute 或 fixed）
• 行内块元素（元素的 display 为 inline-block）
• 表格单元格（元素的 display 为 table-cell，HTML 表格单元格默认为该值）
• 表格标题（元素的 display 为 table-caption，HTML 表格标题默认为该值）
• 匿名表格单元格元素（元素的 display 为 table、table-row、 table-row-group、table-header-group、table-footer-group（分别是 HTML table、row、tbody、thead、tfoot 的默认属性）或 inline-table）
• overflow 值不为 visible 的块元素
• display 值为 flow-root 的元素
• contain 值为 layout、content 或 strict 的元素
• 弹性元素（display 为 flex 或 inline-flex 元素的直接子元素）
• 网格元素（display 为 grid 或 inline-grid 元素的直接子元素）
• 多列容器（元素的 column-count 或 column-width 不为 auto，包括 column-count 为 1）
• column-span 为 all 的元素始终会创建一个新的 BFC，即使该元素没有包裹在一个多列容器中

• 块格式化上下文对浮动定位（参见 float）与清除浮动（参见 clear）都很重要。浮动定位和清除浮动时只会应用于同一个 BFC 内的元素。浮动不会影响其它 BFC 中元素的布局，而清除浮动只能清除同一 BFC 中在它前面的元素的浮动。外边距折叠（Margin collapsing）也只会发生在属于同一 BFC 的块级元素之间。

• 行内级元素是源文档中那些不会形成新内容块的元素，内容分布于多行 ‘display’属性的下列值能让一个元素变成行内级：’inline’，’inline-table’和’inline-block’。一个 inline-block 的内部会被格式化成一个块盒，而该元素本身会被格式化成一个原子行内级盒

• display 为 table 系的元素的 postion:relative 效果是未定义的

• 盒偏移：’top’，’right’，’bottom’，’left’ 如果元素的’position’属性有一个除’static’外的值，就说它是定位元素（positioned） 百分比数值参照包含块的宽度
• 如果’left’和’right’都不是’auto’，位置就被过度约束（over-constrained）了，它们（’left’和’right’）其中有一个会被忽略。如果包含块的’direction’属性是’ltr’，那么’left’有效，’right’变成-‘left’（负的’left’）。如果包含块的’direction’属性是’rtl’，那么’right’有效，’left’被忽略
• 清除浮动的方法 overflow-hidden 创建了一个 BFC，BFC 在计算高度的 也计算浮动元素的高度
• 注意 ‘direction’属性，给表格列元素指定时，不会被列中的单元格继承，因为在文档树中，列不是单元格的祖先。因此，CSS 无法轻易获知[HTML4]的 11.3.2.1 节中”dir”属性的继承规则
• direction 和 unicode-bidi 属性结合处理文本流方向问题（不仅，而且句子从右向左，单词也倒着写）

视觉格式化模型细节

width 应用于除了非替换的行内元素，表格行和行组（row group） 外的所有元素,非替换的行内元素盒的内容宽度是它里面渲染的内容（的内容宽度）负值对于 width 是非法的。

行内非替换（non-replaced）元素 ‘width’属性不适用，其计算值为’auto’的’margin-left’或者’margin-right’对应的应用值为’0’。

行内替换元素 计算值为’auto’的’margin-left’或者’margin-right’对应的应用值为’0’ 如果’height’和’width’计算值都是’auto’，并且该元素还具有固有宽度，那么这个固有宽度就是’width’的应用值。

height 指定一个百分比高度。百分比参照生成盒的包含块的高度。如果包含块的高度没有显式指定（即取决于内容高度），并且该元素不是绝对定位的，则计算值为’auto’。根元素上的百分比高度是相对于初始包含块的 注意：对于那些包含块基于一个块级元素的绝对定位元素，百分比根据这个元素的内边距框（padding box）的高度来计算。这与 CSS1 不同，（CSS1 中）百分比总是根据父级元素的内容框（content box）来计算

line-height 的百分比参考元素自身的字体大小

vertical-align 的百分比是行高

可视化效果

• visibility hidden 生成的盒是不可见的（完全透明，什么都不绘制），但仍然会影响布局。而且该元素具有’visibility: visible’的后代将是可见的

颜色与背景

• background-attachment 指定了它应该相对视口固定，还是随包含块滚动

文本

• 字母与单词间距 ‘letter-spacing’和’word-spacing’
• ‘text-transform’属性 转换单词大小写
• ‘white-space’属性 决定如何处置换行符

用户界面

cursor crosshair 简单十字 move 暗示可移动 text 暗示可选中的文本 wait 暗示正忙
outline 当元素具有焦点时，可应用轮廓属性，该属性不占用空间

一致性 要求和建议

CSS 渲染模型中不考虑替换元素的内容。

在 CSS 2.1 中，只有替换元素才能具有内在维度。对于没有可靠分辨率信息的光栅图像，必须假设每个图像源像素的大小为 1 像素单位。

HTML 的元素名是大小写不敏感的 但是在 XML 中是大小写敏感的

0 长度单位后的单位是可选的

选择器

E[foo] 匹配设置了”foo”属性（无论值是什么）的 E 元素

E[foo=”warning”] 匹配所有”foo”属性值恰好是”wraning”的 E 元素

E[foo~=”warning”] 匹配所有”foo”属性值为一列空格分隔的值，且其中之一恰好是”warning”的 E 元素

E[lang|=”en”] 匹配所有”lang”属性值为一列以”en”开头（从左向右）用连字符分隔的值的 E 元素

link 伪类：:link 与:visited

动态伪类： :hover，:active 与:focus

:first-line 伪元素对段落内容的第一个格式化行应用特殊样式(选择器”P:first-line”不会匹配任何真实 HTML 元素。它匹配一个（与 CSS 规范）一致的用户代理将在每个段落的开头插入的伪元素) :first-line 伪元素只能用于块容器元素

:first-letter 伪元素必须选择一个块的第一行的第一个字母

当:first-letter 和:first-line 伪元素被应用在一个具有使用:before 和:after 生成内容的元素，它们应用于元素包括生成的内容在内的首字母或首行

层叠和继承

为了让用户代理能够避免为不支持的媒体类型检索资源，编写者可以指定带媒体依赖（media-dependent）的@import 规则。

1

@import url("fineprint.css") print;

用户样式表，简单来说就是浏览器的使用者自己编写的一份默认样式表，编写者样式表，是网页的编写者编写的样式表，第一次听说这种说法

视觉格式化模型

Block-level 块级元素 包含以下类型 block list-item table list-item 会生成附加的盒子，相对于主盒子放置

block container box 只包含块级元素或者内联块级元素，

匿名块级盒子 当块级盒子同时包含内联的文本和块级元素时，我们认为这里有一个匿名的盒子包围了这些文本，如果一个块级盒子包含了块级盒子，我们强制让他只包含块级盒子

以@开头的规则（At-rules）需要以分号来结尾

CSS 2.1 用户代理必须忽略在块内或在除@cherset 或@import 规则之外的任何非忽略语句之后发生的任何“@import”规则。一下是非法的，解决方法是将样式的语法放在 At-rules 之后

1
2
3
4
5

@import "subs.css";
h1 {
  color: blue;
}
@import "list.css";

盒模型

margin-top, margin-bottom 这两个属性对非替换的行内元素无效

两个 margin 是相邻的，当且仅当

都属于流内（in-flow）块级盒，处于同一个块格式化上下文

• 没有行框（line box），空隙，内边距和边框把它们隔开（注意，因此某些 0 高度行框（见 9.4.2）会被忽略）
• 都属于垂直相邻框边界（vertically-adjacent box edges），即形成下列某一对：
  • 盒的上边距与其第一个流内（in-flow）孩子的上边距
  • 盒的下边距与其下一个流内紧挨着的兄弟的上边距
  • 最后一个流内孩子的下边距与其 height 计算值为’auto’的父元素的下边距
  • 盒的上边距和下边距，要求该盒没有建立新的块格式化上下文，并且’min-height’计算值为 0，’height’计算值为 0 或’auto’，还没有流内孩子
• margin 和 padding 的百分比数值都相对于包含块，border 不能设置百分比数值

块格式化上下文

以下方式会创建块格式化上下文

• 根元素或包含根元素的元素
• 浮动元素（元素的 float 不是 none）
• 绝对定位元素（元素的 position 为 absolute 或 fixed）
• 行内块元素（元素的 display 为 inline-block）
• 表格单元格（元素的 display 为 table-cell，HTML 表格单元格默认为该值）
• 表格标题（元素的 display 为 table-caption，HTML 表格标题默认为该值）
• 匿名表格单元格元素（元素的 display 为 table、table-row、 table-row-group、table-header-group、table-footer-group（分别是 HTML table、row、tbody、thead、tfoot 的默认属性）或 inline-table）
• overflow 值不为 visible 的块元素
• display 值为 flow-root 的元素
• contain 值为 layout、content 或 strict 的元素
• 弹性元素（display 为 flex 或 inline-flex 元素的直接子元素）
• 网格元素（display 为 grid 或 inline-grid 元素的直接子元素）
• 多列容器（元素的 column-count 或 column-width 不为 auto，包括 column-count 为 1）
• column-span 为 all 的元素始终会创建一个新的 BFC，即使该元素没有包裹在一个多列容器中
• 块格式化上下文对浮动定位（参见 float）与清除浮动（参见 clear）都很重要。浮动定位和清除浮动时只会应用于同一个 BFC 内的元素。浮动不会影响其它 BFC 中元素的布局，而清除浮动只能清除同一 BFC 中在它前面的元素的浮动。外边距折叠（Margin collapsing）也只会发生在属于同一 BFC 的块级元素之间。
• 行内级元素是源文档中那些不会形成新内容块的元素，内容分布于多行 ‘display’属性的下列值能让一个元素变成行内级：’inline’，’inline-table’和’inline-block’。一个 inline-block 的内部会被格式化成一个块盒，而该元素本身会被格式化成一个原子行内级盒
• display 为 table 系的元素的 postion:relative 效果是未定义的
• 盒偏移：’top’，’right’，’bottom’，’left’ 如果元素的’position’属性有一个除’static’外的值，就说它是定位元素（positioned） 百分比数值参照包含块的宽度
• 如果’left’和’right’都不是’auto’，位置就被过度约束（over-constrained）了，它们（’left’和’right’）其中有一个会被忽略。如果包含块的’direction’属性是’ltr’，那么’left’有效，’right’变成-‘left’（负的’left’）。如果包含块的’direction’属性是’rtl’，那么’right’有效，’left’被忽略
• 清除浮动的方法 overflow-hidden 创建了一个 BFC，BFC 在计算高度的 也计算浮动元素的高度
• 注意 ‘direction’属性，给表格列元素指定时，不会被列中的单元格继承，因为在文档树中，列不是单元格的祖先。因此，CSS 无法轻易获知[HTML4]的 11.3.2.1 节中”dir”属性的继承规则
• direction 和 unicode-bidi 属性结合处理文本流方向问题（不仅，而且句子从右向左，单词也倒着写）

视觉格式化模型细节

width 应用于除了非替换的行内元素，表格行和行组（row group） 外的所有元素,非替换的行内元素盒的内容宽度是它里面渲染的内容（的内容宽度）负值对于 width 是非法的。

行内非替换（non-replaced）元素 ‘width’属性不适用，其计算值为’auto’的’margin-left’或者’margin-right’对应的应用值为’0’。

行内替换元素 计算值为’auto’的’margin-left’或者’margin-right’对应的应用值为’0’ 如果’height’和’width’计算值都是’auto’，并且该元素还具有固有宽度，那么这个固有宽度就是’width’的应用值。

height 指定一个百分比高度。百分比参照生成盒的包含块的高度。如果包含块的高度没有显式指定（即取决于内容高度），并且该元素不是绝对定位的，则计算值为’auto’。根元素上的百分比高度是相对于初始包含块的 注意：对于那些包含块基于一个块级元素的绝对定位元素，百分比根据这个元素的内边距框（padding box）的高度来计算。这与 CSS1 不同，（CSS1 中）百分比总是根据父级元素的内容框（content box）来计算

line-height 的百分比参考元素自身的字体大小

vertical-align 的百分比是行高

可视化效果

visibility hidden 生成的盒是不可见的（完全透明，什么都不绘制），但仍然会影响布局。而且该元素具有visibility: visible 的后代将是可见的

颜色与背景

background-attachment 指定了它应该相对视口固定，还是随包含块滚动
文本
字母与单词间距 letter-spacing’和’word-spacing
text-transform属性 转换单词大小写
white-space属性 决定如何处置换行符

用户界面

cursor crosshair 简单十字 move 暗示可移动 text 暗示可选中的文本 wait 暗示正忙
outline 当元素具有焦点时，可应用轮廓属性，该属性不占用空间

数字逻辑电路基础

全加器 溢出标志的逻辑表达式 $OF=C_n \oplus C_(n-1)$ 因为若为两个正数相加，最高位必然没有进位，而弱次高位有进位，则说明溢出 若为两个负数相加，最高位必然有进位，若次高位没有进位，则说明溢出

IEEE754 标准

• 32 位包括 1 位符号位 8 位阶码 23 位有效位
• 64 位包括 1 位符号位 52 位有效位
• 规格化尾数最高位总是 1，所以隐含表示，省略一位
• 阶码使用移码表示
• 全 0 +0
• 符号位 1 之后全 0 -0
• 浮点数除 0 的结果是正负无穷大，而不是一出一场
• 0 11111111 00000000000000000000000 正无穷大
• 1 11111111 00000000000000000000000 负无穷大
• Not a Number 非数 sqrt(-0.4) 0/0 使用全 1 的阶码和非 0 的尾数
• 非规格化数
  • 阶码全 0 尾数非 0

C 语言中涉及的运算

• 无符号数 逻辑左（右）移动，有符号数 算数左（右）移动
• 溢出标志 of，最高位和次高位的进位 Cn 异或 Cn-1， 当两个正数相加时，最高位不会进位，若次高位进位，则为溢出 ，当两个负数相加，最高位必然进位，若次高位不进位，则为溢出，正数加负数永远不会溢出
• 乘法指令分有符号乘和无符号乘 若只取低 n 位 不考虑溢出 则可以只使用无符号乘 由程序员自行判断是否溢出
• 乘法可以转换成加法和移位运算的组合
• 对于带符号正数 出了 -2^n / -1 = 2^n-1 会发生溢出外，其余情况都不会发生溢出
• 对于正数 对商取 floor 对于负数 对商取 ceil
• 编译器对于除数为 2 的倍数的除法运算使用移位优化，对于无符号数，带符号数正整数，移除的低位直接舍弃，对于带符号负整数，由于商取 ceil，需要现加上一个偏移量 2^k-1，然后再右移 k 位，低位截断

编译

汇编结果是一个可重定位目标文件，其中包含的是不可读的二进制代码，必须用相应的工具软件来查看其内容

生成的.o 文件可重定位的目标文件 程序中的地址尚未确定 通过链接后方可执行

磁盘驱动器

柱面号就是磁道号

层次结构存储系统

• 非易失存储器 Nonvolatile Memory 易失存储器 Volitile Memory
• SRAM 不采用地址引脚复用方式，DRAM 采用地址引脚复用方式
• 内存位宽是 64bit DDR3 采用 8 位预读，若内部核心频率为 133.25MHZ，则每秒传送的数据次数为 133.25M*8 = 1066M 次，带宽为 1066 M*8B=8.5GB/S
• 当写不命中时，有写分配法和非写分配法。采用写分配法时，需要分配一个 cache 空行，以将主存块复制到 cache，当采用非写分配法时，不将主存块分配到 cache。因此，回写策略下，一定采用写分配法，在全写策略下，两种分配方式都可采用
• 栈和堆合称堆栈，栈区从 0xc0000000 开始向低地址增长，共享库区从 0x400000000 向高地址增长，只读区从 0x08048000 开始向高地址增长。

题目是求 2019 可以由多少个两两不同的质因数组成，可以转化为 01 背包模型，将每个质因数的价值和花费等同于其数值大小。那么问题就简单变为了求 01 背包的方案数量。
代码如下
注意初始化 dp[0] =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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 3000;
int isp[maxn];
vector<int> prime;
void seive()
{
    isp[0] = isp[1] = 0;
    for (int i = 2; i < maxn; i++)
    {
        isp[i] = 1;
    }
    for (int i = 2; i < maxn; i++)
    {
        if (isp[i])
        {
            prime.push_back(i);
            for (int j = i + i; j < maxn; j += i)
            {
                isp[j] = 0;
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    freopen("data.in", "r", stdin);
    seive();
    int dp[maxn];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < prime.size(); i++)
    {
        for (int j = 2019; j >= prime[i]; j--)
        {
            dp[j] += dp[j - prime[i]];
        }
    }
    cout << dp[2019];
}

题目是求有 100 个约数的数字的最小值。有两种方法去做，一种直接暴力求每个数的约数个数，直到找到第一个约数为 100 的数。第二种用到了约数定理，首先用质因数分解的方法求出每个质因数的指数：

那么 n 的约数个数可以用以下公式求得：

很简单的乘法原理的思想，对于质因数 $ a_1 $ 可以取 0,1,2…n 一共 n+1 个，其他同理。
如何证明这样不会取得相同的因数呢？
假设两个因数

如果 $ b_1 = b_2 $ 那么有 $ a_1 * a _2 = a_4 $，显然与$a_4$是一个质数矛盾，所以不存在重复的情况。
代码如下

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int solve(int n)
{
    int factor = 2, cnt = 0;
    vector<int> a;
    while (n != 1)
    {
        if (n % factor != 0)
        {
            factor++;
            a.push_back(cnt);
            cnt = 0;
        }
        else
        {
            n = n / factor;
            cnt++;
        }
    }
    a.push_back(cnt);

    int sum = 1;
    for (int i = 0; i < a.size(); i++)
    {
        sum *= (a[i] + 1);
    }
    return sum;
}
int main()
{
    std::ios::sync_with_stdio(false);
    freopen("data.in", "r", stdin);
    int n = 1;
    while (1)
    {
        int ret = solve(n);
        // cout << ret << endl;5
        if (ret == 100)
        {
            cout << n << endl;
            break;
        }
        n++;
    }
    return 0;
}

最小生成树的算法有 Prim 和 Kruskal,首先，先说明一个结论，定义图有 n 个点，m 条边, prim 的复杂度为 O(nlogm)，kk 的复杂度为 O(mlogm)，可见 prim 更适合稠密图，而 kk 更适合稀松图。

当连通图中各边权值不相等时,最小生成树唯一;当有相等的权值时最小生成树可能不唯一。

prim 算法的思想是，首先选取一个点，加入点集，然后将该点所连的边加入边集，重复以下步骤。
选取当前边集合中权值最小的边，如果该边所连接的点不在点集中，将该边的另一个端点加入点集合，同时将该端点所连接的边加入边的集合。
当选取了 n-1 条边后，得到最小生成树。使用堆优化后的时间复杂度为 O(nlogm)。

证明，假设 prim 生成的树 T* 不是最小生成树，设最小生成树为 T，T* 中 不属于 T ，那么一定有将 加入 T，T 中形成环(此时共有 n 条边，一定存在环)，可以通过删除环上任意一条边(根据构建过程，是点所连边中权值最小的)得到更小的生成树，因此 T 不存在。

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
62
63
64

const int maxn = 1e4 + 7;
int vis[maxn];
int n, m;
struct edge
{
    int from, to, w;
    edge(int from, int to, int w)
    {
        this->from = from;
        this->to = to;
        this->w = w;
    }
    bool operator<(const edge b) const
    {
        return this->w > b.w;
    }
};
vector<edge> gra[maxn];
priority_queue<edge> pq;
int prim()
{
    int res = 0;
    int cnt = 0;
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    for (int i = 0; i < gra[1].size(); i++)
    {
        edge tmp = gra[1][i];
        pq.push(tmp);
    }
    while (cnt < n - 1 && !pq.empty())
    {
        edge top = pq.top();
        pq.pop();
        int to = top.to;
        if (!vis[to])
        {
            res += top.w;
            cnt++;
            vis[to] = 1;
            for (int i = 0; i < gra[to].size(); i++)
            {
                edge tmp = gra[to][i];
                if (!vis[tmp.to])
                {
                    pq.push(tmp);
                }
            }
        }
    }
    if (cnt != n - 1)
    {
        return -1;
    }
    else
    {
        return res;
    }
}
void addedge(int from, int to, int w)
{
    gra[from].push_back(edge(from, to, w));
    gra[to].push_back(edge(to, from, w));
}

次小生成树问题一般使用 prim 算法解决。设最小生成树的权值为 W，因为 prim 算法可以记录生成树路径，思想是在剩下的边集中尝试将每一条边 (u,v) 加入生成树中 ，此时必然可以构成一个环，此时要删除权值最大的一条边。可以用一个 max 数组记录路径 path(u,v) 上的权值最大值 max(u,v)，那么最终的答案就是 min (W + w(u,v) - max(u,v) )，max(u，v)可以在循环过程中求得。

网上的算法都是 O(V^2)的，我自己尝试了，似乎写不出堆优化的后的次小生成树写法，记录路径要用到 LCA。下面是模板的使用。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

const int maxn = 1e4 + 7;
int n, m;
int pre[maxn];
int dis[maxn];
bool vis[maxn];
bool use[maxn][maxn]; // 最小生成树使用的边
int maxv[maxn][maxn]; // u->v中边权最大值
int cost[maxn][maxn]; // u->v的花费
inline int prim(int s)
{
    memset(vis, 0, sizeof vis);
    memset(use, 0, sizeof use);
    memset(maxv, 0, sizeof maxv);
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    for (int i = 1; i <= n; i++)
        pre[i] = s;
    int res = 0;
    for (int j = 1; j <= n; ++j)
    {
        int u, minw = INF;
        for (int i = 1; i <= n; ++i)
        {
            if (!vis[i] && dis[i] < minw)
            {
                u = i, minw = dis[i];
            }
        }
        if (minw == INF)
            return -1;
        // 不连通
        res += dis[u];
        vis[u] = 1;
        use[u][pre[u]] = use[pre[u]][u] = 1;
        for (int v = 1; v <= n; ++v)
        {
            if (vis[v])
            {
                maxv[u][v] = maxv[v][u] = max(maxv[v][pre[u]], dis[u]);
            }
            if (!vis[v] && dis[v] > cost[u][v])
            {
                dis[v] = cost[u][v], pre[v] = u;
            }
        }
    }
    return res;
}
inline int smst(int s)
{
    // s:起点 ans:最小生成树的值
    int res = INF, ans = prim(s);
    if (ans == -1)
        return -1;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (cost[i][j] != INF && !use[i][j]) // i->j有边且不在最小生成数里
                res = min(res, ans + cost[i][j] - maxv[i][j]);
    return res == INF ? -1 : res;
}

int main()
{
    freopen("data.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cost[i][j] = cost[j][i] = INF;
        }
    }
    for (int i = 0; i < m; i++)
    {
        int from, to, w;
        scanf("%d%d%d", &from, &to, &w);
        cost[from][to] = min(cost[from][to], w);
        cost[to][from] = min(cost[to][from], w);
    }
    cout << smst(1);
}

Kruskal 的算法思想是，对于一个有 n 个点和 m 条边的无向图来说，先对其边按照权值按照从小到大的顺序进行排序。初始化一个并查集。每次取排好序的边集中权值最小的一条边，若这条边与已经选取的边不构成回路，那么将这条边加入到最终的生成树中，最终得到的生成树一定是最小生成树。回路的判断用并查集来实现。时间复杂度为 O(mlogm)

假设 Kruskal 算法对 n≤k 阶图适用，那么，在 k+1 阶图 G 中，我们把最短边的两个端点 a 和 b 做一个合并操作，即把 u 与 v 合为一个点 v’，把原来接在 u 和 v 的边都接到 v’上去，这样就能够得到一个 k 阶图 G’(u,v 的合并是 k+1 少一条边)，G’最小生成树 T’可以用 Kruskal 算法得到。

我们证明 T’+{}是 G 的最小生成树。

用反证法，如果 T’+{}不是最小生成树，最小生成树是 T，即 W(T)})。显然 T 应该包含，否则，可以用加入到 T 中，形成一个环，删除环上原有的任意一条边，形成一棵更小权值的生成树。而 T-{}，是 G'的生成树。所以 W(T-{})=W(T’)，也就是 W(T)=W(T’)+W()=W(T’+{})，产生了矛盾。于是假设不成立，T’+{}是 G 的最小生成树，Kruskal 算法对 k+1 阶图也适用。

由数学归纳法，Kruskal 算法得证。

算法的实现如下

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

struct edge
{
    int from, to, w;
} edges[maxn];
int cmp(edge a, edge b)
{
    return a.w < b.w;
}
int n, m;
int u[maxn];
int find(int x)
{
    return u[x] == x ? x : u[x] = find(u[x]);
}
void merge(int x, int y)
{
    u[x] = y;
}

int kk()
{
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        u[i] = i;
    }

    sort(edges, edges + m, cmp);
    for (int i = 0; i < m; i++)
    {
        int x = find(edges[i].from);
        int y = find(edges[i].to);
        if (x != y)
        {
            merge(x, y);
            res += edges[i].w;
        }
    }
    return res;
}

对于 KK 算法，求次小生成树的方法是维护一个子图集合和一个 maxw 数组，maxw 数据记录子图集之间的最大边权。开始每个点都属于一个子图。在进行并查集合并操作的时候合并子图。每次插入边的时候，更新边端点所在子图的最大边权为新加入的边的权值。显然根据 KK 算法的思想，每次加入的边的权值都是连接的两个子图中权值中最大的。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
vector<int> gra[maxn];
int maxw[5005][5005];
struct edge
{
    int from, to, w, vis;
} edges[5005];
int cmp(edge &a, edge &b)
{
    return a.w < b.w;
}
int n, m;
int u[maxn];
int find(int x)
{
    return u[x] == x ? x : u[x] = find(u[x]);
}
void merge(int x, int y)
{
    u[x] = y;
    for (int i = 0; i < gra[x].size(); i++)
    {
        gra[y].push_back(gra[x][i]);
    }
}

int kk()
{
    int res = 0;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        u[i] = i;
        gra[i].push_back(i);
    }

    sort(edges, edges + m, cmp);
    for (int i = 0; i < m; i++)
    {
        int x = find(edges[i].from);
        int y = find(edges[i].to);
        if (x != y)
        {
            for (int j = 0; j < gra[x].size(); j++)
            {
                for (int k = 0; k < gra[y].size(); k++)
                {
                    maxw[gra[x][j]][gra[y][k]] = maxw[gra[y][k]][gra[x][j]] = edges[i].w;
                }
            }
            edges[i].vis = 1;
            merge(x, y);
            cnt++;
            res += edges[i].w;
        }
    }

    if (cnt != n - 1)
    {
        return -1;
    }
    return res;
}

int seckk()
{
    int ans = INF;
    int res = kk();
    if (res == -1)
    {
        return -1;
    }
    for (int i = 0; i < m; i++)
    {
        if (!edges[i].vis)
        {
            int w = edges[i].w;
            int wmax = maxw[edges[i].from][edges[i].to];
            ans = min(ans, res + w - wmax);
        }
    }
    return ans;
}

int main()
{
    freopen("data.in", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &edges[i].from, &edges[i].to, &edges[i].w);
        edges[i].vis = 0;
    }
    int res = seckk();

    if (res == -1)
    {
        cout << "orz";
    }
    else
    {
        cout << res;
    }
}