【2021-2】阅读笔记

Tony2/13/2021阅读笔记

#2月13号 forof

一个数据结构只要具有Symbol.iterator属性，就可以认为可遍历。

默认包含Symbol.iterator属性的有：

数组
Set
Map
类数组对象
Generator
字符串

#2月12号动态规划(DP)

#来源

labuladong(opens new window)

#知识点

动态规划问题的一般形式是求最值
求解动态规划的核心问题是穷举
动态规划的三要素：重叠的子问题、最优子结构(要求子元素之间独立)、状态转移方程（明确base case -> 明确【状态】-> 明确【选择】-> 定义dp数组/函数的含义）

#例1斐波那契数列

#递归

function fn(n: number): number {
  if (n === 1 || n === 2) {
    return 1;
  }

  return fn(n - 1) + fn(n - 2);
}

1
2
3
4
5
6
7

其中：

子问题拆分个数为O(2^n)
解决一个子问题的时间fn(n - 1) + fn(n - 2)为一个加法操作，时间为O(1)
时间复杂度为两者相乘，为O(2^n)

问题：

存在大量重复计算（重叠子问题）

#带备忘录的递归算法（自顶向下）

解决措施：一般使用一个数组充当这个备忘录（也可以使用哈希表）

function fn(n: number): number {
  if (n < 1) return 0;
  let arr: number[] = []; // 备忘录
  return helper(arr, n);
}

function helper(arr: number[], n: number): number {

  // base case
  if (n === 1 || n === 2) {
    return 1;
  }

  // 判断是否已经在备忘录中
  if (typeof arr[n] === 'number') {
    return arr[n];
  }

  arr[n] = helper(arr, n - 1) + helper(arr, n - 2);
  return arr[n];
}

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

其中：

所有子问题个数为O(n)
解决一个子问题时间为O(1)
算法的时间复杂度为两者之积，因此时间复杂度为O(n)

#动态规划的迭代算法

自底向上，建立一个DP table

function fn(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  const dp = [];
  dp[1] = 1;
  dp[2] = 1;

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

1
2
3
4
5
6
7
8
9
10
11
12
13

这里的状态转移方程可以表示为：

        {1, n = 1, 2
fn(n) = {
        {f(n - 1) + f(n - 2), n > 2

1
2
3

优化：只需要存储前两个状态

function fn(n: number): number {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;

  let prev = 1;
  let curr = 1;
  for (let i = 3; i <= n; i++) {
    let sum = prev + curr;
    prev = curr;
    curr = sum;
  }
  return curr;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

这个叫状态压缩

#凑零钱问题

题：给k中面值的硬币，面值分别是c1, c2, c3 ..., ck，每种硬币的数量无限，再给一个总金额amount，最少需要几枚硬币凑出这个金额，如果没有凑出则返回-1

base case，amount为0时返回0
确定状态——变量为目标金额amount
确定选择——所有硬币的面值
明确dp函数/数组的定义——dp(n)：返回的最少硬币数量

#递归

function coinChange(coins: number[], amount: number): number {
  let dp = (n) => {
    if (n === 0) {
      return 0;
    }

    if (n < 0) {
      return -1;
    }

    // 无穷大
    let res = Infinity;
    for (const coin of coins) {
      let subproblem = dp(n - coin);

      if (subproblem === -1) {
        continue;
      }

      res = Math.min(res, 1 + subproblem);
    }

    return res === Infinity ? -1 : res;
  }

  return dp(amount);
}

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

状态转移方程

dp(n) = 0, n = 0
      = -1, n < 0
      = min(dp(n - coin) + 1) coin∈coins, n > 0

1
2
3

其中：

子问题总数O(n^K)，每一个子问题含有一个for循环，复杂度为O(k)，总的复杂度为O(k * n ^ k)。

#备忘录

function coinChange(coins: number[], amount: number): number {
  let arr: number[] = [];

  let dp = (n: number): number => {
    if (typeof arr[n] === 'number') {
      return arr[n];
    }

    if (n === 0) {
      return 0;
    }

    if (n < 0) {
      return -1;
    }

    // 无穷大
    let res = Infinity;

    for (const coin of coins) {
      let subproblem = dp(n - coin);
      if (subproblem === -1) {
        continue;
      }

      res = Math.min(res, 1 + subproblem);
    }
    arr[n] = res === Infinity ? -1 : res;
    return arr[n];
  }

  return dp(amount);
}

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

其中：

子元素个数为n，所以数目为O(n)，子问题的时间为O(k)，所以总的时间复杂度为O(kn)

#DP的迭代法

function coinChange(coins: number[], amount: number): number {
  if (amount === 0) { return 0 };
  let dp: number[] = Array(amount + 1).fill(amount + 1);
  dp[0] = 0;

  for (let i = 0; i < amount + 1; i++) {
    for (const coin of coins) {
      if (i - coin < 0) {
        continue;
      }
      dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
    }
  }

  return dp[amount] === amount + 1 ? -1 : dp[amount];
}

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

#2月10号箭头函数

#来源

冴羽的Blob(opens new window)

#与普通函数的对比

没有this，不能用call、apply、bind改变this指向
没有arguments
不能用new进行实例化箭头函数，因为没有[[Construct]] 方法
没有new.target
没有原型
没有super
不能使用yeild命令，因此不能使用Generator函数

#优缺点

优点：简洁
缺点：函数内部依赖绑定的this就不适用箭头函数（也不算缺点，算是箭头函数不适用这种场景）

#2月9号let和const

#来源

#为什么会出现

解决ES5中var声明变量存在的变量提升问题

#let & const特点

变量不提升
重复声明报错，相同变量只允许声明一次
不绑定全局作用域（例如浏览器中声明的变量不会绑定到window对象上）

#临时死区（暂时性死区）

在没有运行声明代码时，变量会存在于临时死区中，一旦在声明变量之前使用，则报错。

console.log(typeof a);
let a = 1;

1
2

#区别

let声明的变量允许修改值，
const不允许修改变量的内存地址

#范围

{}大括号
for循环的圆括号内

Tony's Blob

Choose mode