2-18

1 MobX

一个不依赖UI 框架的状态管理器，最新版为v6

有三个概念：

observable
computed
action

[1] MobX_v6.https://zh.mobx.js.org/README.html

2 Prettier配置不生效问题

解决方案：重新设置一遍Prettier

3 一键式登录区块链：METAMASK教程

[1] 一键式登录区块链：METAMASK教程.https://zh.portaldacalheta.pt/one-click-login-with-blockchain

4 如何批量删除Docker中已停止的容器

[1] 如何批量删除Docker中已停止的容器.https://blog.csdn.net/CSDN_duomaomao/article/details/78587103

5 Eslint配置any不警告

{
  "rules": {
    "@typescript-eslint/no-explicit-any": ["off"]   
  }
}

6 Css配置Flex间距

#container > :not(style) + :not(style) {
  margin-left: 8px;
}

/* 原理：选中容器的直接儿子，并且是紧邻的兄弟节点，那么就会排除第一个 */

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 无时间限制

7 利用css变量实现主题换色

TODO

8 CSS实现渐变色边框

最佳，并且最快速的方法是包一个背景，背景渐变，上层元素设置背景（露出边缘即可）

附：如果不满足，参考[1] 中有一些其他实现方式

[1] CSS实现渐变色边框（Gradient borders）的5种方法.https://segmentfault.com/a/1190000040794056

9 算法2.22

题目：50.pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例

输入: 2.00000, 10
输出: 1024.00000

分析

方法有：1.快速幂 + 递归 2.快速幂 + 迭代，这里只采用递归

分治的思想

x * x = x²
x² * x² = x^4
x^4 * x^4 * x = x^9 // 如果为%2的奇数，则补乘一个x，
                                        // 注意计算时候是反过来，所以可以知道%2的值
x^9 * x^9 * x = x^19

详细分析见.https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/

题解

function main() {
  const x = 2
  const n = 10

  const res = myPow(x, n)

  console.log('[res]:', res)
  // [res]: 1024
}
main()

function myPow(x: number, n: number) {
  return n >= 0 ? quickMul(x, n) : 1 / quickMul(x, -n)
}

function quickMul(x: number, n: number) {
  n = Math.floor(n) // 向下取整
  
  if (n == 0) {
    return 1
  }

  const y = quickMul(x, n / 2)
  return n % 2 == 0 ? y * y : y * y * x
}

10 算法2.23

题目：155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

示例

输入:

["MinStack","push","push","push","getMin","pop","top","getMin"]
[],[-2],[0],[-3],[],[],[],[]

输出:

[null,null,null,null,-3,null,0,-2]

解释:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();  --> 返回 -3.
minStack.pop();
minStack.top();         --> 返回 0.
minStack.getMin();  --> 返回 -2.

分析

方法有：1.辅助栈法

思想为：需要两个栈，一个栈为正常栈，另一个栈为最小栈（辅助栈）。

正常栈中就进行正常push、pop、top
最小栈的主要作用是满足 常数时间内检索最小元素 ，最小栈的栈顶永远是最小的元素，所以可以直接访问栈顶元素，即为最小元素

题解

// class不具有变量提升
class MinStack {
  private readonly stack = []
  private readonly minStack = []
  // assist stack
  // only for get min element

  private len = 0

  push(e: number) {
    this.stack.push(e)

    if (this.len == 0) {
      this.minStack.push(e)
    } else {
      const oldMin = this.minStack[this.len - 1] ?? Infinity
      this.minStack.push(Math.min(e, oldMin))
    }

    ++this.len
  }
  pop() {
    if (this.len == 0) return undefined

    const e = this.stack.pop()
    this.minStack.pop()

    --this.len

    return e
  }
  top() {
    return this.stack[this.len - 1]
  }
  getMin() {
    return this.minStack[this.len - 1]
  }
}

function main() {
  const stack = new MinStack()

  stack.push(-3)

  console.log('[getMin]:', stack.getMin())
  console.log('[pop]:', stack.pop())
  console.log('[top]:', stack.top())
  console.log('[getMin]:', stack.getMin())
}

main()

11 React多种方式进行样式管理

[1] Styling in React: 4 ways to style a React app.https://blog.logrocket.com/styling-in-react-4-ways-style-react-app/

12 Emotion库

详见 [1] 中的Emotion那一小节

介绍

它分为两种工作方式：1.与框架无关 2.与React结合

第一种：与框架无关

import { css } from 'emotion';

const styles = {
  panel: {
    color: 'red',
    // ...
  }
};

class App extends Component {
  render() {
    return (
      <div className={css(styles.panel)}>
        React + Emotion rocks!
      </div>
    );
  }
}

可以看到，放到了类名这里，那它是如何工作的呢？

emotion做了两件事：1.生成一个唯一类名 2.生成css代码，并放在头部style中

// 唯一类名
<div class="css-4k75yl">
  React + Emotion rocks!
</div>

 // 生成的style标签（放在head标签中）
<style data-emotion="">
  .css-4k75yl {
    color: red;
    /* ... */
  }
</style>

第二种：与React结合

结合有什么好处呢？可以选择用styled-components创建组件，也就是说：支持两种使用方式

需要额外安装一个库

yarn add react-emotion // or preact-emotion

然后就可以创建组件了

import styled from 'react-emotion';

// 类写法（object）
const MyDiv = styled('div')({
    color: 'red',
  }
)

// or 模板字符串（template literal）
const MyDiv = styled('div')`
  color: red;
`;

class App extends Component {
  render() {
    return (
      <MyDiv>
        React + Emotion rocks!
      </MyDiv>
    );
  }
}

总结

Emotion是一个借鉴多方灵感而来的一个库，可以看到它比较多样化，可以与框架无关，也可以与React无缝结合，支持类和模板字符串写法

[1] The best React inline style libraries compared.https://blog.logrocket.com/the-best-react-inline-style-libraries-comparing-radium-aphrodite-emotion-849ef148c473/

[2] Emotion.https://github.com/emotion-js/emotion

13 一些缺乏的知识

示例见 [1]

Client-side

Google Analytics

Server-side

Service Worker
Dynamic routing
CORS
Trailing slash on all routes
Server Response caching
Sitemap & robots.txt

Configuration

HmR with static type-checking
Easy-to-remember import structure
Git Commit linting
Code linting
Code style & formatting
Bundle size checking
Container ready

DevOps

Continuous Integration
Semantic versioning
Automated code review and changelog

[1] MoNA Starter Kit.https://github.com/Kandelborg/MoNA-starter-kit

14 简历建议

技能，可以采用图标的方式（参考 [1] ）
https://alexbeciana.com/![image-20220223174014128](https://cdn.gincool.com//img/image-20220223174014128.png)
项目，可以采用这种，最好加一个图片更好
https://tom-young-portfolio.vercel.app/#work
经验，可以采用时间线的方式
https://aziz-chebbi-54214.web.app/
可以加入3D内容

15 Lighthouse

Lighthouse可以审查网站的性能，一般用chrome插件，插件见 [1]

[1] https://chrome.google.com/webstore/detail/lighthouse/blipmdconlkpinefehnmjammfjpmpbjk

16 Nestjs加载.env文件

import { config as load } from 'dotenv';

// 加载.env文件
load()

// 加载指定文件
load({path: './development.env'})

17 算法2.24

题目：102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

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

示例 3：

输入：root = []
输出：[]

分析

层序遍历采用BFS（Breadth-first search）进行，算法为维护队列算法，具体参考 [1]

题解

function levelOrder(root: TreeNode | null) {
  if (root == null) return []

  const queue: (TreeNode | null)[] = []
  const res: number[][] = []

  queue.unshift(root)

  while (queue.length > 0) {
    const len = queue.length

    const layer: number[] = []
    for (let i = 0; i < len; ++i) {
      const el = queue.pop()
      layer.push(el.val)

      if (el.left != null) {
        queue.unshift(el.left)
      }
      if (el.right != null) {
        queue.unshift(el.right)
      }
    }

    res.push(layer)
  }

  return res
}

扩展问题1：DFS和BFS的区别？

Deep-first Search and Breadth-first search

详见 [1]

[1] BFS 的使用场景总结：层序遍历、最短路径问题.https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/

[2] LeetCode 例题精讲 | 12 岛屿问题：网格结构中的 DFS.https://mp.weixin.qq.com/s?__biz=MzA5ODk3ODA4OQ==&mid=2648167208&idx=1&sn=d8118c7c0e0f57ea2bdd8aa4d6ac7ab7&chksm=88aa236ebfddaa78a6183cf6dcf88f82c5ff5efb7f5c55d6844d9104b307862869eb9032bd1f&token=1064083695&lang=zh_CN#rd

扩展问题2：数组转二叉树？

示例

输入：root = [3, 9, 20, null, null, 15, 7]
输出：
TreeNode111 {
  left: TreeNode111 { left: null, right: null, val: 9 },
  right: TreeNode111 {
    left: TreeNode111 { left: null, right: null, val: 15 },
    right: TreeNode111 { left: null, right: null, val: 7 },
    val: 20
  },
  val: 3
}

分析

数组转二叉树有两种情况：

未优化的数组

[2,null,4,null,null,9,8,null,null,null,null,null,null,4]

优化的数组
```
[2,null,4,9,8,null,null,4]
```

题解

优化数组的版本

// Optimize array to binary tree
function arr2Tree(arr: (number | null)[]) {
  if (arr[0] == null) return null

  const queue: (TreeNode | null)[] = []
  const root = new TreeNode111(arr[0])

  queue.unshift(root)

  let isLeft = true
  for (let i = 1; i < arr.length; ++i) {
    const peekEl = queue[queue.length - 1]

    if (isLeft) {
      if (arr[i] != null) {
        peekEl.left = new TreeNode111(arr[i])
        queue.unshift(peekEl.left)
      }
      isLeft = false
    } else {
      if (arr[i] != null) {
        peekEl.right = new TreeNode111(arr[i])
        queue.unshift(peekEl.right)
      }

      queue.pop()
      isLeft = true
    }
  }

  return root
}

没有优化数组的版本

function arr2tree2(arr: (number | null)[]) {
  return createTreeNode(arr, 1)
}
function createTreeNode(arr: (number | null)[], index: number): TreeNode111 | null {
  if (arr[index - 1] == null) {
    return null
  }

  if (index > arr.length) {
    return null
  const node = new TreeNode111(arr[index - 1])

  node.left = createTreeNode(arr, 2 * index)
  node.right = createTreeNode(arr, 2 * index + 1)

  return node
}

[1] Java 一维数组转换二叉树.https://leetcode-cn.com/circle/article/htJ97s/

18 Uncaught TypeError: Cannot read property 'add' of undefined

条件：在使用 react-helmet-async 出现上述报错

原因：没有用HelmetProvider包裹，包裹即可

<HelmetProvider context={context}>
  <App />
</HelmetProvider>

[1] Uncaught TypeError: Cannot read property 'add' of undefined.https://github.com/staylor/react-helmet-async/issues/1

19 2.25算法

😄 😕 😟

题目：136. 只出现一次的数字 [简单😄 ]

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例

示例1

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

示例2

输入: [4,1,2,1,2]
输出: 4

分析

比较常规想到的解法：

[哈希表] 遍历数组，用一个哈希表存每个数出现的次数，再遍历一遍，拿到次数为1的就是出现一次的元素
[集合] 遍历数组，用一个集合存数据，规则为：1.如果该元素存在，则删除 2.如果不存在，则加入，那么最后剩余的元素，就是出现一次的元素
[求和] 先求数组之和s1，再遍历数组，用一个集合存所有元素，再将集合元素求和s2，那么s2 - s1就是出现一次的元素（该解法前提为元素是纯数字）

以上三个方法虽然时间复杂度满足，但都是需要 O(n) 的辅助空间

这里可以采用 位运算 ，推理过程：

首先需要知道位运算三个性质：

一个数和0作位运算，结果为该数
一个数和自身作位运算，结果为0
满足交换律和结合律：
即 a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b

假设有m个元素出现两次，1个元素出现一次，那么共有2m+1个元素，这2m+1个元素异或结果为：

(a1⊕a1)⊕(a2⊕a2) ... ⊕((m-1)⊕(m-1))⊕(m+1) = m+1

m+1就是出现一次的元素

题解

function main() {
  // const arr = [2, 2, 1]
  const arr = [4, 1, 2, 1, 2]
  console.log('[singleNumber]:', singleNumber(arr))
}

main()

function singleNumber(arr: number[]): number {
  let res = 0
  for (let i = 0; i < arr.length; ++i) {
    res ^= arr[i]
  }

  return res
}

20 算法2.26

题目：560. 和为 K 的子数组 (😕)

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

说明

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

示例

示例1

输入: nums = [1,1,1], k = 2

[1,1], [1,1]
输出: 2

示例2

输入：nums = [1,2,3], k = 3

[1,2], [3]
输出：2

分析

该题肯定不能用滑动窗口，因为窗口是固定的，不符合该题

解法有：1暴力法 2

题解

1.暴力法，这里采用的正向子串求法，也有反向子串的解法，复杂度都是O(n^2)

function main() {
  // const nums = [1, 1, 1]
  const nums = [1, 2, 3]
  const k = 3

  console.log('[]:', subarraySum(nums, k))
}

main()

function subarraySum(nums: number[], k: number): number {
  let res = 0
  const len = nums.length

  for (let left = 0; left < len; ++left) {
    let sum = 0
    for (let right = left; right < len; ++right) {
      sum += nums[right]

      if (sum === k) {
        ++res
      }

      // can not continue, because the next element maybe 0 or negative number
      // continue
      // } else if (sum > k) {
      //   continue
      // }
    }
  }

  return res
}

2.前缀和法（含哈希优化）

这里最好看视频图解，https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/

但要注意，先判断是否在map中，之后再map.set

function subarraySum2(nums: number[], k: number): number {
  let count = 0
  let pre = 0
  const len = nums.length
  const map = new Map<number, number>()

  map.set(pre, 1)

  for (let i = 0; i < len; ++i) {
    pre += nums[i]

    // console.log('[map]:', map)
    // console.log('[pre]:', pre)

    // map's elment is [j...i-1]
    // so it must be ahead of map.set
    let exist0 = map.get(pre - k)
    if (exist0) {
      count += exist0
    }

    // maintain the pre map
    let exist1 = map.get(pre)
    if (exist1) {
      map.set(pre, ++exist1)
    } else {
      map.set(pre, 1)
    }
  }

  return count
}

扩展1：滑动窗口算法

01_滑动窗口

一般求解最大和、数组/字符串的子元素问题

示例：给定一个整数数组，计算长度为 'k' 的连续子数组的最大总和。

输入: [100,200,300,400]

输出: 700

题解

function main() {
  const arr = [100, 200, 300, 400, 500, 100]
  const k = 2

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

main()

function maxSum(arr: number[], k: number): number {
  let maxSum = 0
  const len = arr.length

  // 边界条件
  if (len < k) return -1

  // 根据窗口大小，初步计算最大值
  for (let i = 0; i < k; ++i) {
    maxSum += arr[i]
  }

  // 挪动窗口，并尝试更新最大值
  for (let i = k; i < len; ++i) {
    const sum = maxSum + arr[i] - arr[i - k]
    maxSum = Math.max(maxSum, sum)
  }

  return maxSum
}

扩展2：动态规划算法

关于动态规划，可以参考 [1]

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

这里上一个简单的示例，题目

给定1,5,11三种面值，请给出凑出15元的最小组合方式

题解

function main() {
  const coinFace = [1, 4, 11]
  const w = 15

  console.log('[]:', coinWaysNum(coinFace, w))
}

main()

function coinWaysNum(coinFace: number[], w: number): number {
  const fn = [0]

  for (let i = 1; i <= w; ++i) {
    let cost = Infinity

    for (let j = 0; j < coinFace.length; ++j) {
      if (i - coinFace[j] >= 0) cost = Math.min(cost, fn[i - coinFace[j]] + 1)
    }
    console.log(`[cost${i}]:`, cost)
    fn[i] = cost
  }

  return fn[w]
}

21 算法2.27

题目：25. K 个一组翻转链表 (😟)

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例

示例1

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明

你的算法只能使用常数的额外空间。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

分析

这个题难度较大，有时间再处理，今天先练习一个简单的题 扩展1：206. 反转链表

LeetCode题解见：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/k-ge-yi-zu-fan-zhuan-lian-biao-by-leetcode-solutio/

题解

TODO

扩展1：206. 反转链表 (😄)

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

分析

该题有两种解法，迭代法和递归法

迭代的时候有两个要点，1.向后推进 2.缓存下一个节点（否则会丢失后面的链）

递归可以模拟出栈的效果，所以操作的时候，就直接拿到链表尾巴了，而在本次上下文中又有当前节点信息，所以只需要操作让节点

详细见：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/

题解

1.迭代法时间O(n)，空间O(1)

function reverseList1(head: ListNode): ListNode {
  // [1,2,3,4,5]
  let prev: ListNode | undefined
  let curr = head

  while (curr) {
    // cache
    const next = curr.next

    // move pointer
    curr.next = prev
    prev = curr
    curr = next
  }

  return prev
}

2.递归法时间O(n)，空间O(n)

function reverseList2(head: ListNode): ListNode {
  // [1,2,3,4,5]
  if (!head || !head.next) {
    // the !head condition only for initial head value is undefined
    return head
  }

  const newHead = reverseList2(head.next)
  head.next.next = head
  head.next = undefined // only for the tail node
  return newHead
}

1 MobX​

2 Prettier配置不生效问题​

3 一键式登录区块链：METAMASK教程​

4 如何批量删除Docker中已停止的容器​

5 Eslint配置any不警告​

6 Css配置Flex间距​

7 利用css变量实现主题换色​

8 CSS实现渐变色边框​

9 算法2.22​

题目：50.pow(x, n)​

示例​

分析​

题解​

10 算法2.23​

题目：155. 最小栈​

示例​

分析​

题解​

11 React多种方式进行样式管理​

12 Emotion库​

介绍​

第一种：与框架无关​

第二种：与React结合​

总结​

13 一些缺乏的知识​

Client-side​

Server-side​

Configuration​

DevOps​

14 简历建议​

15 Lighthouse​

16 Nestjs加载.env文件​

17 算法2.24​

题目：102. 二叉树的层序遍历​

示例​

分析​

题解​

扩展问题1：DFS和BFS的区别？​

扩展问题2：数组转二叉树？​

示例​

分析​

题解​

18 Uncaught TypeError: Cannot read property 'add' of undefined​

19 2.25算法​

题目：136. 只出现一次的数字 [简单😄 ]​

说明​

示例​

分析​

题解​

20 算法2.26​

题目：560. 和为 K 的子数组 (😕)​

说明​

示例​

分析​

题解​

扩展1：滑动窗口算法​

扩展2：动态规划算法​

21 算法2.27​

题目：25. K 个一组翻转链表 (😟)​

示例​

说明​

分析​

题解​

扩展1：206. 反转链表 (😄)​

示例1​

分析​

题解​