2-28

1 算法2.28

题目：210.课程表 II(😕)

图、拓扑排序、BFS(广度优先搜索)

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例

示例1

输入: 2, [[1,0]]

输出: [0,1]

解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例2

输入: 4, [[1,0],[2,0],[3,1],[3,2]]

输出: [0,1,2,3] or [0,2,1,3]

解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。   因此，一个正确的课程顺序是  [0,1,2,3] 。另一个正确的排序是  [0,2,1,3]

说明

1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
2. 你可以假定输入的先决条件中没有重复的边。

前提知识

图、拓扑排序、DFS、BFS（深度、广度优先搜索）

分析

此题虽然根据他人代码，我也做出来了，但过程还是没理解。由于本身对图认识不够，后续还要加强练习

题解

function main() {
  const numCourses = 4
  const prerequisites = [
    [1, 0],
    [2, 0],
    [3, 1],
    [3, 2],
  ]

  console.log('[]:', findOrder(numCourses, prerequisites))
}

main()

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  let res = []

  // 计算入度和关系
  // 这里的关系是 依赖课程: [课程1，课程2]，也就是指课程1和2依赖于依赖课程
  const inDeeps = new Array(numCourses).fill(0)
  const relationship: {
    [key: number]: number[]
  } = {}
  for (let i = 0; i < prerequisites.length; ++i) {
    const value = prerequisites[i][0]
    const dep = prerequisites[i][1]

    inDeeps[value]++

    if (relationship[dep]) {
      relationship[dep].push(value)
    } else {
      relationship[dep] = [value]
    }
  }

  // 生成队列
  const queue = []
  for (let i = 0; i < inDeeps.length; ++i) {
    // 只需要入度为0的，因为这是开始条件，注意queue中放的是课程编号
    if (inDeeps[i] == 0) queue.push(i)
  }

  console.log('[queue]:', queue)
  // 开始广度优先搜索
  while (queue.length) {
    const dep = queue.shift()
    res.push(dep)

    // 后续的课程
    const courses = relationship[dep]
    for (let i = 0; courses && i < courses.length; ++i) {
      const course = courses[i]

      // 向后推进
      const depAfter = --inDeeps[course]
      if (depAfter == 0) {
        queue.push(course)
      }
    }
  }

  // 结果的数量，一定与总课程数一致
  return res.length == numCourses ? res : []
}

这是根据代码，分析的一次各个变量的状态

4, [[1,0],[2,0],[3,1],[3,2]]

inDeep:
[
  0,1,1,2
]

queue:
[
  0
]

relationship:
[
  '0': [1, 2],
  '1': [3],
  '2': [3]
]

扩展1：图、拓扑序列

图基础知识

入度：指向改点的边数

扩展2：贪心算法

贪心算法简而言之：每一步最优，则全局最优。

2 通过CSS实现 文字渐变色

span {
  background: linear-gradient(to right, red, blue);
  -webkit-background-clip: text;
  color: transparent;
}

[1] 简单说 通过CSS实现 文字渐变色 的两种方式.https://segmentfault.com/a/1190000011882933

3 通过CSS是实现 模糊效果

filter: blur(5px);

[1] filter.https://developer.mozilla.org/zh-CN/docs/Web/CSS/filter

[1] CSS3实现模糊背景的三种效果.https://blog.csdn.net/csu_passer/article/details/78406702

4 Nextjs图像优化

TODO

5 算法2.29

题目：152. 乘积最大的子数组(😕)

动态规划

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组是数组的连续子序列。

示例

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是连续子数组。

所需基础

• 动态规划

  什么是动态规划（Dynamic Programming）？动态规划的意义是什么？.https://www.zhihu.com/question/23995189

  该文章有一个关于凑硬币的问题，有三种面值（1,5,11），给定一个数量K，找出最少数量凑出K值的方式

  比如：K=15，则最少数量为3，即（5,5,5）三张5元的

分析

该题可以采用：1.暴力法 2.动态规划

• 暴力法比较好想，只是会超过时间限制

• 该题的动态规划比 扩展1：53. 最大子数组和 要难一些，主要要处理 [1,2,-3,4,-5] 这种包含多个负号的问题，详细推论见 乘积最大子数组

题解

暴力法

function maxProduct(nums: number[]): number {
  let res = -Infinity

  for (let i = 0; i < nums.length; ++i) {
    let mul = nums[i]
    res = Math.max(res, mul)

    for (let j = i + 1; j < nums.length; ++j) {
      mul *= nums[j]

      res = Math.max(res, mul)
    }
  }

  return res == -Infinity ? undefined : res
}

动态规划

function main() {
  // const nums = [2, 3, -2, 4]
  // const nums = [-2, 0, -1]
  // const nums = []
  // const nums = [-2]
  const nums = [-3, 0, 1, -2]

  // console.log('[]:', maxProduct(nums))
  console.log('[]:', maxProduct111(nums))
}

[1,5,11]
15

f(15) = min(f(15-1), f(15-5), f(15-11))
f(n) = min(f(n-1), f(n-5), f(n-11))

minF = []

minF[i] = Math.min(f)

main()

function maxProduct111(nums: number[]): number {
  const len = nums.length
  let maxF = new Array(len).fill(0)
  let minF = new Array(len).fill(0)

  maxF[0] = nums[0]
  minF[0] = nums[0]

  for (let i = 1; i < len; ++i) {
    maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(minF[i - 1] * nums[i], nums[i]))
    minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(maxF[i - 1] * nums[i], nums[i]))
  }

  let res = maxF[0]
  for (let i = 1; i < len; ++i) {
    res = Math.max(res, maxF[i])
  }

  return res
}

扩展1：53. 最大子数组和(😄)

动态规划

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

分析：可以采用 1.暴力法 2.动态规划

题解

暴力法

function maxSubArray(arr: number[]): number {
  let max = -Infinity

  for (let i = 0; i < nums.length; ++i) {
    let sum = 0
    for (let j = i; j < nums.length; ++j) {
      sum += nums[j]
      max = Math.max(max, sum)
    }
  }

  return max
}

动态规划

function main() {
  const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

  console.log('[]:', maxSubArray(arr))
}

main()

function maxSubArray(arr: number[]): number {
  let max = arr[0]
  let pre = arr[0]

  for (let i = 0; i < arr.length; ++i) {
    pre = Math.max(pre + arr[i], arr[i])
    max = Math.max(max, pre)
  }

  return max
}

6 Nextjs配置i18n-lingui

问题一：自动重定向？

表现：访问首页，会自动重定向到 /zh-TW

为什么会自动重定向？

这个在官方文档中叫做 Automatic Locale Detection （自动区域检测），会自动检测 Accept-Language 头部，然后做出对应的重定向

如何取消自动重定向？

next.config.js文件中配置 localeDetection 为false即可，其他回答见 [2]

{
  i18n: {
    locales,
      defaultLocale: sourceLocale,
        // realDefaultLocale: sourceLocale,

        // not redirect
        localeDetection: false
  }
}

问题二：next epxort 不支持i18n怎么办？

有两种解决方式：

• 只渲染默认语言的页面
• 渲染所有语言的页面

第一种：这种比较简单，首先，去掉next.config.js的 i18n 配置字段

切换语言，动态加载语言即可

第二种：详见 [3]、[4]

问题二扩展：那为什么非要用 next export 呢？

为什么不直接部署一个next的node服务呢？

在 deployment 章节中介绍了多种方式部署，其中可以通过docker部署

参考

[1] nextjs配置lingui-i18n示例.https://stackblitz.com/github/akellbl4/next.js/tree/examples/with-lingui-update/examples/with-lingui?file=lingui.config.js

[2][i18n] Prefix for default locale.https://github.com/vercel/next.js/discussions/18419

[3] i18n routes in Static Sites using NextJS.https://medium.com/schmiedeone/i18n-routes-in-static-sites-using-nextjs-b6a547477bb1

[4] i18n with next export calls getStaticProps for each defined lang, but then errors.https://github.com/vercel/next.js/issues/18318

7 Duplicate declaration "Trans"

https://github.com/lingui/js-lingui/issues/952

8 Nextjs与图像懒加载

https://blog.logrocket.com/next-js-automatic-image-optimization-next-image/

9 Support for the experimental syntax 'jsx' isn't currently enabled

愿意：没有配置预设babel

{
  "presets": [
    "next/babel"
  ],
    "plugins": [
      "macros"
    ]
}

10 导航栏跟随滚动高亮

TODO写一个示例项目出来

一些知识点：

• 1.元素的距离信息（距离窗口的位置，自身的大小信息）
• 2.浏览器滚动距离
• 3.浏览器平缓的滑动到指定锚点

核心算法，这里只涉及到 getBoundingClientRect 的使用

const { top, height } = el.getBoundingClientRect()
const distance1 = top
const distance2 = top + height

// 这里会有三种情况：
// 1.distance1和distance2都小于0，那么表示它已经在窗口上面了
// 2.distance1小于0，distance2大于0，那么表示它正在窗口中
// 3.distance1和distance2都大于0，那么表示它还在窗口下面

if (distance1 <= 0 && distance2 >= 0) {
  // 进入该元素的范围
  // 可以进行一些激活操作
  // setActive(_page)
}

扩展1：如何获取浏览器滚动的距离？

document.documentElement.scrollTop

=>> 600

扩展2：如何让浏览器平缓的滑动到指定锚点？

scrollIntoView 是元素具有的一个方法，smooth 表示平滑的滚动，其他参数见 [1]

一般搜索关键字 Ref实现导航滚动定位 就可以找到一些实现，方法使用示例：

el.scrollIntoView({
  behavior: "smooth"
})

[1] Element.scrollIntoView().https://developer.mozilla.org/zh-CN/docs/Web/API/Element/scrollIntoView

11 如何让搜索引擎收录自己的博客？

一般常用搜索引擎为：1.Google 2.Baidu

操作地址为：1.搜索资源平台 2.Google Search Console

具体操作可以参考 ¹¹¹ 和 ¹¹²

扩展1：如何检查网站收录情况？

在搜索引擎中搜索，例如：

site:https://gincool.com

12 算法3.3

题目：680.验证回文字符串 Ⅱ ( 简单😄 )

标签：双指针、贪心

附题：验证回文串

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例

示例1

输入: "aba"

输出: True

示例2

输入: "abca"

输出: True

解释: 你可以删除 c 字符。

分析

• 暴力法：首先验证原串是否为回文串，如果是则返回True，否则，枚举每一个位置空缺时候，是否为回文串。

  时间O(N^2)，空间O(1)

• 贪心法：依旧利用双指针，如果当前两个指针指向值相同，那么继续下一步，如果不相同，则认为(左指针+1)和右指针指向相同 或者 左指针和(右指针+1)指向相同，否则返回False

  时间O(N)，空间O(1)

附：贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

题解

暴力法

function validPalindrome(s: string): boolean {
  const len = s.length
  let i = 0
  let j = len - 1
  let res = true

  while (i < j) {
    if (s[i] != s[j]) {
      res = false
      break
    }

    ++i
      --j
  }

  if (res) {
    console.log('[删除位置]:', '无需删除')
    return true
  }

  for (let k = 0; k < len; ++k) {
    i = 0
    j = len - 1
    res = true

    while (i <= j) {
      if (i == k) ++i
      if (j == k) --j

      if (s[i] != s[j]) {
        res = false
        break
      }

      ++i
        --j
    }

    if (res) {
      console.log('[删除位置]:', k)
      return true
    }
  }

  return false
}

贪心法

function validPalindrome111(s: string): boolean {
  const len = s.length
  let low = 0
  let high = len - 1

  while (low < high) {
    if (s[low] == s[high]) {
      ++low;
      --high
    } else {
      return validPalindromeAssist(s, low + 1, high) || validPalindromeAssist(s, low, high - 1)
    }
  }

  return true


  function validPalindromeAssist(s: string, low: number, high: number): boolean {
    let i = low
    let j = high
    while (i < j) {
      if (s[i] != s[j]) {
        return false
      }

      ++i;
      --j
    }

    return true
  }
}

基础题1：验证回文串 ( 简单😄 )

给定一个非空字符串 s，判断是否能成为回文字符串。

解法有：

• 反转序列法：将字符串反转，如果与原串相等，则认为true

  时间O(N)，空间O(N)，空间是因为需要通过额外的数组去转化（即字符串转数组，数组再转字符串）

• 双指针法：定义两个指针，分别指向头和尾，并分别向中间必进，其过程中，如果不相等，则认为false (O(N))

  时间O(N)，空间O(1)

双指针法

function validPalindrome(s: string): boolean {
  const len = s.length
  let i = 0
  let j = len - 1
  let res = true

  while (i < j) {
    if (s[i] != s[j]) {
      res = false
      break
    }

    ++i;
      --j
  }

  return res
}

基础题2：反转数组

给定一个数组，将其元素反转

示例：

输入 arr: [1,2,3,4]

输出 arr: [4,3,2,1]

分析

• 额外数组法：声明一个数组，从后向前写入即可
• 双指针法：定义两个指针 i 和 j ，分别指向头和尾，两头逼近中间，分别交换，直至 i==j

13 实现Promise

题目：实现Promise

请利用Ts | Js，实现一个Promise，尽量根据PromiseA+规范来实现

分析

总体而言，有四个方面：

• 1.承诺有三种状态
• 2.承诺一定要有 then 方法
• 3.在调用then后，返回一个promise
• 4.promise结果解析函数

题解

代码详见 https://github.com/ginlink/js-demo/blob/main/src/02_Leetcode/033_Promise%E5%AE%9E%E7%8E%B0.ts

测试代码 https://github.com/ginlink/js-demo/blob/main/src/02_Leetcode/033_Promise%E5%AE%9E%E7%8E%B0.test.ts

14 算法3.4

题目：1371. 每个元音包含偶数次的最长子字符串 Ⅱ ( 中等😕 )

分析

• 暴力法：

  • 时间复杂度O(n^3)

• 前缀和

  前缀和特点

  • 对于一个区间，我们可以用两个前缀和的差值，得到其中某个字母的出现次数

  关于前缀和的解法，可以参考这篇文章：参考官方题解，步步引导，代码实现

  • 时间复杂度O(n)，空间复杂度O(n)

• 前缀和+状态压缩

题解

暴力法

function main() {
  const s = 'eleetminicoworoep'
  // const s = 'leetcodeisgreat'
  // const s = 'bcbcbc'

  console.log('[]:', findTheLongestSubstring(s))
}

main()

function findTheLongestSubstring(s: string): number {
  const len = s.length

  let max = ''
  let evenMap: { [key: string]: number } = {}

  for (let i = 1; i < len; ++i) {
    let current = ''
    resetMap()

    for (let j = i; j >= 0; --j) {
      current = s[j] + current

      if (evenMap[s[j]] != undefined) {
        ++evenMap[s[j]]
      }

      if (isEven() && current.length >= max.length) {
        max = current
      }
    }
  }

  return max.length

  function isEven(): boolean {
    return Object.values(evenMap).every((x) => x % 2 == 0)
  }

  function resetMap() {
    evenMap = {
      a: 0,
      e: 0,
      i: 0,
      o: 0,
      u: 0,
    }
  }
}

前缀和

enum NumType {
  EVEN = '1',
  ODD = '2',
}

class Status {
  private status: {
    [key: string]: NumType
  } = {
    a: NumType.EVEN,
    e: NumType.EVEN,
    i: NumType.EVEN,
    o: NumType.EVEN,
    u: NumType.EVEN,
  }

  invert(who: 'a' | 'e' | 'i' | 'o' | 'u') {
    this.status[who] = this.status[who] == NumType.EVEN ? NumType.ODD : NumType.EVEN
  }

  toString() {
    return Object.keys(this.status)
      .map((key) => key + this.status[key])
      .join('')
  }

  isEqual(newState: { [key: string]: NumType }) {
    const state = this.status
    const keys = Object.keys(state)

    for (let i = 0; i < keys.length; ++i) {
      if (state[i] != newState[i]) return false
    }

    return true
  }
}


function main() {
  // const s = 'eleetminicoworoep'
  // const s = 'leetcodeisgreat'
  const s = 'bcbcbc'

  console.log('[]:', findTheLongestSubstring222(s))
}

main()

function findTheLongestSubstring222(s: string): number {
  const len = s.length

  let res = 0
  const map = new Map<string, number>()
  const currStatus = new Status()

  map.set(currStatus.toString(), -1)

  for (let i = 0; i < len; ++i) {
    const char = s.charAt(i)

    if (char == 'a') {
      currStatus.invert('a')
    } else if (char == 'e') {
      currStatus.invert('e')
    } else if (char == 'i') {
      currStatus.invert('i')
    } else if (char == 'o') {
      currStatus.invert('o')
    } else if (char == 'u') {
      currStatus.invert('u')
    }

    // use status's string as key
    const currKey = currStatus.toString()

    if (map.has(currKey)) {
      res = Math.max(res, i - map.get(currKey))
    } else {
      map.set(currKey, i)
    }
  }

  return res
}

15 算法3.5

题目：5. 最长回文子串 ( 中等😕 )

给你一个字符串 s，找到 s 中最长的回文子串。

示例

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

分析

• 暴力法：枚举所有的子串，判断是否为回文串

  耗时：枚举需要O(n^2)，判断需要O(n)，所以时间复杂度为O(n^3)

• 动态规划，边缘扩散

  呈现的感觉就是，子串从中心向两边扩散

  

  详细见：最长回文子串

题解

动态规划

function longestPalindrome(s: string): string {
  const len = s.length
  // error:
  // const dep: boolean[][] = new Array(len).fill([])
  const dep: boolean[][] = new Array(len)
  let begin = 0,
      maxLen = 1

  // the substring's length is 1, so it is a palindrome
  for (let i = 0; i < len; ++i) {
    const newArr = new Array(len)
    newArr[i] = true
    dep[i] = newArr
  }

  for (let size = 2; size <= len; ++size) {
    for (let i = 0; i < len; ++i) {
      // size is [i, j]'s length
      // size = j - i + 1 ==> j = size + i -1
      const j = size + i - 1

      if (j >= len) {
        break
      }

      if (s[i] !== s[j]) {
        dep[i][j] = false
      } else {
        if (j - i + 1 <= 3) {
          dep[i][j] = true
        } else {
          dep[i][j] = dep[i + 1][j - 1]
        }
      }

      const newMaxLen = j - i + 1
      if (dep[i][j] && newMaxLen > maxLen) {
        maxLen = newMaxLen
        begin = i
      }
    }
  }

  return s.substring(begin, begin + maxLen)
}

使用

function main() {
  // const s = 'babbd'
  const s = 'cbbd'

  console.log('[]:', longestPalindrome(s))
}

main()

export {}

扩展0：根据下标计算数组的长度

const len = j - i + 1

const j = len + i - 1
const i = j - len + 1

扩展1：Js中初始化二维数组？

我想初始化一个3x3的存放boolean值的二维数组，怎么操作呢？

可能会这样写：

const len = 3

const dp: boolean[][] = new Array(len).fill(new Array(len).fill(true))

// =>> 输出
// [
//   [true, true, true],
//   [true, true, true],
//   [true, true, true],
// ]

看起来，符合预期，我尝试修改第0行第1个元素为false

dp[0][1] = false
console.log('[dp]:', dp)

// =>> 输出
// [
//   [true, false, true],
//   [true, false, true],
//   [true, false, true],
// ]

嗯？为什么第2行，第3行也变了

猜测，Array.fill 填充的是同一个数组对象，即三个数组引用地址是一样的

正确写法

const len = 3
const dp: boolean[][] = new Array(len)

for (let i = 0; i < len; ++i) {
  dp[i] = new Array(len).fill(true)
}

输出

[
  [true, true, true],
  [true, true, true],
  [true, true, true],
]

16 Vercel和Netlify的比较

Vercel 和 Netlify 都是为了简化前端代码部署的流程的一个平台

它们的差异可以参考 ¹

17 防抖和节流

项目	内容
防抖	调用函数触发冷却时间，如果在delay时间内再次被调用，则重新计时冷却时间
节流	固定时间被调用
区别	防抖是贪婪的，如果在delay时间内反复调用，那么该函数永远不会执行 而节流是开发的，固定时间调用，不管是否在delay时间内调用

题解

以下实现是伊拉克战损版，实际生产中建议用 lodash 库，lodash的防抖函数写得很复杂，边界情况处理到位，还具有 cancel、flush和pending方法，控制函数的执行，详见 debounce

防抖

function debounce(fn: () => void, wait = 50, immediate = true) {
  let timer = null

  return (...args) => {
    if (timer) {
      clearTimeout(timer)
    }
    if (!timer && immediate) {
      fn.apply(null, args)
    }

    timer = setTimeout(() => {
      // !immediate && fn.apply(null, args)
      fn.apply(null, args)
    }, wait)
  }
}

function main() {
  const fn = debounce(() => {
    console.log('[13232323233]:')
  })

  let counter = 0
  const timer = setInterval(() => {
    if (counter > 10) {
      clearInterval(timer)
    }

    ++counter
    fn()
  }, 100)
  }

main()

节流

function throttle(fn: () => void, wait = 50) {
  // let lastTime: number = -Infinity
  let lastTime: number = 0

  return function (...args) {
    const curr = new Date().getTime()

    if (curr - lastTime >= wait) {
      // apply null said that it is window object
      // fn.apply(null, args)

      // It's better to pass `this` here
      // If you use the arrow function outside, it doesn't work here
      fn.apply(this, args)
      lastTime = curr
    }
  }
  const that = this

  // const throttled = throttle(() => {
  //   console.log('[equal]:', that === this)
  //   console.log('[1秒打印一次]:')
  // }, 1000)
  const throttled = throttle(function () {
    console.log('[this]:', this)
    console.log('[equal]:', that === this)
    console.log('[1秒打印一次]:')
  }, 1000)

  setInterval(() => {
    throttled()
  }, 100)
}

main()

18 深拷贝

深拷贝实现程度不一，实现方式也有很多种

实现程度

• 能够处理对象
• 能够处理对象和数组
• 能够解决对象循环引用问题

方式：

• JSON方式

  • 只适用于拷贝基础类型，例如：string、boolean、null、number、undefined
  • 无法处理引用数据类型，例如：function, RegExp, function等
  • 应用场景：拷贝接口数据

• 递归

  一层一层判断元素类型，并进行拷贝

注意

生产中，建议使用 lodash 的 cloneDeep

题解

JSON方式

function cloneDeep1(value) {
  return JSON.parse(JSON.stringify(value))
}

递归

实现并不完整，无法拷贝函数，没有处理循环引用问题

详细请参考 deepClone

const arrayTag = '[object Array]'
const boolTag = '[object Boolean]'
const dateTag = '[object Date]'
const errorTag = '[object Error]'
const mapTag = '[object Map]'
const numberTag = '[object Number]'
const objectTag = '[object Object]'
const regexpTag = '[object RegExp]'
const setTag = '[object Set]'
const stringTag = '[object String]'
const symbolTag = '[object Symbol]'
const weakMapTag = '[object WeakMap]'

function getTag(value) {
  if (value == null) {
    return value === undefined ? '[object Undefined]' : '[object Null]'
  }
  return Object.prototype.toString.call(value)
}

function isObject(value) {
  const type = typeof value
  return value != null && (type === 'object' || type === 'function')
}

function isArray(value) {
  return Array.isArray(value)
}

function cloneDeep2(value) {
  // regard null as not object
  if (!isObject(value)) {
    return value
  }

  if (isArray(value)) {
    return value.map((x) => {
      return cloneDeep2(x)
    })
  } else {
    const tag = getTag(value)

    if (tag == regexpTag) {
      return new RegExp(value)
    } else if (tag == dateTag) {
      return new Date(value)
    } else if (tag == errorTag) {
      return new Error(value)
    } else if (tag == mapTag) {
      const newMap = new Map()
      value.forEach((subValue, key) => {
        newMap.set(key, cloneDeep2(subValue))
      })

      return newMap
    } else if (tag == setTag) {
      const newSet = new Set()
      value.forEach((subValue) => {
        newSet.add(cloneDeep2(subValue))
      })

      return newSet
    } else {
      return Object.keys(value).reduce((memo, key) => {
        memo[key] = cloneDeep2(value[key])

        return memo
      }, {})
    }
  }
}

19 算法3.6

题目：105.从前序与中序遍历序列构造二叉树 ( 中等😕 )

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例

示例1

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例2

输入: preorder = [-1], inorder = [-1]
输出: [-1]

分析

疑问：

• 前序遍历的左子树右边界如何计算？

  前序遍历和中序遍历的两个左子树的长度是一致的，所以可得：

  pIndex-1 - inLeft = x - (preLeft + 1)，即：

  x = pIndex - inLeft + preLeft

• 通过代码来看，遍历左子树时，其中序遍历左边界永远为inLeft

  相反，遍历右子树时，其中序遍历有边界永远为inRight，为什么？

题解

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const pLen = preorder.length
  const iLen = inorder.length
  const inorderMap = new Map<number, number>()
  for (let i = 0; i < iLen; ++i) {
    inorderMap.set(inorder[i], i)
  }

  return buildTreeRec(preorder, 0, pLen - 1, inorderMap, 0, iLen - 1)

  function buildTreeRec(
  preorder: number[],
   preLeft: number,
   preRight: number,
   inorderMap: Map<number, number>,
   inLeft: number,
   inRight: number
  ) {
    if (preLeft > preRight || inLeft > inRight) {
      return null
    }

    const val = preorder[preLeft]
    const root = new TreeNode(val)
    const pIndex = inorderMap.get(val)

    root.left = buildTreeRec(preorder, preLeft + 1, pIndex - inLeft + preLeft, inorderMap, inLeft, pIndex - 1)
    root.right = buildTreeRec(preorder, pIndex - inLeft + preLeft + 1, preRight, inorderMap, pIndex + 1, inRight)

    return root
  }
}

测试

function main() {
  const preorder = [3, 9, 20, 15, 7]
  const inorder = [9, 3, 15, 20, 7]

  console.log('[]:', buildTree(preorder, inorder))
}

main()

20 MobX是什么

mobx与vuex十分类似，设计理念为：任何可以从应用程序状态派生的内容都应该派生

mobx文档： MobX

redux、mobx比较：redux、mobx、concent特性大比拼, 看后生如何对局前辈

---

1. 让Google搜索到自己的博客.https://zoharandroid.github.io/2019-08-03-%E8%AE%A9%E8%B0%B7%E6%AD%8C%E6%90%9C%E7%B4%A2%E5%88%B0%E8%87%AA%E5%B7%B1%E7%9A%84%E5%8D%9A%E5%AE%A2/↩
2. 怎么样让自己的博客被谷歌和百度收录！.https://segmentfault.com/a/1190000037550362↩
3. Vercel vs. Netlify: Jamstack Deployment & Hosting Solutions Comparison↩