Giter VIP home page Giter VIP logo

markdown_blogs's Introduction

Hi, I'm 阿星 (A-Star)

  • 🔭 I’m currently in HangZhou, China
  • 🌱 I’m currently working on FE at Bytedance.

Links

AI技术人的学习资料.md

Visitors

markdown_blogs's People

Contributors

55utah avatar

Watchers

 avatar

markdown_blogs's Issues

2021-02-22 学习

  1. Promise的三个常用方法
    说明
Promise.all([promise1, promise2])
所有promise都fulfilled才会resolve,返回对应的promise结果的数组,否则reject第一个rejected的promise的数据.

Promise.allSettled([promise1, promise2])
所有promise状态变化后resolve,返回对应的promise结果的数组。

Promise.race([promise1, promise2]) 
只要有一个promise状态改变,就返回对应promise结果
  1. optional chaining AND Nullish coalescing

optional chaining 可选链操作符

  (1)
  const a = {}
  console.log(a.b?.c) // undefined
  a.b?.()  // undefined
 
  在属性或者函数执行上,可避免报错,通过undefined检测属性和函数是否存在。
 
 (2)当使用方括号与属性名的形式来访问属性时,你也可以使用可选链操作符;可以用来访问数组;可选链不能赋值;
 let nestedProp = obj?.['prop' + 'Name'];
 const = arr?.[42];
 
 (3)连用可选链操作符
  可以连续使用可选链读取多层嵌套结构:
  console.log(a?.b?.c?.d?.f) // undefined
  
  (4)另有 Nullish coalescing 空值合并操作符 ??
   - 空值合并操作符(??)是一个逻辑操作符,当左侧的操作数为 null 或者 undefined 时,返回其右侧操作数,否则返回左侧操作数。
   - 与 || 不同,当为''或0时,也会触发,但是??只在null或者undefined触发。
   - 空值合并操作符可以在使用可选链时设置一个默认值。空值合并操作符针对 undefined 与 null 这两个值,可选链式操作符(?.) 也是如此。
   - 在这访问属性可能为 undefined 与 null 的对象时,可选链式操作符非常有用。
   
   console.log(a?.b?.c ?? 'hello')
   
  1. 其他

发展情况相关

Node 后端框架

目前 Next.js 是开发服务端应用的首选,Hulu,Docker,Netflix 都在用 Next.js

桌面或原生应用

用 JS 编写桌面端应用,最好的框架绝对是 Electron;
但是移动端应用不只React Native; 目前Capacitor也是非常推荐。

  1. 一个V8特性
try catch 内的代码无法被V8编译优化, 最好是提出来作为一个单独函数。
const run = () => {}
try{
   run();
} catch(){}

webpack-chain使用体验,url-loader体验

webpack-chain 是一个链式API用于创建和修改webpack配置。

// chain就是webpack-chain实例对象

chain.module
            .rule('cdnLoader')
            .test(/\.(.+)$/i) // 匹配public文件夹下任意文件
            .include.add(resolve('public')) // 必须限制只针对与src同级的public生效
            .end()
            .use('url-loader')
            .loader('url-loader')
            .options({
              limit: true, // 强制使用generator
              generator: (content, mimetype, encoding, resourcePath) => {
                const isProd = process.env.NODE_ENV === 'production'
                const relativePath = relative(resolve('public'), resourcePath)
                // 相对路径,如 /public/dir/test1.jpg 结果是 'dir/test1.jpg'
                console.log({
                  relativePath,
                  mimetype,
                  encoding,
                  resourcePath,
                  isProd,
                }) // 打包期间可以看到日志,表示执行成功
                const cdnHost =
                  process.env.CUSTOM_PUBLIC_CDN_HOST
                return isProd
                  ? cdnHost + '/' + relativePath
                  : `data:${mimetype}${
                      encoding ? `;${encoding}` : ''
                    },${content.toString(encoding)}`
                // 调试时,一律使用base64,build时NODE_ENV=production,则使用链接
              },
            })
            .end()
            .enforce('post') // 强制最后执行

Array.prototype.some方法重认识

1.接受一个返回boolean值的函数,如果有一个返回true则some方法返回true,否则false
2.空数组使用,返回false
3. 遍历时,如果找到了true值,就立即返回,不再向下计算了。

[1,2,3,4].some(p => {
	console.log(p)
	return p > 1
})
// 1
// 2
// true

HTTP缓存学习

参考:
https://segmentfault.com/a/1190000021716418
https://juejin.cn/post/6907592506779631623

前提:http缓存策略,是client/server共同控制,client在header增加cache-control决定是否走缓存,server在响应头加cache-control等字段来告知客户端是否缓存数据;缓存策略分为“强缓存”和“协商缓存”;
相关字段:

  • Expires
  • Cache-Control
  • last-Modified
  • Etag

服务端缓存控制

  1. Expires
    server返回header,表示失效绝对时间,http1.0方案,现在基本使用Cache-Control代替了;
  2. Cache-Control (最重要的规则)
  • max-age: 3000:单位ms,相对时间,表示缓存3s后失效;
  • no-store: 不允许缓存;
  • no-cache: 指允许缓存,但使用前先去服务端验证是否过期,没过期使用缓存;
  • public: 可以被任何对象缓存;
  • must-revalidate: 允许缓存,如果缓存不过期的话,先使用缓存,过期则去服务端请求;
    -... 还有一些值

比如:Cache-Control: no-cache; max-age=31536000
表示允许缓存,有效期365天,每次使用缓存前需要先去服务端验证是否过期;

客户端缓存控制

  1. F5刷新,页面http请求添加 Cache-Control:max-age:0,这样就不走缓存,直接去服务端读取;
  2. 强制刷新
    页面http请求会添加 Cache-Control:no-cache ,此时会去server验证资源是否更新,如果未更新,返回304,使用缓存;
    (状态码 304,表示客户端直接使用缓存)
  3. 浏览器前进后退
    页面http头中不会有 Cache-Control字段,表示检查缓存,使用之前的资源,不请求server;

如何去server验证资源是否变化

两组header头来完成验证逻辑,通过Last-Modified / if-Modified-Since,或者Etag/If-None-Match(优先级高于Last-Modified)来判断;

  1. Last-Modified / if-Modified-Since
    server响应时,返回 Last-Modified ,值是最后修改时间,浏览器下次请求会传if-Modified-Since请求头,值为上次收到的Last-Modified的值,server对比,未改变就返回304;
  2. Etag/If-None-Match
    server响应时,返回 Etag,值是资源的hash标识,client再次请求带上If-None-Match,值是这个Etag的值,server比对是否一致,一致就返回304,使用缓存;

一致性hash算法

一致性hash

    一致性Hash是一种特殊的Hash算法,由于其均衡性、持久性的映射特点,广泛应用于负载均
衡领域,如nginx和memcached都采用了一致性Hash作为集群负载均衡的方案。
    先构造一个长度为2^32的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值
(其分布为[0, 2^32-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到
其Hash值(其分布也为[0, 2^32-1]),接着在Hash环上顺时针查找距离这个Key值的Hash值
最近的服务器节点,完成Key到服务器的映射查找。

参考文章

https://www.cnblogs.com/xrq730/p/5186728.html

webpack自定义loader

  1. 简单例子

import { loader } from 'webpack';
import path from 'path';

export default function svgCheckLoader(this: loader.LoaderContext, content: string): string {
  
  // 可以在this内读取到上下文一些信息
  const { resourcePath = '' } = this
  console.log(resourcePath, svgCheckerData.files.length)
  // 这里转换,然后返回转换后的内容
  return content;
}

  1. pitch + inline loader
import { getOptions } from 'loader-utils';
import { loader } from 'webpack';

function cdnFileLoader(): string {
  return '';
}

function cdnFileLoaderPitch(this: loader.LoaderContext): string {
  const options = getOptions(this);

  const loaderOptions = Object.assign(
    {
      name: '[path][name].[ext]',
      outputPath: '../output',
      publicPath: '/',
      context: process.cwd(),
    },
    options,
  );

  const queryStr = Object.entries(loaderOptions || {})
    .map(([key, value]) => {
      return `${key}=${value}`;
    })
    .join('&');

  const returnContent = `
    import content from '!!file-loader?${queryStr}!${this.resourcePath}';

    export default content;
  `;

  return returnContent;
}

export default cdnFileLoader;

export { cdnFileLoaderPitch as pitch };

参考 https://zhuanlan.zhihu.com/p/360421184
pitch改变执行顺序,inline loader可以阻止部分loader执行。

检测js文件是否包含es6语法的实现

摸索了一个检测实现,可以检测es6语法,不检测es6 API

/* eslint-disable semi */
import { parse } from '@babel/parser'
import traverse, { NodePath } from '@babel/traverse'

const checkMap = {
  ArrowFunctionExpression: '箭头函数',
  VariableDeclaration: 'const、let变量',
  AwaitExpression: 'await表达式',
  YieldExpression: 'Yield表达式',
  ClassDeclaration: 'class定义',
  AsyncFunction: 'async函数',
  TemplateElement: '模版字符串',
  SpreadElement: '拓展运算符',
  RestElement: 'rest元素',
  ForOfStatement: 'for of遍历方式',
  ObjectMethod: "对象方法, getter, setter",
}

type CheckType = keyof typeof checkMap

interface CheckBin {
  type: CheckType
  name: string
  kind?: string
  code: string
  pos: number
}

interface Options {
  /** 最多统计几个结果 默认3 */
  limit?: number
  /** 代码片段长度限制 默认200 */
  codeFrgmentSize?: number
}

/**
 * 检测es6语法(注意,这边只检测语法,不检测es6新的API,如Set、Map、Promise、Object.assign、Array.from等)
 * 支持如下常用的es6语法:
 * 箭头函数
 * const、let
 * async、await
 * yield表达式
 * class定义
 * 模版字符串
 * ...拓展运算符
 * ...rest参数等rest元素
 * for of遍历方式
 * 对象方法, getter, setter
 *
 */

const esChecker = (code: string, options?: Options): CheckBin[] => {
  const { limit = 3, codeFrgmentSize = 200 } = options || {}

  const result: CheckBin[] = []

  const report = (params: { type: CheckType; kind?: string; n: NodePath }) => {
    if (result.length >= limit) return
    const { type, kind = '', n } = params
    const node = n.node
    const start = node.start
    const end = node.end
    const content =
      typeof start === 'number' && typeof end === 'number'
        ? end - start <= codeFrgmentSize
          ? code.slice(start, end)
          : code.slice(start, start + codeFrgmentSize)
        : ''

    result.push({
      type,
      name: checkMap[type],
      kind,
      code: content,
      pos: typeof start === 'number' ? start : -1,
    })
  }

  const ast = parse(code)

  traverse(ast, {
    ArrowFunctionExpression: (n) => {
      report({ type: 'ArrowFunctionExpression', n })
    },
    VariableDeclaration: (nodePath) => {
      const kind = nodePath.node.kind
      if (kind === 'const' || kind === 'let') {
        report({ type: 'VariableDeclaration', kind, n: nodePath })
      }
    },
    AwaitExpression: (n) => report({ type: 'AwaitExpression', n }),
    YieldExpression: (n) => report({ type: 'YieldExpression', n }),
    ClassDeclaration: (n) => report({ type: 'ClassDeclaration', n }),
    FunctionDeclaration: (nodePath) => {
      const async = nodePath.node.async
      if (async) report({ type: 'AsyncFunction', n: nodePath })
    },
    SpreadElement: (n) => report({ type: 'SpreadElement', n }),
    RestElement: (n) => report({ type: 'RestElement', n }),
    ForOfStatement: (n) => report({ type: 'ForOfStatement', n }),
    TemplateElement: (n) => report({ type: 'TemplateElement', n }),
    ObjectMethod: (n) => {
      const kind = n.node.kind;
      const async = n.node.async;
      report({ type: "ObjectMethod", kind, n });
      if (async) report({ type: "AsyncFunction", n });
    },
  })
  return result
}

/*

https://github.com/babel/babylon/blob/master/ast/spec.md
https://babeljs.io/docs/en/babel-types

  interface VariableDeclaration <: Declaration {
    type: "VariableDeclaration";
    declarations: [ VariableDeclarator ];
    kind: "var" | "let" | "const";
  }

  Expressions:
  interface Super <: Node {
      type: "Super";
  }
  interface ArrowFunctionExpression <: Function, Expression {
    type: "ArrowFunctionExpression";
    body: BlockStatement | Expression;
    expression: boolean;
  }
  interface YieldExpression <: Expression {
    type: "YieldExpression";
    argument: Expression | null;
    delegate: boolean;
  }
  interface AwaitExpression <: Expression {
    type: "AwaitExpression";
    argument: Expression | null;
  }
  interface Function <: Node {
    id: Identifier | null;
    params: [ Pattern ];
    body: BlockStatement;
    generator: boolean;
    async: boolean;
  }

  interface SpreadElement <: Node {
    type: "SpreadElement";
    argument: Expression;
  }
  interface RestElement <: Pattern {
    type: "RestElement";
    argument: Pattern;
  }
  interface Class <: Node {
    id: Identifier | null;
    superClass: Expression | null;
    body: ClassBody;
    decorators: [ Decorator ];
  }
  // es6对象方法语法、getter、setter
  // 即 const p = { get hello() { return 0 } }
  interface ObjectMethod <: ObjectMember, Function {
    type: "ObjectMethod";
    kind: "get" | "set" | "method";
  }

*/

vscode调试技巧

1. npm命令

// 调试node, 执行npm命名
// 在项目.vscode文件夹下添加 launch.json 设置如下配置
{
  "version": "0.2.0",
  "configurations": [
    {
      "type": "node",
      "request": "launch",
      "name": "CLI debug",
      // 这里是项目地址,也就是package.json所在文件夹绝对路径
      "cwd": "/Users/55utah/workspace/reportx12/reportx",
      // 指定执行npm命令
      "runtimeExecutable": "npm",
      // 这里指执行 npm run dev:online命令
      "runtimeArgs": [
        "run",
        "dev:online"
      ]
    }
  ]
}

会在DEBUG CONSOLE内输出调试代码,并且console输出的对象都是可以展开的。

2. 非npm命令使用program属性

{
  "version": "0.2.0",
  "configurations": [
    {
      "type": "node",
      "request": "launch",
      "name": "CLI debug",
      // 这里是项目地址
      "cwd": "/Users/55utah/workspace/reportx12/reportx",
      // 这里面是脚本路径
      "program": "xxx/node_modules/.bin/taro",
      // 给脚本传的参数,实际执行taro build --type
      "args": [
          "build",
          "--type"
      ],
    }
  ]
}

vscode调试命令对workspace支持比较差,需要单独项目的vscode窗口才行;
执行成功后,会在Debug Console窗口输出debug代码,这里的输出与chrome devtools功能接近;
可以展开对象,查看链接文件等;
参考: node调试技巧:https://zhuanlan.zhihu.com/p/338287139

2021小知识点汇总

  1. iframe的srcdoc属性
const iframe = document.createElement("iframe");
iframe.srcdoc = `<!DOCTYPE html><p>Hello World!</p>`;
document.body.appendChild(iframe);

srcdoc属性支持传入html内容,让iframe直接渲染这些html文档;

模块/系统 API设计**

大佬的**

  • 明确问题
  • 解决问题的整体思路(如沙盒化)
  • 在该思路下,为每个问题拆解出的解决方法
    -输入管控
    • 输入A管控
    • 输入B管控
      -输出管控
      ....
  • 同类型的方法进行聚合/组合/抽象出统一的行为
  • 方法聚合成模块
  • 模块聚合成层级

    归纳出模块和层级后,再回过头来为他们定性,描述他们的职责和行为

思路分析

思路整体层层递进,明确了抽象组合如何使用到设计中,并说明了设计思路的核心,值得反复学习!

【拾遗】useEffect完整机制

机制

  1. 依赖为空数组时,只会在组件初始化时执行,return回调在组件卸载时执行,其余时间不执行;
  2. 无依赖参数时,每次组件渲染都会执行,执行下一个 effect 之前,上一个 effect 就已被清除,清除时执行return回调;
  3. 有依赖时,在组件初始化时执行一次、每次依赖变化清除上一个effect并执行新的effect一次;
  4. 上述情况,都会在初始化时执行一次,组件卸载时执行一次return回调;
  5. 多个useEffect时,会从上到下按注册顺序依次执行,return回调也是这个顺序;

例子

const c = (n) => console.warn(n)

useEffect(() => {
   c(1) 
   return () => { c(2) } 
}, [])

useEffect(() => {
    c(3)
    return () => { c(4) }
}, [props.show])

// 初始化时
1
3
// props.show变化
4
3
// 组件卸载
2
4

yyx关于react最大优点的理解

React 的精髓有两块:

  1. 函数式的视图渲染思维,UI = f(state)。但是由于 DOM 的慢,需要用 Virtual DOM 来解决性能问题,用 JSX 来解决 Virtual DOM 的书写语法问题。
  2. 组件能够声明式地进行嵌套组构,像搭积木一样搭出整个应用。

vscode如何调试项目

vscode调试技巧

node调试技巧:https://zhuanlan.zhihu.com/p/338287139

学到如何使用vscode调试项目:

// 调试node, 执行npm命名
// 在项目.vscode文件夹下添加 launch.json 设置如下配置
{
  "version": "0.2.0",
  "configurations": [
    {
      "type": "node",
      "request": "launch",
      "name": "CLI debug",
      // 这里是项目地址
      "cwd": "/Users/55utah/workspace/reportx/reportx_taro3/reportx",
      // 指定执行npm命令
      "runtimeExecutable": "npm",
      // 这里指执行 npm run dev:online命令
      "runtimeArgs": [
        "run",
        "dev:online"
      ]
    }
  ]
}

非npm命令使用program属性

{
  "version": "0.2.0",
  "configurations": [
    {
      "type": "node",
      "request": "launch",
      "name": "CLI debug",
      // 这里是项目地址
      "cwd": "/Users/55utah/workspace/reportx/reportx_taro3/reportx",
      // 这里面是脚本路径
      "program": "xxx/node_modules/.bin/taro",
      // 给脚本传的参数,实际执行taro build --type
      "args": [
          "build",
          "--type"
      ],
    }
  ]
}

注意事项:

  • vscode调试命令对workspace支持比较差,需要单独项目的vscode窗口才行;
  • 执行成功后,会在Debug Console窗口输出debug代码,这里的输出与chrome devtools功能接近;
    可以展开对象,查看链接文件等;

CSS 实现多行文本“展开收起”

参考地址:
CSS 实现多行文本“展开收起”
实现关键方法:

// 利用浮动把按钮加在又下角 && 利用遮挡方式支持未超出时,不显示按钮;
// 省略号是在按钮前伪元素实现的。
<html>
  <header>
    <style>
      .wrapper {
        display: flex;
        margin: 50px auto;
        width: 80%;
        overflow: hidden;
      }
      .text {
        overflow: hidden;
        text-overflow: ellipsis;
        text-align: justify;
        position: relative;
        line-height: 1.5;
        font-size: 20px;
        max-height: 4.5em;
      }
      .text::before {
        content: '';
        width: 0;
        height: 100%;
        margin-bottom: -24px;
        float: right;
      }
      .text::after {
        content: '';
        width: 100%;
        height: 100%;
        position: absolute;
        background: #fff;
      }
      .btn {
        float: right;
        clear: both;
        width: 40px;
        height: 20px;
        position: relative;
        margin-left: 20px;

        font-size: 14px;
        background-color: blue;
        color: white;
        text-align: center;
        border-radius: 4px;
      }
      .btn::before{
        content: '...';
        position: absolute;
        left: -5px;
        color: #333;
        transform: translateX(-100%)
      }
    </style>
  </header>
  <body>
    <div class='wrapper'>
    <div class="text">
    <label class="btn">展开</label>
    浮动元素是如何定位的
正如我们前面提到的那样,当一个元素浮动之后,它会被移出正常的文档流,然后向左或者向右平移,一直平移直到碰到了所处的容器的边框,或者碰到另外一个浮动的元素。
在下面的图片中,有三个红色的正方形。其中有两个向左浮动,一个向右浮动。要注意到第二个向左浮动的正方形被放在第一个向左浮动的正方形的右边。如果还有更多的正方形。
  </div>
  </div>
  </body>
</html>


宽度较大,未超出时:
image
宽度较小,超出三行,出现省略号:
image

复原三阶魔方过程记录

记录下复原三阶魔方的过程

白色为顶,黄色为底,从上到下为1、2、3层
黄色Y、粉P1、紫P2、蓝B、白W、绿G、无关色X

  1. 第1层复原,简单
  2. 2层每个方向的两边需复原
正面:
P1 P1 P1
X P1 X
X P1 X
正面下中的P1下方是B
左侧:
B B B
B B X
X X X
需要将正面下中的P1绕中间旋转到左侧右中位置
旋转方法:
下右、左下、下左、左上、下左、正面逆时针转、下右、正面顺时针转
如果是将正面下中移动到右中,第一步是下左,第二步是右下,然后类似

1、2步之后1、2层已复原

  1. 底层十字
基础过程:右下、下左、右上、下右、右上、正面逆时针、右下、正面顺时针;
其他细节不予记录;
  1. 底层全恢复
底层"小鱼"置于左上角,如果双头鱼,则"小鱼左下角";
正面,使用233法则:
右下、下右、左下(形成233,然后开始恢复)、下左、右上、下右、左上;
可反复使用,调整小鱼方向,直到形成小鱼或底层全恢复
  1. 3层四个角复原
首先一定要找到侧面两个角相同的那一面,将这一面放在右侧;
然后执行:
右下、下右、左下(形成233,然后开始恢复)、下左、右上、下右、下右、左上、下右、左下、下左、下左、左上
没有成功就多做几次;
  1. 3层4个中心块复原,完成整体复原
首先如果侧面有一面已复原,就置于背面;
执行:
正面中间列向下、正面中间列向下(白色列到底层)、下右、正面中间列向上、下右、下右、正面中间列向下、下右、正面中间列向上、正面中间列向上;
未恢复重复执行;

两个有趣的数学问题

  1. 有1000瓶水,给你10只小白鼠,如何找出其中唯一一瓶有毒药的水 (必须在60分钟内找出,毒药50分钟必发作)。
  2. 12枚硬币,至多一个假币,质量与真币不同,一个天平,如何称三次判断是否有假币,假币是哪个
1. 解法
因为 2的10次方是1024 所以我们可以用10只小鼠按2进制编码 来达到1000种结果的目的 也就是10位二进制数字;
比如:小鼠从0到9编号 从右到左排队  比如十进制11二进制表示是1011 那就是 0 1 3 三只小鼠去喝11号杯子的水,
依次类推 就有1000种组合  如果50分钟后 0 1 3三只小鼠死掉 那就说明11号杯子有毒;

同样的如果有x只小鼠,那么就最多可以辨别 2^x -1 瓶水中的一瓶毒药(比如3只小鼠可以鉴别7瓶)。
2. 解法
转换为线性代数方式解决
https://www.bilibili.com/video/BV1Fy4y1T7mL

npm init 拓展知识

npm init

[email protected] 之后的版本增加了 npm run <initializer> 这样的操作,即执行
npm run thinkjs
时,npm会补全为create-thinkjs并执行
npx create-thinkjs
完整的规则:
* npm init foo -> npx create-foo
* npm init @usr/foo -> npx @usr/create-foo
* npm init @usr -> npx @usr/create

详细:

npm init vite-app
# same as 
npx create-vite-app

相当于更加语义化的一种操作,可以提高生产力。

例如create-vite-app推荐的初始化命令

npm init vite-app <project-name>
相当于 npx create-vite-app <project-name>
执行create-vite-app命令传参数project-name

mac工具记录

  1. zsh
    然后要装oh-my-zsh, 之后一定要装的几个插件(git zsh-autosuggestions zsh-syntax-highlighting autojump)
  2. stats
    很好用的性能监测工具
    https://github.com/exelban/stats
  3. Kap
    好用的录屏工具,可以生成gif/mp4等
  4. chrome浏览器标签,建议使用群组功能
  5. vscode插件
    ESLint\GitLens\Markdown Preview Enhanced\prettier等
  6. github1s 在github代码链接中修改为github1s即可在线以vscode的方式查看项目代码

两个新知道的js小技巧

一、解构小技巧 -- 多次解构

平常我们需要用到一个嵌套多层的对象中某些属性,会将其解构出来使用

let obj = {
part1: {
name: '零一',
age: 23
}
}

// 解构
const { part1: { name, age } } = obj
// 使用
console.log(name, age) // 零一 23
这种情况下,你把 name 和 age 从 part1 里解构出来了以后,你就无法使用变量 obj 中的 part1 属性了,如:

const { part1: { name, age } } = obj
console.log(part1) // Uncaught ReferenceError: part1 is not defined
其实你可以多次解构,如:
const { part1: { name, age }, part1 } = obj
console.log(part1) // {name: "零一", age: 23}

二、数字分隔符

有时你会在文件中定义一个数字常量

const myMoney = 1000000000000
这么多个 0 ,1、2 ... 6、7 ... 数晕了都,怎么办?

数字分隔符整起来!

const myMoney = 1_000_000_000_000

console.log(myMoney) // 1000000000000
这样写是没问题的,而且数字分割开后也更直观!!

window.opener的一个问题

window.opener的一个问题

场景:
使用<a target="_blank"> 或者 window.open()打开新页面,不做特殊处理的话,新页面可以使用
**window.opener**
访问当前页面的window对象!
其中一个后果是在新页面使用window.opener.location = 'xx.com'后直接修改了原页面地址。
某些论坛等外链可能会修改原本页面地址,引导用户进入恶意网站,或者修改window属性值,
达到看恶意攻击的目的。

如何防止出现这种问题呢

方案就是禁止新页面获取到原本页面的window对象
页面增加如下代码:
const otherWindow = window.open()
otherWindow.opener = null
这样新页面获取到的window.opener对象就是null

js无主题笔记

  1. Object.is(value1, value2)
    方法用于比较两个值是否相同, 返回布尔值;
    如果是对象,就判断指向地址是否相同。
let a = {j: 0}, b = a
Object.is(a, b)
//true
  1. 块元素水平居中
.content {
  width: 980px;
  margin-left: auto;
  margin-right auto;
}
不应该偷懒,写成
.content {
  width: 980px;
  margin: 0 auto;
}
css代码要符合最小影响原则,水平居中不应该设置top, bottom的margin.
这个要记住。
  1. js探测cpu, 内存情况
    (1)通过setTimeout方式探测cpu,每隔50ms打一下点
    通过 setTimeout 的方式探测 CPU 已经不是秘密,去年腾讯的朋友在 Velocity 上分享过,北京有朋友还通过这个原理,几年前就实现了网页游戏中动画等耗时操作的自动调节。原理很简单:
function pulse() {
  t && data.push(Date.now() - t)
  t = Date.now()
  setTimeout(pulse, 50)
}
pulse()

就是每隔 50ms 打一下点。理想情况下,data 的值应该是
data = [50, 50, 50, 50, ...]
但实际情况,data 会是
data = [51, 52, 50, 52, ...]
当 CPU 比较忙时,data 的数据变成
data = [81, 102, 90, 62, ...]
可以绘制出 CPU 占比趋势图
(2)内存泄漏探测
可以使用performance.memory接口探测
performance.memory.usedJSHeapSize等。

  1. 浏览器进程和线程
    浏览器是多进程的,有渲染进程,主进程,插件进程等等;
    浏览器内核是多线程的,如GUI渲染线程,GUI事件触发线程,http请求线程等;
    js引擎本身是单线程的,计时需要依赖外部,异步请求也需要外部,否则就会阻塞;
    定时事件是异步的(定时触发线程),请求是异步的(http请求线程)。
    浏览器会新开一个线程做请求,当请求状态更新时,有回调,异步线程就会将状态变化放在js引擎的处理队列中等待结果,当任务处理,js引擎始终是单线程执行js程序。

  2. 浏览器发起一次请求的过程(很详细)
    https://segmentfault.com/a/1190000013662126

  3. react 内联样式
    style={Object.assign({}, style, {margin: ${props.padding}px})}

  4. npx
    npx是npm的一个命令,可以调用项目内部安装的模块;
    一般使用依赖里面的命令,只能在项目脚本和 package.json 的scripts字段里面, 如果想在命令行下调用,必须像下面这样:

$ node-modules/.bin/mocha --version

npx就是解决这个问题, 可以直接运行安装的模块。
npx create-react-app --version

  1. commonjs, amd规范
commonJS规范:
在node端使用
require('xx.js')
module.exports
amd规范
浏览器使用
require(['dep1'], function(){})
接受依赖列表, 和一个回调函数,异步读取依赖后执行回调。
angular使用requirejs这种AMD规范实现来做浏览器端的模块开发方式;

  1. js中通过queueMicrotask()使用微任务
    为了允许第三方库、框架、polyfills 能使用微任务, Window 暴露了 queueMicrotask() 方法,而 Worker 提供了同名的 queueMicrotask() 方法。
    不需要参数, 也不返回任何内容。
if (a) {
    this.data = xx;
    this.dispatchEvent(new Event("load"));
} else {
    fetch(url).then(result => result.arrayBuffer()).then(data => {
      this.cache[url] = data;
      this.data = data;
      this.dispatchEvent(new Event("load"));
    )};
}

上诉情况下,if - else分支分开了两部分代码,分别是微任务和普通代码, 可以在if里面使用微任务来保持一致性

if (a) {
	queueMicrotask(() => {
		this.data = xx;
    	this.dispatchEvent(new Event("load"));
	})
} else {
    fetch(url).then(result => result.arrayBuffer()).then(data => {
      this.cache[url] = data;
      this.data = data;
      this.dispatchEvent(new Event("load"));
    )};
}

平衡了两个子句。

vscode好用快捷键

  1. option + ↑/↓ 当前行内容上下移动
  2. shift + option + ↑/↓ 向上/下拷贝当前行代码(选中多行则拷贝多行)
    a. 按住alt,用鼠标左键点击,可以出现多个光标
    b. 选中一段文字,按shift+alt+i,可以在每行末尾出现光标
  3. ctrl + cmd + space 打开表情选择器
  4. ctrl + ~ 打开terminal
  5. shift + option + F 格式化代码
  6. ctrl + D 选中下一个当前选中单词
  7. 选中单词后 cmd + shift + L 选中所有当前单词
  8. ctrl + shift + A 注释多行代码

Object.keys 返回属性名排序问题

结论

1. 属性名如果是数字,按从小到大排序输出;如果是字符串或者symbol类型,按属性创建时间先后排序;
2. 如果是数字、字符串、symbol混合,则先输出数字,再字符串,最后symbol

上面规则也适用于以下API

1. Object.entries
2. Object.values
3. for...in循环
4. Object.getOwnPropertyNames
5. Reflect.ownKeys

以上API除了Reflect.ownKeys之外,其他API均会将Symbol类型的属性过滤掉。

例子

Object.keys({
    4: '12',
    'b': 'b-v',
    2: '11',
    'a': 'a-v',
    0: '222',
    'c': 'c-v',
})
// ["0", "2", "4", "b", "a", "c"]

// 可以看到数字属性名被转字符串并按规则组织顺序。

再测试Object.values
Object.values({
    4: '12',
    'b': 'b-v',
    2: '11',
    'a': 'a-v',
    0: '222',
    'c': 'c-v',
})
//  ["222", "11", "12", "b-v", "a-v", "c-v"]

js隐式类型转换(奇怪运算知识总结)

请参考 https://juejin.cn/post/6844903934876745735#heading-2

  1. 加法一元运算
  • target 实际会进行Number(target)操作
    不同类型值Number转换后结果:
  • null -> 0
  • undefined -> NaN
  • Boolean -> true是1 false是0
  • string -> 纯数字字符串就是数字,否则就是NaN
  • Object -> 进行ToPrimitive

ToPrimitive介绍
如果是原始值返回本身,不然调用valueOf,返回是原始值就返回本身;否则调用toString;

+null
0
+undefined
Nan
+false
0
+''
0
+'123'
123
+'xc'
NaN
+{}
NaN
+[]
NaN

+{} 就是如下:{}.valueOf 不是原始值; Number({}.toString()) => Number('[object Object]') => NaN

  1. 加法二元运算
    value1 + value2
    在计算这个表达式时,内部的操作步骤是这样的
    将两个操作数转换为原始值 (以下是数学表示法的伪代码,不是可以运行的 JavaScript 代码):
    prim1 := ToPrimitive(value1)
    prim2 := ToPrimitive(value2)
    如果 prim1 或者 prim2 中的任意一个为字符串,则将另外一个也转换成字符串,然后返回两个字符串连接操作后的结果。
    否则,将 prim1 和 prim2 都转换为数字类型,返回他们的和。

比如:
[]+[]
// 非原始值,所以ToPrimitive =》[].toString() => ""
// "" + "" => ""

  1. 布尔值转化
    值不是undefined或null的任何对象、非空字符串(包括其值为false的布尔对象)在传递给条件语句时都将计算为true
    或者说:只有null,undefined,0,false,NaN,空字符串这6种情况转为布尔值结果为false,其余全部为true

  2. 宽松相等(==)的隐式转换
    (1)当字符串类型与数字类型相比较时,字符串类型会被转换为数字类型
    (2)只要布尔类型参与比较,该布尔类型就会率先被转成数字类型

  3. 更多知识
    参考 https://jsisweird.com/

1. true + false
// 1
二元相加,基础类型不是对象,没有字符串,就转为数字
=> 1 + 0 => 1
2. [,,,].length
// 3
比如[,].length == 1
数组最后一个空逗号尾后逗号,会被忽略。如
var arr = [
  1,
  2,
  3,
];
arr; // [1, 2, 3]
3. [1, 2, 3] + [4, 5, 6]
// "1,2,34,5,6"
4. 10,2,3
// 3
逗号运算符,只会返回最后一个值。
1, 2, 3, 4; // -> 4
42, "pineapple", true; // -> true
5. +!![]
// 1
转布尔值,[]是对象一律转为true => +true => 1
6. 1/0; // -> Infinity
7. 

最近学到的三个知识:数列、幸存者偏差、nazo

数列与二进制
问题1: 老鼠试毒问题,1000瓶酒其中1瓶有毒,用10只老鼠找出毒酒,需要注意每只老鼠只可以试1次,毒酒立即生效;
问题2:有10个箱子,每个箱子装任意数目苹果,共有1000个苹果装在这些箱子内,要求随机选择一个 >=1 且<=1000的数字,都可以找到几个箱子内苹果数组合加起来刚好等于这个数字。请问每个箱子内苹果数量。

幸存者偏差
问题:以下是二战期间美国统计的在空中遭遇后幸存的飞机身上的弹孔分布情况,请问该给飞机哪里加装更多钢板呢?为什么?
image

问题2: 餐馆提供了一个用餐调研,客人可以扫码填写用餐建议和评价,请问这个评价是客观的吗,为什么?

nazo题目
一个网址: https://nazo.one-story.cn/
有很多有趣的题目。

答案
问题1: 2^10 === 1024,给酒按0~999编号,老鼠按二进制0~9位编号,01===0b1, 3 === 0b11, 9 === 0b1001等,然后按二进制位给老鼠喝对应编号的所有酒的混合酒,找到死亡老鼠相同的编号作为二进制置1,比如1,2号死,那就是011为3号有毒,即死亡的小鼠编号就是这杯毒酒编号的二进制所有为1的位置的小鼠。
问题2:答案是1/2/4/8/16/32/64/128/256/489
原因:(1)从1开始,逐渐增加数字,3可以通过1 +2 得到,8之前的数字可以过1 2 4组合等。。 实际就是2的n次方,2^0~2^9,最后一个数字将剩余苹果都放进去即可。(2)考虑二进制思路,这个问题是老鼠试毒问题反过来,考虑随机一个<1000的数字,就是小于2^10即0bxxxxxxxxx的数字,每个x位可为1也可为0,所有情况组合即得到所有0~1000数字,甚至考虑每个x位为1,那结果是等于2^11-1的结果,大于1000了,我们将10个bit位分别分配给每个箱子,按每个bit位为1,低于这个bit的位全部为0,即可得到结果,即箱子分别数字是0b1/0b10/0b100/0b1000....刚好每个是2^n,n从0开始,比如0b1/0b100/0b10000相加是0b10101,给出的随机数字转为二进制数字,哪个bit为1,哪个箱子就参与求和即可。
问题3: 只要幸存的飞机才能降落下来,所以中弹的地方都是不致命的,机头和尾端邮箱发动机等处没有弹孔的才是真正致命的地方;
问题4: 反馈只能体现体验很好和体验很差的那些人,中间的人是不会写建议的,评价不客观,但是可以帮助解决体验差的人的问题;

web请求的压缩格式---gzip,brotli

参考 掘金文章

  1. 大部分网站都对js, css等开启了gzip压缩,请求response头中有content-encoding: gzip,表示文件是经过gzip压缩的,浏览器会自动根据这个返回头对文件解压,得到原始文件。gzip压缩大大减少了传输文件体积。
    gzip压缩算法是Deflate算法(一般先用Lz77算法压缩,再使用Huffman编码)。
  2. 更好的压缩方式: brotli
    如果浏览器支持 请求头Accept-Encoding的值:
    Accept-Encoding: gzip, deflate, sdch, br
    如果服务端支持Brotli算法,则会返回以下的响应头:
    Content-Encoding: br
    brotli算法压缩效率更好。目前国内网站使用的不多。

Array.from API 使用

忽略的知识:

  1. 字符串可直接生成字符数组
Array.from("abc")
// ['a', 'b', 'c']
  1. 如何创建一个n的遍历器
Array.from({ length: 10 }, (_, i) => i + 1)
// [1, 2, 3, .....]

// 可以从类数组生成数组,所以,可以从{ length: 10 } 这样的对象生成;
// 第二个参数是一个函数,对生成数组的每个元素转换

一个讲动态规划算法核心思路的非常好的文章

地址:https://labuladong.github.io/algo/1/3/

总结:

动态规划有两种基本思路:
1. 自顶向下
使用dp函数,从大的结果一路计算到基础状态。
2. 自下而上
使用dp table,也就是dp数组,从小的基础状态向上不断计算,直到计算出大的结果。

以下是原文:

读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目:

509.斐波那契数(简单)

322.零钱兑换(中等)

———–

动态规划问题(Dynamic Programming)应该是很多读者头疼的,不过这类问题也是最具有技巧性,最有意思的。本书使用了整整一个章节专门来写这个算法,动态规划的重要性也可见一斑。

本文解决几个问题:

动态规划是什么?解决动态规划问题有什么技巧?如何学习动态规划?

刷题刷多了就会发现,算法技巧就那几个套路,我们后续的动态规划系列章节,都在使用本文的解题框架思维,如果你心里有数,就会轻松很多。所以本文放在第一章,来扒一扒动态规划的裤子,形成一套解决这类问题的思维框架,希望能够成为解决动态规划问题的一部指导方针。本文就来讲解该算法的基本套路框架,下面上干货。

首先,动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。

既然是要求最值,核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值呗。

动态规划这么简单,就是穷举就完事了?我看到的动态规划问题都很难啊!

首先,动态规划的穷举有点特别,因为这类问题存在「重叠子问题」,如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算。

而且,动态规划问题一定会具备「最优子结构」,才能通过子问题的最值得到原问题的最值。

另外,虽然动态规划的核心**就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事,只有列出正确的「状态转移方程」,才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解,但是在实际的算法问题中,写出状态转移方程是最困难的,这也就是为什么很多朋友觉得动态规划问题困难的原因,我来提供我研究出来的一个思维框架,辅助你思考状态转移方程:

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

按上面的套路走,最后的结果就可以套这个框架:

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 求最值(选择1,选择2...)

下面通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理。前者主要是让你明白什么是重叠子问题(斐波那契数列没有求最值,所以严格来说不是动态规划问题),后者主要举集中于如何列出状态转移方程。

一、斐波那契数列
请读者不要嫌弃这个例子简单,只有简单的例子才能让你把精力充分集中在算法背后的通用**和技巧上,而不会被那些隐晦的细节问题搞的莫名其妙。想要困难的例子,历史文章里有的是。

1、暴力递归

斐波那契数列的数学形式就是递归的,写成代码就是这样:

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

这个不用多说了,学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂,但是十分低效,低效在哪里?假设 n = 20,请画出递归树:

PS:但凡遇到需要递归的问题,最好都画出递归树,这对你分析算法的复杂度,寻找算法低效的原因都有巨大帮助。

这个递归树怎么理解?就是说想要计算原问题 f(20),我就得先计算出子问题 f(19) 和 f(18),然后要计算 f(19),我就要先算出子问题 f(18) 和 f(17),以此类推。最后遇到 f(1) 或者 f(2) 的时候,结果已知,就能直接返回结果,递归树不再向下生长了。

递归算法的时间复杂度怎么计算?就是用子问题个数乘以解决一个子问题需要的时间。

首先计算子问题个数,即递归树中节点的总数。显然二叉树节点总数为指数级别,所以子问题个数为 O(2^n)。

然后计算解决一个子问题的时间,在本算法中,没有循环,只有 f(n - 1) + f(n - 2) 一个加法操作,时间为 O(1)。

所以,这个算法的时间复杂度为二者相乘,即 O(2^n),指数级别,爆炸。

观察递归树,很明显发现了算法低效的原因:存在大量重复计算,比如 f(18) 被计算了两次,而且你可以看到,以 f(18) 为根的这个递归树体量巨大,多算一遍,会耗费巨大的时间。更何况,还不止 f(18) 这一个节点被重复计算,所以这个算法及其低效。

这就是动态规划问题的第一个性质:重叠子问题。下面,我们想办法解决这个问题。

2、带备忘录的递归解法

明确了问题,其实就已经把问题解决了一半。即然耗时的原因是重复计算,那么我们可以造一个「备忘录」,每次算出某个子问题的答案后别急着返回,先记到「备忘录」里再返回;每次遇到一个子问题先去「备忘录」里查一查,如果发现之前已经解决过这个问题了,直接把答案拿出来用,不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」,当然你也可以使用哈希表(字典),**都是一样的。

int fib(int N) {
    // 备忘录全初始化为 0
    int[] memo = new int[N + 1];
    // 进行带备忘录的递归
    return helper(memo, N);
}

int helper(int[] memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过,不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

现在,画出递归树,你就知道「备忘录」到底做了什么。

实际上,带「备忘录」的递归算法,把一棵存在巨量冗余的递归树通过「剪枝」,改造成了一幅不存在冗余的递归图,极大减少了子问题(即递归图中节点)的个数。

递归算法的时间复杂度怎么计算?就是用子问题个数乘以解决一个子问题需要的时间。

子问题个数,即图中节点的总数,由于本算法不存在冗余计算,子问题就是 f(1), f(2), f(3) … f(20),数量和输入规模 n = 20 成正比,所以子问题个数为 O(n)。

解决一个子问题的时间,同上,没有什么循环,时间为 O(1)。

所以,本算法的时间复杂度是 O(n)。比起暴力算法,是降维打击。

至此,带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上,这种解法和迭代的动态规划已经差不多了,只不过这种方法叫做「自顶向下」,动态规划叫做「自底向上」。

啥叫「自顶向下」?注意我们刚才画的递归树(或者说图),是从上向下延伸,都是从一个规模较大的原问题比如说 f(20),向下逐渐分解规模,直到 f(1) 和 f(2) 这两个 base case,然后逐层返回答案,这就叫「自顶向下」。

啥叫「自底向上」?反过来,我们直接从最底下,最简单,问题规模最小的 f(1) 和 f(2) 开始往上推,直到推到我们想要的答案 f(20),这就是动态规划的思路,这也是为什么动态规划一般都脱离了递归,而是由循环迭代完成计算。

3、dp 数组的迭代解法

有了上一步「备忘录」的启发,我们可以把这个「备忘录」独立出来成为一张表,就叫做 DP table 吧,在这张表上完成「自底向上」的推算岂不美哉!

int fib(int N) {
    if (N == 0) return 0;
    int[] dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

画个图就很好理解了,而且你发现这个 DP table 特别像之前那个「剪枝」后的结果,只是反过来算而已。实际上,带备忘录的递归解法中的「备忘录」,最终完成后就是这个 DP table,所以说这两种解法其实是差不多的,大部分情况下,效率也基本相同。

这里,引出「状态转移方程」这个名词,实际上就是描述问题结构的数学形式:

为啥叫「状态转移方程」?其实就是为了听起来高端。你把 f(n) 想做一个状态 n,这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来,这就叫状态转移,仅此而已。

你会发现,上面的几种解法中的所有操作,例如 return f(n - 1) + f(n - 2),dp[i] = dp[i - 1] + dp[i - 2],以及对备忘录或 DP table 的初始化操作,都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性,它是解决问题的核心。而且很容易发现,其实状态转移方程直接代表着暴力解法。

千万不要看不起暴力解,动态规划问题最困难的就是写出这个暴力解,即状态转移方程。只要写出暴力解,优化方法无非是用备忘录或者 DP table,再无奥妙可言。

这个例子的最后,讲一个细节优化。细心的读者会发现,根据斐波那契数列的状态转移方程,当前状态只和之前的两个状态有关,其实并不需要那么长的一个 DP table 来存储所有的状态,只要想办法存储之前的两个状态就行了。所以,可以进一步优化,把空间复杂度降为 O(1):

int fib(int n) {
    if (n < 1) return 0;
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

这个技巧就是所谓的「状态压缩」,如果我们发现每次状态转移只需要 DP table 中的一部分,那么可以尝试用状态压缩来缩小 DP table 的大小,只记录必要的数据,上述例子就相当于把DP table 的大小从 n 缩小到 2。后续的动态规划章节中我们还会看到这样的例子,一般来说是把一个二维的 DP table 压缩成一维,即把空间复杂度从 O(n^2) 压缩到 O(n)。

有人会问,动态规划的另一个重要特性「最优子结构」,怎么没有涉及?下面会涉及。斐波那契数列的例子严格来说不算动态规划,因为没有涉及求最值,以上旨在说明重叠子问题的消除方法,演示得到最优解法逐步求精的过程。下面,看第二个例子,凑零钱问题。

二、凑零钱问题
先看下题目:给你 k 种面值的硬币,面值分别为 c1, c2 ... ck,每种硬币的数量无限,再给一个总金额 amount,问你最少需要几枚硬币凑出这个金额,如果不可能凑出,算法返回 -1 。算法的函数签名如下:

// coins 中是可选硬币面值,amount 是目标金额
int coinChange(int[] coins, int amount);
比如说 k = 3,面值分别为 1,2,5,总金额 amount = 11。那么最少需要 3 枚硬币凑出,即 11 = 5 + 5 + 1。

你认为计算机应该如何解决这个问题?显然,就是把所有可能的凑硬币方法都穷举出来,然后找找看最少需要多少枚硬币。

1、暴力递归

首先,这个问题是动态规划问题,因为它具有「最优子结构」的。要符合「最优子结构」,子问题间必须互相独立。啥叫相互独立?你肯定不想看数学证明,我用一个直观的例子来讲解。

比如说,假设你考试,每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩,那么你的子问题就是要把语文考到最高,数学考到最高…… 为了每门课考到最高,你要把每门课相应的选择题分数拿到最高,填空题分数拿到最高…… 当然,最终就是你每门课都是满分,这就是最高的总成绩。

得到了正确的结果:最高的总成绩就是总分。因为这个过程符合最优子结构,“每门科目考到最高”这些子问题是互相独立,互不干扰的。

但是,如果加一个条件:你的语文成绩和数学成绩会互相制约,数学分数高,语文分数就会降低,反之亦然。这样的话,显然你能考到的最高总成绩就达不到总分了,按刚才那个思路就会得到错误的结果。因为子问题并不独立,语文数学成绩无法同时最优,所以最优子结构被破坏。

回到凑零钱问题,为什么说它符合最优子结构呢?比如你想求 amount = 11 时的最少硬币数(原问题),如果你知道凑出 amount = 10 的最少硬币数(子问题),你只需要把子问题的答案加一(再选一枚面值为 1 的硬币)就是原问题的答案。因为硬币的数量是没有限制的,所以子问题之间没有相互制,是互相独立的。

PS:关于最优子结构的问题,后文动态规划答疑篇 还会再举例探讨。

那么,既然知道了这是个动态规划问题,就要思考如何列出正确的状态转移方程?

1、确定 base case,这个很简单,显然目标金额 amount 为 0 时算法返回 0,因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」,也就是原问题和子问题中会变化的变量。由于硬币数量无限,硬币的面额也是题目给定的,只有目标金额会不断地向 base case 靠近,所以唯一的「状态」就是目标金额 amount。

3、确定「选择」,也就是导致「状态」产生变化的行为。目标金额为什么变化呢,因为你在选择硬币,你每选择一枚硬币,就相当于减少了目标金额。所以说所有硬币的面值,就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法,所以会有一个递归的 dp 函数,一般来说函数的参数就是状态转移中会变化的量,也就是上面说到的「状态」;函数的返回值就是题目要求我们计算的量。就本题来说,状态只有一个,即「目标金额」,题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数:

dp(n) 的定义:输入一个目标金额 n,返回凑出目标金额 n 的最少硬币数量。

搞清楚上面这几个关键点,解法的伪码就可以写出来了:


// 伪码框架
int coinChange(int[] coins, int amount) {
    // 题目要求的最终结果是 dp(amount)
    return dp(coins, amount)
}

// 定义:要凑出金额 n,至少要 dp(coins, n) 个硬币
int dp(int[] coins, int n) {
    // 做选择,选择需要硬币最少的那个结果
    for (int coin : coins) {
        res = min(res, 1 + dp(n - coin))
    }
    return res
}

根据伪码,我们加上 base case 即可得到最终的答案。显然目标金额为 0 时,所需硬币数量为 0;当目标金额小于 0 时,无解,返回 -1:

int coinChange(int[] coins, int amount) {
    // 题目要求的最终结果是 dp(amount)
    return dp(coins, amount)
}

int dp(int[] coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解,然后加一
        res = Math.min(res, subProblem + 1);
    }

    return res == Integer.MAX_VALUE ? -1 : res;
}

PS:这里 coinChange 和 dp 函数的签名完全一样,所以理论上不需要额外写一个 dp 函数。但为了后文讲解方便,这里还是另写一个 dp 函数来实现主要逻辑。

至此,状态转移方程其实已经完成了,以上算法已经是暴力解法了,以上代码的数学形式就是状态转移方程:

至此,这个问题其实就解决了,只不过需要消除一下重叠子问题,比如 amount = 11, coins = {1,2,5} 时画出递归树看看:

递归算法的时间复杂度分析:子问题总数 x 每个子问题的时间。

子问题总数为递归树节点个数,这个比较难看出来,是 O(n^k),总之是指数级别的。每个子问题中含有一个 for 循环,复杂度为 O(k)。所以总时间复杂度为 O(k * n^k),指数级别。

2、带备忘录的递归

类似之前斐波那契数列的例子,只需要稍加修改,就可以通过备忘录消除子问题:


int[] memo;

int coinChange(int[] coins, int amount) {
    memo = new int[amount + 1];
    // dp 数组全都初始化为特殊值
    Arrays.fill(memo, -666);

    return dp(coins, amount);
}

int dp(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 查备忘录,防止重复计算
    if (memo[amount] != -666)
        return memo[amount];

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解,然后加一
        res = Math.min(res, subProblem + 1);
    }
    // 把计算结果存入备忘录
    memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
    return memo[amount];
}

不画图了,很显然「备忘录」大大减小了子问题数目,完全消除了子问题的冗余,所以子问题总数不会超过金额数 n,即子问题数目为 O(n)。处理一个子问题的时间不变,仍是 O(k),所以总的时间复杂度是 O(kn)。

3、dp 数组的迭代解法

当然,我们也可以自底向上使用 dp table 来消除重叠子问题,关于「状态」「选择」和 base case 与之前没有区别,dp 数组的定义和刚才 dp 函数类似,也是把「状态」,也就是目标金额作为变量。不过 dp 函数体现在函数参数,而 dp 数组体现在数组索引:

dp 数组的定义:当目标金额为 i 时,至少需要 dp[i] 枚硬币凑出。

根据我们文章开头给出的动态规划代码框架可以写出如下解法:

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // 数组大小为 amount + 1,初始值也为 amount + 1
    Arrays.fill(dp, amount + 1);

    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解,跳过
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

PS:为啥 dp 数组初始化为 amount + 1 呢,因为凑成 amount 金额的硬币数最多只可能等于 amount(全用 1 元面值的硬币),所以初始化为 amount + 1 就相当于初始化为正无穷,便于后续取最小值。为啥不直接初始化为 int 型的最大值 Integer.MAX_VALUE 呢?因为后面有 dp[i - coin] + 1,这就会导致整型溢出。

三、最后总结
第一个斐波那契数列的问题,解释了如何通过「备忘录」或者「dp table」的方法来优化递归树,并且明确了这两种方法本质上是一样的,只是自顶向下和自底向上的不同而已。

第二个凑零钱的问题,展示了如何流程化确定「状态转移方程」,只要通过状态转移方程写出暴力递归解,剩下的也就是优化递归树,消除重叠子问题而已。

如果你不太了解动态规划,还能看到这里,真得给你鼓掌,相信你已经掌握了这个算法的设计技巧。

计算机解决问题其实没有任何奇技淫巧,它唯一的解决办法就是穷举,穷举所有可能性。算法设计无非就是先思考“如何穷举”,然后再追求“如何聪明地穷举”。

列出状态转移方程,就是在解决“如何穷举”的问题。之所以说它难,一是因为很多穷举需要递归实现,二是因为有的问题本身的解空间复杂,不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路,是降低时间复杂度的不二法门,除此之外,试问,还能玩出啥花活?

之后我们会有一章专门讲解动态规划问题,如果有任何问题都可以随时回来重读本文,希望读者在阅读每个题目和解法时,多往「状态」和「选择」上靠,才能对这套框架产生自己的理解,运用自如。

接下来可阅读:

动态规划设计:最长递增子序列

2023 零散知识拾遗

  1. 关于event.target 和 event.currentTarget的区别
    event.target是事件真正的触发者,event.currentTarget是当前事件监听者;比如:
<div id="A><div id="B">B</div></div>

function handle(e) {
  console.warn(e.target.id, e.currentTarget.id)
}
document.querySelector('#A').onclick = handle

// 点击B
// 打印 B A
  1. 关于npm version和npm publish
    npm version:
    npm version可以快捷修改版本号
    npm version prerelease --preid=alpha
    更新一个alpha版本,会修改package.json文件
    npm version patch
    更新版本的最后一位:1.0.6 -> 1.0.7
    npm publish:
    npm dist-tag ls <pkg> 来查看一个包的tag,至少三种:latest(最新版本)、beta(测试版本)、next(先行版本);
    npm publish --tag beta
    这样发布的是测试版本,其他人直接npm install xx的时候不会安装到这个版本,只有直接指定这个beta版本版本号才会安装;
    如果版本号是1.0.6-alpha.1,但是通过npm publish发布,还是会发布到latest这个tag,用户npm i xx就会安装这个最新版本。

【学习探索】useMemo是怎么做到缓存的, useCallback呢, useEffect, useState;

  1. 实际就是Hook的原理,React Hooks源码解析,原来这么简单~
  2. 所有hook都是mount, update两个场景,会在所有hook mount时,按照顺序放入一个单向链表,每个hook再储存一个action更新queue(单向循环链表),每次setState就会依次调用,拿到最新结果;useEffect, useMemo这些有依赖的,会在每次判定时,为依赖打上tag, 标记是否改变了,改变就更新执行内部回调。

eslint配置

这里是一个eslint例子;

文件名:.eslintrc.js

module.exports = {
  // 这个parser可以帮助检测ts相关问题
  parser: '@typescript-eslint/parser',
  // 可以继承一个已有配置
  extends: ['@bdxxxx/eslint-config-xxxxx'],
  // 三个eslint插件分别处理文件夹/文件名/导入;需要dev安装eslint-plugin-filenames;eslint-plugin-folders;eslint-plugin-import;
  plugins: ['folders', 'filenames', 'import'],
  ignorePatterns: ['src/services/api/typings/**/*.ts', 'src/services/tea/types/**/*.ts'],
  rules: {
    '@typescript-eslint/no-non-null-asserted-optional-chain': 'off',
    '@typescript-eslint/explicit-function-return-type': 'off',
    '@typescript-eslint/explicit-member-accessibility': 'off',
    '@typescript-eslint/no-empty-function': 'off',
    'react/destructuring-assignment': 'warn',
    'react/react-in-jsx-scope': 'off',
    'no-shadow': 'warn',
    'no-sequences': ['error', { allowInParentheses: false }],
    // 这里控制了文件名/文件夹名必须的格式;
    'filenames/match-regex': [2, '^[a-z0-9][a-z0-9-.]*[a-z0-9]$', '/src'],
    'folders/match-regex': [2, '^[a-z0-9][a-z0-9-]*[a-z0-9]$', '/src'],
    'import/no-nodejs-modules': 'off',
    // disallow non-import statements appearing before import statements
    // https://github.com/benmosher/eslint-plugin-import/blob/master/docs/rules/first.md
    // 这个控制import内容的顺序,必须绝对路径在相对路径前面
    'import/first': ['error', 'absolute-first'],
    'import/imports-first': 'off',
    'import/order': ['off', {
      groups: ['builtin', 'external', 'internal', 'parent', 'sibling', 'index'],
      'newlines-between': 'never'
    }],
    // 控制import内容和正式内容之间必须有一行间隔;
    'import/newline-after-import': 'error',
  },
  parserOptions: {
    project: 'tsconfig.json',
   // 这个配置可以让eslint在monorepo模式下生效;
    tsconfigRootDir: __dirname,
    sourceType: 'module',
  },
}

同时,需要装vscode eslint插件,eslintrc修改后可运行 Eslint: Restart eslint server;

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.