ssh_晨曦时梦见兮

ssh_晨曦时梦见兮 查看完整档案

上海编辑  |  填写毕业院校字节跳动  |  前端工程师 编辑 github.com/sl1673495 编辑
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

ssh_晨曦时梦见兮 发布了文章 · 2月23日

浅谈 Vite 2.0 原理,依赖预编译,插件机制是如何兼容 Rollup 的?

前言

Hi,我是 ssh,春节过去了,躁动的心也该收一收,开始新一年的学习了。我目前就职于字节跳动的 Web Infra 团队,目前团队还很缺人(尤其是北京)。

为此我组建了一个氛围特别好的招聘社群,大家在里面尽情的讨论面试相关的想法和问题,也欢迎你加入,随时投递简历给我。

在字节跳动,大家都会自发的研究社区前沿的技术,尝试接入内部的项目并寻找提升开发效率的可能性,这种追求极致敢于创新也是被鼓励的,也有不少同学已经在尝试把新一代的构建工具 Vite 和 snowpack 引入使用。

这篇文章我想简单的聊聊,让尤老师如此专注的 Vite 2.0 到底有哪些亮点。

前几天,尤雨溪在各个社交平台宣布 Vite 2.0 发布了。

看得出他对 Vite 倾注了很多感情,甚至都冷落了 Vue3,停更了两个多月。

相关的中文公告已经有翻译了,可以在尤雨溪的知乎文章:Vite 2.0 发布了中查看。

这篇文章来谈谈 Vite 2.0 的发布中,几个让我比较感兴趣的技术点。

Vite 原理

为什么会出现 Vite?在过去的 Webpack、Rollup 等构建工具的时代,我们所写的代码一般都是基于 ES Module 规范,在文件之间通过 importexport 形成一个很大的依赖图。

这些构建工具在本地开发调试的时候,也都会提前把你的模块先打包成浏览器可读取的 js bundle,虽然有诸如路由懒加载等优化手段,但懒加载并不代表懒构建,Webpack 还是需要把你的异步路由用到的模块提前构建好。

当你的项目越来越大的时候,启动也难免变的越来越慢,甚至可能达到分钟级别。而 HMR 热更新也会达到好几秒的耗时。

Vite 则别出心裁的利用了浏览器的原生 ES Module 支持,直接在 html 文件里写诸如这样的代码:

// index.html
<div id="app"></div>
<script type="module">
  import { createApp } from 'vue'
  import Main from './Main.vue'

  createApp(Main).mount('#app')
</script>

Vite 会在本地帮你启动一个服务器,当浏览器读取到这个 html 文件之后,会在执行到 import 的时候才去向服务端发送 Main.vue 模块的请求,Vite 此时在利用内部的一系列黑魔法,包括 Vue 的 template 解析,代码的编译等等,解析成浏览器可以执行的 js 文件返回到浏览器端。

这就保证了只有在真正使用到这个模块的时候,浏览器才会请求并且解析这个模块,最大程度的做到了按需加载。

用 Vite 官网上的图来解释,传统的 bundle 模式是这样的:

传统 bundle

而基于 ESM 的构建模式则是这样的:

基于 ESM

灰色部分是暂时没有用到的路由,甚至完全不会参与构建过程,随着项目里的路由越来越多,构建速度也不会变慢。

依赖预编译

依赖预编译,其实是 Vite 2.0 在为用户启动开发服务器之前,先用 esbuild 把检测到的依赖预先构建了一遍。

也许你会疑惑,不是一直说好的 no-bundle 吗,怎么还是走启动时编译这条路线了?尤老师这么做当然是有理由的,我们先以导入 lodash-es 这个包为例。

当你用 import { debounce } from 'lodash' 导入一个命名函数的时候,可能你理想中的场景就是浏览器去下载只包含这个函数的文件。但其实没那么理想,debounce 函数的模块内部又依赖了很多其他函数,形成了一个依赖图。

当浏览器请求 debounce 的模块时,又会发现内部有 2 个 import,再这样延伸下去,这个函数内部竟然带来了 600 次请求,耗时会在 1s 左右。

lodash 请求依赖链路

这当然是不可接受的,于是尤老师想了个折中的办法,正好利用 Esbuild 接近无敌的构建速度,让你在没有感知的情况下在启动的时候预先帮你把 debounce 所用到的所有内部模块全部打包成一个传统的 js bundle

Esbuild 使用 Go 编写,并且比以 JavaScript 编写的打包器预构建依赖快 10-100 倍。

Esbuild 的速度

httpServer.listen 启动开发服务器之前,会先把这个函数劫持改写,放入依赖预构建的前置步骤,Vite 启动服务器相关代码

// server/index.ts
const listen = httpServer.listen.bind(httpServer)
httpServer.listen = (async (port: number, ...args: any[]) => {
  try {
    await container.buildStart({})
    // 这里会进行依赖的预构建
    await runOptimize()
  } catch (e) {
    httpServer.emit('error', e)
    return
  }
  return listen(port, ...args)
}) as any

runOptimize 相关的代码则在 Github optimizer 中。

首先会根据本次运行的入口,来扫描其中的依赖:

let deps: Record<string, string>, missing: Record<string, string>
if (!newDeps) {
  ;({ deps, missing } = await scanImports(config))
}

scanImports 其实就是利用 Esbuild 构建时提供的钩子去扫描文件中的依赖,收集到 deps 变量里,在扫描到入口文件(比如 index.html)中依赖的模块后,形成类似这样的依赖路径数据结构:

{
  "lodash-es": "node_modules/lodash-es"
}

之后再根据分析出来的依赖,使用 Esbuild 把它们提前打包成单文件的 bundle。

const esbuildService = await ensureService()
await esbuildService.build({
  entryPoints: Object.keys(flatIdDeps),
  bundle: true,
  format: 'esm',
  external: config.optimizeDeps?.exclude,
  logLevel: 'error',
  splitting: true,
  sourcemap: true,
  outdir: cacheDir,
  treeShaking: 'ignore-annotations',
  metafile: esbuildMetaPath,
  define,
  plugins: [esbuildDepPlugin(flatIdDeps, flatIdToExports, config)]
})

在浏览器请求相关模块时,返回这个预构建好的模块。这样,当浏览器请求 lodash-es 中的 debounce 模块的时候,就可以保证只发生一次接口请求了。

你可以理解为,这一步和 Webpack 所做的构建一样,只不过速度快了几十倍。

在预构建这个步骤中,还会对 CommonJS 模块进行分析,方便后面需要统一处理成浏览器可以执行的 ES Module

插件机制

很多同学提到 Vite,第一反应就是生态不够成熟,其他构建工具有那么多的第三方插件,提供了各种各样开箱即用的便捷功能,Vite 需要多久才能赶上呢?

Vite 从 preact 的 WMR 中得到了启发,把插件机制做成兼容 Rollup 的格式。

于是便有了这个相亲相爱的 LOGO:

Vite Rollup Plugins

目前和 vite 兼容或者内置的插件,可以查看vite-rollup-plugins

简单的介绍一下 Rollup 插件,其实插件这个东西,就是 Rollup 对外提供一些时机的钩子,还有一些工具方法,让用户去写一些配置代码,以此介入 Rollup 运行的各个时机之中。

比如在打包之前注入某些东西,或者改变某些产物结构,仅此而已。

而 Vite 需要做的就是基于 Rollup 设计的接口进行扩展,在保证 Rollup 插件兼容的可能性的同时,再加入一些 Vite 特有的钩子和属性来扩展。

举个简单的例子,@rollup/plugin-image 可以把图片模块解析成 base64 格式,它的源码其实很简单:

export default function image(opts = {}) {
  const options = Object.assign({}, defaults, opts)
  const filter = createFilter(options.include, options.exclude)

  return {
    name: 'image',

    load(id) {
      if (!filter(id)) {
        return null
      }

      const mime = mimeTypes[extname(id)]
      if (!mime) {
        // not an image
        return null
      }

      const isSvg = mime === mimeTypes['.svg']
      const format = isSvg ? 'utf-8' : 'base64'
      const source = readFileSync(id, format).replace(/[\r\n]+/gm, '')
      const dataUri = getDataUri({ format, isSvg, mime, source })
      const code = options.dom
        ? domTemplate({ dataUri })
        : constTemplate({ dataUri })

      return code.trim()
    }
  }
}

其实就是在 load 这个钩子,读取模块时,把图片转换成相应格式的 data-uri,所以 Vite 只需要在读取模块的时候,也去兼容执行相关的钩子即可。

虽然 Vite 很多行为和 Rollup 构建不同,但他们内部有很多相似的行为和时机,只要确保 Rollup 插件只使用了这些共有的钩子,就很容易做到插件的通用。

可以参考 Vite 官网文档 —— 插件部分

一般来说,只要一个 Rollup 插件符合以下标准,那么它应该只是作为一个 Vite 插件:

  • 没有使用 moduleParsed 钩子。
  • 它在打包钩子和输出钩子之间没有很强的耦合。
  • 如果一个 Rollup 插件只在构建阶段有意义,则在 build.rollupOptions.plugins 下指定即可。

Vite 后面的目标应该也是尽可能和 Rollup 相关的插件生态打通,社区也会一起贡献力量,希望 Vite 的生态越来越好。

比较

和 Vite 同时期出现的现代化构建工具还有:

Snowpack

Snowpack 和 Vite 比较相似,也是基于 ESM 来实现开发环境模块加载,但是它的构建时却是交给用户自己选择,整体的打包体验显得有点支离破碎。

而 Vite 直接整合了 Rollup,为用户提供了完善、开箱即用的解决方案,并且由于这些集成,也方便扩展更多的高级功能。

WMR

WMR 则是为 Preact 而生的,如果你在使用 Preact,可以优先考虑使用这个工具。

@web/dev-server

这个工具并未提供开箱即用的框架支持,也需要手动设置 Rollup 构建配置,不过这个项目里包含的很多工具也可以让 Vite 用户受益。

更具体的比较可以参考Vite 文档 —— 比较

总结

Vite 是一个充满魔力的现代化构建工具,尤老师也在各个平台放下狠话,说要替代 Webpack。其实 Webpack 在上个世代也是一个贡献很大的构建工具,只是由于新特性的出现,有了可以解决它的诟病的解决方案。

目前我个人觉得,一些轻型的项目(不需要一些特别奇怪的依赖构建)完全可以开始尝试 Vite,比如:

  • 各种框架、库中的展示 demo 项目。
  • 轻量级的一些企业项目。

也衷心祝福 Vite 的生态越来越好,共同迎接这个构建的新世代。

不过到那个时候,我可能还会挺怀念从前 Webpack 怀念构建的时候,那几分钟一本正经的摸鱼时刻 😆。

感谢

欢迎各路前端豪杰加我 sshsunlight 交个朋友,也欢迎随时找我投递简历。

查看原文

赞 1 收藏 0 评论 0

ssh_晨曦时梦见兮 发布了文章 · 2月1日

📝 如何写「前端简历」,能敲开字节跳动的大门?

本文由字节跳动-基础工程-APM团队合作编写,我们负责开发字节跳动的性能监控平台,还需要很多(10 个以上)优秀的同学来一起共建。

今年我们组打算建立一个字节跳动招聘社群,如果你对加入字节跳动感兴趣的话,我们可以一起进行面试相关的答疑评估简历、聊聊面试的故事、并且在你准备好的时候随时帮你内推

直接加 sshsunlight,备注「面试」,或者发送简历到 shanshihao@bytedance.com

或者在这个仓库里了解详情:https://github.com/sl1673495/bytedance-apm-group

前言

魔幻的 2020 年已经过去,金三银四很快就要到来,不少小伙伴开始考虑跳槽的事情。

我们也收到了不少的简历,有一部分同学技术很强,但是却不知道如何写出一份能够吸引面试官的简历,导致在简历筛选的过程中就被淘汰了,非常可惜。

这篇文章的目的,就是帮助你了解:怎么样的一份简历可以更容易通过面试官的筛选。

  • 适用人群:社招、校招、实习👔
  • 适用目标:进入大厂🥺

本篇文章会从一下几个角度切入,教你成为一个优秀的“简历工程师”。(😁 玩笑而已,实力最重要)

  • 不同阶段的工程师分别应该有一份怎样的简历
  • 如何规划简历结构
  • 如何避免简历中的“坑”
  • 如何优化简历的细节
  • 优秀简历的片段摘选

不同阶段的简历

校招 -1 年

这个阶段还属于成长期,更需要看重的是你的基础和热情。对于 JS 基础,计算机基础,网络通信,算法等部分的要求会相对高一些。毕竟这个阶段比较难考察你的业务项目中的沉淀,所以只能从基础部分入手考察。

  • 在学校学习,或是利用网络上的各种资料巩固自己的基础,是这个阶段的关键。
  • 在简历里用各种方式展示出你对前端的热情,让面试官看到你的潜力。
  • 多去了解社区前沿技术,关注国内外的各种技术趋势。
  • 尝试自己写一些小项目,或者是参与社区开源的项目。
  • 开始记录自己的技术博客,尝试费曼学习法,用输出倒逼你的输入。

1 年 - 4 年

这个阶段一般来说是向着独当一面的工程师发展。也是非常关键的一个时期,避免一年的经验用三年。

  • 社区里关于进阶的资料和路线有很多,平时多关注一下,补齐自己的基础知识。
  • 平时常用的框架进阶一步去使用,比如它的一些高级用法是否有所掌握,有没有试着去了解它的原理实现
  • 日常的业务开发中不局限于完成功能,是否有去思考项目结构如何设计,如何封装基础工具基础组件如何设计、开发、共享。
  • 在日常的业务开发中有没有去思考团队提效的方式,比如:

    • 接入 eslint、prettier 等代码检验、风格统一的插件。
    • 工程化的角度思考本地开发的提效,如何去进行 webpack 构建的优化,最近社区 esbuild 很火,尝试去接入一下。vite 和 snowpack 的思路很赞,能不能在新项目中运用起来等等……
    • 平常如果经常有多项目开发的需求,整理出差异和统一的部分,建立团队内部的脚手架避免重复劳动。
    • 尝试搭建CI / CD 平台,尝试搭建npm 私服维护自己公司内部的通用包。
  • 锻炼你的软技能,沟通协作也是很重要的一项能力。通过思考业务真实需求砍掉多余的需求,协调各个角色一起推进目标,也是高级工程师很重要的技能。
  • 以我们 APM 团队(Application Performance Monitor)为例,我们的业务就是性能监控相关。那么你在日常的业务中有没有关注过网站的性能指标,是否尝试过调研、接入开源的性能监控平台,是否了解性能监控 sdk 的一些原理,这些都会让我们觉得你和团队的契合度很高,当然这不是必要的,在其他方面亮眼的经历会让我们觉得你的学习能力足够 cover 这些。

4 年以上

走到这个阶段,可能就往技术专家或者管理的方向前进了。我们希望你可以把握某(多)个具体产品或者技术方向的研发工作,独立负责一个复杂度高的项目,并突破其中的关键技术。

你需要具备相当的产品视野和技术深度,需要站在更宏观的角度来看问题,也需要具备一定的跨团队协作能力;能够制定所负责方向的产品和技术规划,并推动落地,同时在研发效率、质量、资源使用率、产品渗透率等方面有一定的提高。

  • 如何负责技术调研,是否关注行业前沿趋势,根据不同场景选择最优的技术方案,能不能有拍板决定的能力和魄力。
  • 技术经验是否丰富,有没有相当的技术储备,参与过的项目类型多吗,遇到的困难都是如何解决,是否有沉淀出一套自己的方法?拒绝一年的经验重复使用。
  • 产品上是否能协助甚至主导业务目标的制定,并根据业务目标划分任务,指定排期,合理的推动项目达到预期效果。
  • 是否带过团队,或者是协作过跨团队项目,带团队有什么心得,能协调处理团队成员情绪问题吗,成员技能分布不平衡等问题如何解决。
  • 如何打造一个有技术氛围的团队,不局限于自己提升技术,而是帮助团队共同成长。

如何规划简历结构

通常来说,简历结构最好遵循一定规律。一个容易突出亮点,阅读友好的简历结构可以是这样的:

  1. 个人信息
  2. 优势总结
  3. 工作经历
  4. 项目经历

个人信息

简洁明了即可,包括你的:

  1. 姓名、电话
  2. 邮箱:最好不要是 QQ 邮箱。
  3. 学校:可选,如果你的学校还不错,可以直接列出,否则放在简历最后即可,记得写清楚入学和离校时间哦。
  4. 目前任职公司:可选,如果你目前的公司还不错,可以放这里,否则放在工作经历即可,简历中的工作经历一定要保证完整哦。
  5. 对未来团队或者业务方向的期望:可选,如果对自己未来的规划比较明确,篇幅较长的话,甚至可以单开一个章节好好聊聊,这说明你是一个对未来规划很清晰的人
  6. 照片:可选,这个需要你自己判断是否对你的简历有加分 😜,注意参考简历中的照片怎么选择?

优势总结

很多人漏掉了优势总结这一步,个人信息写完就开始急急忙忙的介绍自己的项目。

但大厂的 HR 一天可能要看上百份简历,要一个个的从候选人的项目描述中找到你的技术栈亮点,是不太现实的一件事情。

在个人信息下面附上一段优势介绍,是很容易加分的。

举个简单的社招工程师的例子,并不是说以下这些你都要有,根据个人情况参考即可,最好是每一项都可以列出简单的相关成就

  1. 🌟 熟悉以下类型项目的开发: PC Web、小程序、Electron 桌面客户端应用、React Native 开发原生应用。

    • 陈述自己用过的技术类型,第一时间表达你可以做什么事情。
    • 让 HR 第一眼看到技术匹配度,最好和投递的职位要求结合起来。
  2. 🌟 熟悉React / Vue / Angular技术栈,成就如:搭建了 React 后台系统,设计了权限管理体系。

    • 社招一般对框架掌握有一定要求,和部门的技术栈匹配也是加分项
    • 如果能熟悉原理细节则更好,可以补充上。
  3. 🌟 熟悉工程化建设,推动团队基础工程建设,成就如:推动 CI / CD 的建设,优化了构建流程。

    • 跳出浏览器的边界,探索更广阔的技术范围。
    • 说明你在团队提效的方向上探索,是个 team player。
  4. 🌟 有良好的编码习惯,对技术有追求和热情,成就如:推动了 Code Review 体系,编写内部风格指南。

    • 任何团队都希望新进来的同学不要写一些让人匪夷所思的代码。
    • 可以列举你平时学习的渠道,知乎 / 掘金 / Medium / 各种博主等等,说不定可以和志同道合的面试官多聊聊不同平台的学习心得。
    • 可以给出你的博客地址,这是一个很容易加分的项,30 分钟的面试里你能表达给面试官的东西太有限了,但是一个有内容的博客可以在面试前就为你加分很多。
  5. 🌟 社区成就,你的 Github 开源获得了多少 Star,你坚持记录了多少学习博客,你的个人网站获得了什么样的成就等等……

    • 开源社区的贡献,知名项目的 Contributor 各家公司都抢着要,当然不能只是改了个错别字提个 Issue 啥的。
    • Github 如果空空如也的话,就不要列出来了,可能反而成为扣分项。
    • 如果你的博客获得不错的点赞 / 阅读,也可以列举,这说明你有把技术原理讲明白的能力,且文字表达能力不错。
  6. 🌟 如果针对你投递的部门的技术栈,能够列出你在相关方面的经验和沉淀,这甚至可以成为能够直接进入面试的一个加分项。

工作经历

对于社招的同学来说,工作经历是简历中相当重要的一部分,它是你过去几年经历的总结和背书。

这里比较推荐按时间轴的方式,距离现在的时间从近到远的列出你工作过的公司,举个简单的例子:

腾讯

2017 - 至今

  • 带领团队完成了某某项目从零到一的建设,攻克了怎样的难题,提升了内部团队多少的效率。
  • 优化了核心项目首屏性能, 接入性能监控工具,提升了 fp, fcp 指标,整体性能提升 30%
  • 优化了核心项目的打包构建体积,利用增量构建配合缓存总体节省70% 的 CDN 资源成本
  • 搭建项目脚手架,集成框架全家桶,单元测试、集成测试解决方案,内部平台 CI / CD 的对接。

工作经历需要写的是你做成了什么,注意不是流水账一样去列举你做了什么,最好的是你给公司带来了什么样的贡献和提效。很多人在这里的宝贵位置写:“完成了一些增删改查的工作”,我一脸问号。

<div align=center></div>

一般来说大厂对于社招工程师的要求肯定是要有相对亮眼的成绩,如果你的简历和大多数简历一样千篇一律,那么就比较容易被忽略。

这里挺关键的,尽量找出工作中你独立或带头做成的比较出色的事,最好辅以数据佐证。

如何避免简历中的“坑”

  1. 可以适度美化,不要造假,诚信第一。
  2. 避免千篇一律,不要写流水账,写你 owner 了哪些事情,做成了哪些事情。
  3. 不要用奇怪的简历结构,不要漏写学校,教育经历(遇到过几次)。公司都会有简历自动识别录入系统,缺少信息会需要来回反复核对,比较麻烦。
  4. 关键的信息往前放,会让你减分的信息往后点放,心里学中的「首因效应」表明了第一印象的重要性。
  5. 多写雇主希望了解你的信息,无关紧要的信息尽量减少,比如你是社招的同学,在学校社团的经历什么的就可以淡化了。

如何优化简历的细节

  1. 注意简历文件的命名,准确的包含你的姓名-目标岗位-工作地点。

    • ❌ 张三简历.pdf、张三前端.pdf、张三实习.pdf。
    • ✅ 张三-前端-社招-上海.pdf、张三-前端-实习-北京.pdf。
  2. 用 PDF 而不是 Word,这是很多简历相关的文章中都会提到的一点,Word 的版本、兼容问题可能会导致在你电脑上看起来很漂亮的简历,在面试官电脑上打开就变得一塌糊涂,减少印象分。
  3. 注意各种技术名词的正确拼写 / 大小写

    • ❌ 熟悉 vue,vuerouter,vuex,vue-cli
    • ✅ 熟悉 Vue、vue-router,Vuex,Vue-CLI
  4. 注意简历的排版细节,可以参考写给大家看的中文排版指南

    • ❌ 我熟悉 React,擅长 Web 网页开发。
    • ✅ 我熟悉 React,擅长 Web 网页开发。(中英文之间的空格)

优秀简历片段摘录

为了让大家能更有体感的知道一份优秀的简历是什么样的,我摘选了社区里大佬们公开的简历中的一些片段:

比如黄轶老师的简历,这是一份典型的自带社区光环的大佬的简历,讲师的身份以及撰写的书籍在开头就吸引了招聘者的注意,开源项目也获得了非常高的社区赞誉,下面列举的技能的格式也是范例:

而在工作经历中,他也清晰简洁的描述出了自己在公司推动了什么事情,解决了什么难点,而不是千篇一律的流水账。

图片

比如芋头大佬在知乎回答中提到的一句话描述自己的优势:

主攻前端和 NodeJS 开发,6 年+前端开发经验,呆过大公司和小团队,从 0 组建 20 人前端 NodeJS 混合开发团队,带领团队利用最新技术解决业务快速发展过程中的各种业务场景问题。熟悉客户端开发,有多个上架 APP,有 Java 开发经验。

很清晰明了的表明了自己的优势,这一段话就涵盖了擅长的方向、带团队的经验、跨端的经验、解决问题的能力等等,非常吸引招聘者的目光。

再比如敖天羽同学的简历

图片

从这些优秀的简历中你可以发现一些共同点,向他们学习。

欢迎加入我们

我们是字节跳动-基础工程-APM团队,我们开发字节跳动全链路的应用性能管理平台,我们欢迎有才华的你加入:

  • 你可以加入平台研发方向,需要熟悉 React 或 Vue 开发后台系统。
  • 你可以做性能采集和分析,需要你有性能优化的经验,熟悉性能相关指标以及采集和优化,熟悉 Lighthouse 等工具的使用。
  • 你可以加入数据应用的方向,需要热爱数据可视化,有一定的数据 sense,使用过数据可视化类库,最好掌握 SVG、Canvas、WebGL 等前端绘图技术。

当然如果你想加入其它的团队如Web 开发引擎、跨端解决方案、Serverless 解决方案、NodeJS 方向,也可以加入社群了解。

暂时不看机会,之后有想法来字节试试的同学,也一样欢迎你加入 😁。

直接加 sshsunlight,备注「面试」,或者发邮件到 shanshihao@bytedance.com

或者在这个仓库里获取了解更多https://github.com/sl1673495/bytedance-apm-group

查看原文

赞 0 收藏 0 评论 0

ssh_晨曦时梦见兮 发布了文章 · 1月14日

Facebook 重构:抛弃 Sass / Less ,迎接原子化 CSS 时代

文章由 ssh 翻译 / 润色,原文地址

首发公众号「前端从进阶到入院」,欢迎关注,加我好友探讨。

随着 Facebook 和 Twitter 最近的产品部署,我认为一个新的趋势正在缓慢增长:Atomic CSS-in-JS

在这篇文章中,我们将看到什么是Atomic CSS(原子 CSS),它如何与 Tailwind CSS 这种实用工具优先的样式库联系起来,目前很多大公司在 React 代码仓库中使用它们。

由于我不是这方面的专家,所以我不会去深入探讨它的利弊。我只是希望能帮助你了解它的大致内容。

先抛出一个令人开心的结论,新的 CSS 编写和构建方式让 Facebook 的主页减少了 80% 的 CSS 体积

什么是原子 CSS?

你可能听说过各种 CSS 方法,如 BEM, OOCSS…

<button class="button button--state-danger">Danger button</button>

现在,人们真的很喜欢 Tailwind CSS 和它的 实用工具优先(utility-first) 的概念。这与 Functional CSS 和 Tachyon 这个库的理念非常接近。

<button
  class="bg-blue-500 hover:bg-blue-700 text-white font-bold py-2 px-4 rounded"
>
  Button
</button>

用海量的实用工具类(utility classes)组成的样式表,让我们可以在网页里大显身手。

原子 CSS 就像是实用工具优先(utility-first)CSS 的一个极端版本: 所有 CSS 类都有一个唯一的 CSS 规则。原子 CSS 最初是由 Thierry Koblentz (Yahoo!)在 2013 年挑战 CSS 最佳实践时使用的。

/* 原子 CSS */
.bw-2x {
  border-width: 2px;
}
.bss {
  border-style: solid;
}
.sans {
  font-style: sans-serif;
}
.p-1x {
  padding: 10px;
}
/* 不是原子 CSS 因为这个类包含了两个规则 */
.p-1x-sans {
  padding: 10px;
  font-style: sans-serif;
}

使用实用工具/原子 CSS,我们可以把结构层和表示层结合起来:当我们需要改变按钮颜色时,我们直接修改 HTML,而不是 CSS!

这种紧密耦合在现代 CSS-in-JS 的 React 代码库中也得到了承认,但似乎 是 CSS 世界里最先对传统的关注点分离有一些异议。

CSS 权重也不是什么问题,因为我们使用的是最简单的类选择器。

我们现在通过 html 标签来添加样式,发现了一些有趣的事儿:

  • 我们增加新功能的时候,样式表的增长减缓了。
  • 我们可以到处移动 html 标签,并且能确保样式也同样生效。
  • 我们可以删除新特性,并且确保样式也同时被删掉了。

可以肯定的缺点是,html 有点臃肿。对于服务器渲染的 web 应用程序来说可能是个缺点,但是类名中的高冗余使得 gzip 可以压缩得很好。同时它可以很好地处理之前重复的 css 规则。

一旦你的实用工具/原子 CSS 准备好了,它将不会有太大的变化或增长。可以更有效地缓存它(你可以将它附加到 vendor.css 中,重新部署的时候它也不会失效)。它还具有相当好的可移植性,可以在任意其他应用程序中使用。

实用工具/原子 CSS 的限制

实用工具/原子 CSS 看起来很有趣,但它们也带来了一些挑战。

人们通常手工编写实用工具/原子 CSS,精心制定命名约定。但是很难保证这个约定易于使用、保持一致性,而且不会随着时间的推移而变得臃肿。

这个 CSS 可以团队协作开发并保持一致性吗?它受巴士因子的影响吗?

巴士系数是软件开发中关于软件专案成员之间讯息与能力集中、未被共享的衡量指标,也有些人称作“货车因子”、“卡车因子”(lottery factor/truck factor)。一个专案或计划至少失去若干关键成员的参与(“被巴士撞了”,指代职业和生活方式变动、婚育、意外伤亡等任意导致缺席的缘由)即导致专案陷入混乱、瘫痪而无法存续时,这些成员的数量即为巴士系数。

你还需要预先开发好一个不错的实用工具/原子样式表,然后才能开始开发新功能。

如果实用工具/原子 CSS 是由别人制作的,你将不得不首先学习类命名约定(即使你知道 CSS 的一切)。这种约定是有主观性的,很可能你不喜欢它。

有时,你需要一些额外的 CSS,而实用工具/原子 CSS 并不提供这些 CSS。没有约定好的方法来提供这些一次性样式。

Tailwind 赶来支援

Tailwind 使用的方法是非常便捷的,并且解决了上述一些问题。

它通过 Utility-First 的理念来解决 CSS 的一些缺点,通过抽象出一组类名 -> 原子功能的集合,来避免你为每个 div 都写一个专有的 class,然后整个网站重复写很多重复的样式。

传统卡片样式写法:

Tailwind 卡片样式写法:

它并不是真的为所有网站提供一些唯一的实用工具 CSS,取而代之的是,它提供了一些公用的命名约定。通过一个配置文件,你可以为你的网站生成一套专属的实用工具 CSS。

ssh 注:这里原作者没有深入介绍,为什么说是一套命名约定呢而不是生成一些定死的 CSS 呢?

举几个例子让大家感受一些,Tailwind 提供了一套强大的构建系统,比如默认情况下它提供了一些响应式的断点值:

// tailwind.config.js
module.exports = {
  theme: {
    screens: {
      'sm': '640px',
      // => @media (min-width: 640px) { ... }

      'md': '768px',
      // => @media (min-width: 768px) { ... }

      'lg': '1024px',
      // => @media (min-width: 1024px) { ... }

      'xl': '1280px',
      // => @media (min-width: 1280px) { ... }
    }
  }
}

你可以随时在配置文件中更改这些断点,比如你所需要的小屏幕 sm 可能指的是更小的 320px,那么你想要在小屏幕时候采用 flex 布局,还是照常写 sm:flex,遵循同样的约定,只是这个 sm 已经被你修改成适合于项目需求的值了。

在比如说,Tailwind 里的 spacing 掌管了 margin、padding、width 等各个属性里的代表空间占用的值,默认是采用了 rem 单位,当你在配置里这样覆写后:

// tailwind.config.js
module.exports = {
  theme: {
    spacing: {
      '1': '8px',
      '2': '12px',
      '3': '16px',
      '4': '24px',
      '5': '32px',
      '6': '48px',
    }
  }
}

你再去写 h-6(height), m-2(margin), mb-4(margin-bottom),后面数字的意义就被你改变了。

也许从桌面端换到移动端项目,这个 6 代表的含义变成了 6rem,但是这套约定却深深的印在你的脑海里,成为你知识的一部分了。

Tailwind 的知识可以迁移到其他应用程序,即使它们使用的类名并不完全相同。这让我想起了 React 的「一次学习,到处编写」理念。

我看到一些用户反馈说,Tailwind 提供的类名能覆盖他们 90% - 95% 的需求。这个覆盖面似乎已经足够广了,并不需要经常写一次性的 CSS 了。

此时,你可能想知道为什么要使用原子 CSS 而不是 Tailwind CSS?强制执行原子 CSS 规则的一个规则,一个类名,有什么好处?你最终会得到更大的 html 标签和更烦人的命名约定吗?Tailwind 已经有了足够多的原子类了啊。

那么,我们是否应该放弃原子 CSS 的想法,而仅仅使用 Tailwind CSS?

Tailwind 是一个优秀的解决方案,但仍然有一些问题没有解决:

  • 需要学习一套主观的命名约定
  • CSS 规则插入顺序仍然很重要
  • 未使用的规则可以轻松删除吗?
  • 我们如何处理剩下的一次性样式?

与 Tailwind 相比,手写原子 CSS 可能不是最方便的。

和 CSS-in-JS 比较

CSS-in-JS 和实用工具/原子 CSS 有密切关系。这两种方法都提倡使用标签进行样式化。以某种方式试图模仿内联样式,这让它们有了很多相似的特性(比如在移动某些功能的时候更有信心)。

Christopher Chedeau 一直致力于推广 React 生态系统中 CSS-in-JS 理念。在很多次演讲中,他都解释了 CSS 的问题:

  1. 全局命名空间
  2. 依赖
  3. 无用代码消除
  4. 代码压缩
  5. 共享常量
  6. 非确定性(Non-Deterministic)解析
  7. 隔离

实用工具/原子 CSS 也解决了其中的一些问题,但也确实没法解决所有问题(特别是样式的非确定性解析)。

如果它们有很多相似之处,那我们能否同时使用它们呢?

探索原子 CSS-in-JS

原子 CSS-in-JS 可以被视为是“自动化的原子 CSS”:

  • 你不再需要创建一个 class 类名约定
  • 通用样式和一次性样式的处理方式是一样的
  • 能够提取页面所需要的的关键 CSS,并进行代码拆分
  • 有机会修复 JS 中 CSS 规则插入顺序的问题

我想强调两个特定的解决方案,它们最近推动了两个大规模的原子 CSS-in-JS 的部署使用,来源于以下两个演讲。

也可以看看这些库:

  • Styletron
  • Fela
  • Style-Sheet
  • cxs
  • otion
  • css-zero
  • ui-box
  • style9
  • stitches
  • catom

React-Native-Web

React-Native-Web 是一个非常有趣的库,让浏览器也可以渲染 React-Native 原语。不过我们这里并不讨论跨平台开发(演讲里有更多细节)。

作为 web 开发人员,你只需要理解 React-Native-Web 是一个常规的 CSS-in-JS 库,它自带一些原始的 React 组件。所有你写 View 组件的地方,都可以用 div 替换。

React-Native-Web 的作者是 Nicolas Gallagher,他致力于开发 Twitter 移动版。他们逐渐把它部署到移动设备上,不太确定具体时间,大概在 2017/2018 年左右。

从那以后,很多公司都在用它(美国职业足球大联盟、Flipkart、Uber、纽约时报……),但最重要的一次部署,则是由 Paul Armstrong 领导的团队在 2019 年推出的新的 Twitter 桌面应用。

Stylex

Stylex 是一个新的 CSS-in-JS 库,Facebook 团队为了 2020 年的 Facebook 应用重构而开发它。未来可能会开源,有可能用另一个名字。

值得一提的是,React-Native-Web 的作者 Nicolas Gallagher 被 Facebook 招安。所以里面出现一些熟悉的概念一点也不奇怪。

我的所有信息都来自演讲 :),还需要等待更多的细节。

可扩展性

不出所料,在 Atomic CSS 的加成下,Twitter 和 Facebook 的 CSS体积都大幅减少了,现在它的增长遵循的是对数曲线。不过,简单的应用则会多了一些 初始体积

Facebook 分享了具体数字:

  • 旧的网站仅仅首页就用了 413Kb 的 CSS
  • 新的网站整个站点只用了 74Kb,包括暗黑模式

源码和输出

这两个库的 API 看起来很相似,但也很难说,因为我们对 Stylex 了解不多。

值得强调的是,React-Native-Web 会扩展 CSS 语法糖,比如 margin: 0,会被输出为 4 个方向的 margin 原子规则。

以一个组件为例,来看看旧版传统 CSS 和新版原子 CSS 输出的区别。

<Component1 classNames="class1" /> <Component2 classNames="class2" />
.class1 {
  background-color: mediumseagreen;
  cursor: default;
  margin-left: 0px;
}
.class2 {
  background-color: thistle;
  cursor: default;
  jusify-content: flex-start;
  margin-left: 0px;
}

可以看出这两个样式中 cursormargin-left 是一模一样的,但它在输出中都会占体积。

再来看看原子 CSS 的输出:

<Component1 classNames="classA classC classD" />
<Component2 classNames="classA classB classD classE" />
class a {
  cursor: default;
}
class b {
  background-color: mediumseagreen;
}
class C {
  background-color: thistle;
}
class D {
  margin-left: 0px;
}
class E {
  jusify-content: flex-start;
}

可以看出,虽然标签上的类名变多了,但是 CSS 的输出体积会随着功能的增多而减缓增长,因为出现过一次的 CSS Rule 就不会再重复出现了。

生产环境验证

我们看看 Twitter 上的标签是什么样子的:

现在,让我们来看看新 Facebook:

很多人可能会被吓到,但是其实它很好用,而且保持了 可访问性

在 Chrome 里检查样式可能有点难,但 devtools 里就看得很清楚了:

CSS 规则顺序

与手写的工具/原子 CSS 不同,JS 库能让样式不依赖于 CSS 规则的插入顺序。

在规则冲突的情况下,生效的不是标签上 class attribute 中的最后一个类,而是样式表中最后插入的规则。

以这张图为例,我们期望的是书写在后blue 类覆盖前面的类,但实际上 CSS 会以样式表中的顺序来决定优先级,最后我们看到的是红色的文字。

在实际场景中,这些库避免在同一个元素上写入多个规则冲突的类。它们会确保标签上书写在最后的类名生效。其他的被覆盖的类名则被规律掉,甚至压根不会出现在 DOM 上。

const styles = pseudoLib.create({
  red: {color: "red"},
  blue: {color: "blue"},
});

// 只会输出 blue 相关的 CSS
<div style={[styles.red, styles.blue]}>
  Always blue!
</div>

// 只会输出 red 相关的 CSS
<div style={[styles.blue, styles.red]}>
  Always red!
</div>
注意:只有使用最严格的原子 CSS 库才能实现这种可预测的行为。

如果一个类里有多个 CSS 规则,并且只有其中的一个 CSS 规则被覆盖,那么 CSS-in-JS 库没办法进行相关的过滤,这也是原子 CSS 的优势之一。

如果一个类只有一个简单的 CSS 规则,如 margin: 0,而覆盖的是 marginTop: 10。像 margin: 0 这样的简写语法被扩展为 4 个不同的原子类,这个库就能更加轻松的过滤掉不该出现在 DOM 上的类名。

仍然喜欢 Tailwind?

只要你熟悉所有的 Tailwind 命名约定,你就可以很高效的完成 UI 编写。一旦你熟悉了这个设定,就很难回到手写每个 CSS 规则的时代了,就像你写 CSS-in-JS 那样。

没什么能阻止你在原子 CSS-in-JS 的框架上建立你自己的抽象 CSS 规则,Styled-system 就能在 CSS-in-JS 库里完成一些类似的事情。它基于一些约定创造出一些原子规则,在 emotion 中使用它试试:

import styled from '@emotion/styled';
import { typography, space, color } from 'styled-system';

const Box = styled('div')(typography, space, color);

等效于:

<Box
  fontSize={4}
  fontWeight="bold"
  p={3}
  mb={[4, 5]}
  color="white"
  bg="primary"
>
  Hello
</Box>

甚至有可能在 JS 里复用一些 Tailwind 的命名约定,如果你喜欢的话。

先看些 Tailwind 的代码:

<div className="absolute inset-0 p-4 bg-blue-500" />

我们在谷歌上随便找一个方案,比如我刚刚发现 react-native-web-tailwindcss

import { t } from 'react-native-tailwindcss';

<View style={[t.absolute, t.inset0, t.p4, t.bgBlue500]} />;

就生产力的角度而言,并没有太大的不同。甚至可以用 TS 来避免错别字。

结论

这就是我要说的关于原子 CSS-in-JS 所有内容。

我从来没有在任何大型生产部署中使用过原子 CSS、原子 CSS-in-JS 或 Tailwind。我可能在某些方面是错的,请随时纠正我。

我觉得在 React 生态系统中,原子 CSS-in-JS 是一个非常值得关注的趋势,我希望你能从这篇文章中学到一些有用的东西。

感谢阅读。

感谢

本文首发于公众号「前端从进阶到入院」,欢迎关注。

字节跳动招人啦,明年光是我们组就新增了十几个 HC,真的很缺人。北上广深杭都有,随时面试都可以,我会帮你做好全方位的内推服务!欢迎通过留言、公众号联系到我咨询 😁。

查看原文

赞 9 收藏 5 评论 6

ssh_晨曦时梦见兮 发布了文章 · 2020-09-08

陪尤雨溪一起,实现 Vuex 无限层级类型推断。(TS 4.1 新特性)

前言

前几天,TypeScript 发布了一项 4.1 版本的新特性,字符串模板类型,还没有了解过的小伙伴可以先去这篇看一下:TypeScript 4.1 新特性:字符串模板类型,Vuex 终于有救了?

本文就利用这个特性,简单实现下 Vuex 在 modules 嵌套情况下的 dispatch 字符串类型推断,先看下效果,我们有这样结构的 store

const store = Vuex({
  mutations: {
    root() {},
  },
  modules: {
    cart: {
      mutations: {
        add() {},
        remove() {},
      },
    },
    user: {
      mutations: {
        login() {},
      },
      modules: {
        admin: {
          mutations: {
            login() {},
          },
        },
      },
    },
  },
})

需要实现这样的效果,在 dispatch 的时候可选的 action 字符串类型要可以被提示出来:

store.dispatch('root')
store.dispatch('cart/add')
store.dispatch('user/login')
store.dispatch('user/admin/login')

实现

定义函数骨架

首先先定义好 Vuex 这个函数,用两个泛型把 mutationsmodules 通过反向推导给拿到:

type Store<Mutations, Modules> = {
  // 下文会实现这个 Action 类型
  dispatch(action: Action<Mutations, Modules>): void
}

type VuexOptions<Mutations, Modules> = {
  mutations: Mutations
  modules: Modules
}

declare function Vuex<Mutations, Modules>(
  options: VuexOptions<Mutations, Modules>
): Store<Mutations, Modules>

实现 Action

那么接下来的重点就是实现 dispatch(action: Action<Mutations, Modules>): void 中的 Action 了,我们的目标是把他推断成一个 'root' | 'cart/add' | 'user/login' | 'user/admin/login' 这样的联合类型,这样用户在调用 dispatch 的时候,就可以智能提示了。

Action 里首先可以简单的先把 keyof Mutations 拿到,因为根 store 下的 mutations 不需要做任何的拼接,

重头戏在于,我们需要根据 Modules 这个泛型,也就是对应结构:

modules: {
   cart: {
      mutations: {
         add() { },
         remove() { }
      }
   },
   user: {
      mutations: {
         login() { }
      },
      modules: {
         admin: {
            mutations: {
               login() { }
            },
         }
      }
   }
}

来拿到 modules 中的所有拼接后的 key

推断 Modules Keys

先提前和大伙同步好,后续泛型里的:

  • Modules 代表 { cart: { modules: {} }, user: { modules: {} } 这种多个 Module 组合的对象结构。
  • Module 代表单个子模块,比如 cart

利用

type Values<Modules> = {
  [K in keyof Modules]: Modules[K]
}[keyof Modules]

这种方式,可以轻松的把对象里的所有 类型给展开,比如

type Obj = {
  a: 'foo'
  b: 'bar'
}

type T = Values<Obj> // 'foo' | 'bar'

由于我们要拿到的是 cartuser 对应的值里提取出来的 key

所以利用上面的知识,我们编写 GetModulesMutationKeys 来获取 Modules 下的所有 key

type GetModulesMutationKeys<Modules> = {
  [K in keyof Modules]: GetModuleMutationKeys<Modules[K], K>
}[keyof Modules]

首先利用 K in keyof Modules 来拿到所有的 key,这样我们就可以拿到 cartuser 这种单个 Module,并且传入给 GetModuleMutationKeys 这个类型,K 也要一并传入进去,因为我们需要利用 cartuser 这些 key 来拼接在最终得到的类型前面。

推断单个 Module Keys

接下来实现 GetModuleMutationKeys,分解一下需求,首先单个 Module 是这样子的:

cart: {
   mutations: {
      add() { },
      remove() { }
   }
},

那么拿到它的 Mutations 后,我们只需要去拼接 cart/addcart/remove 即可,那么如何拿到一个对象类型中的 mutations

我们用 infer 来取:

type GetMutations<Module> = Module extends { mutations: infer M } ? M : never

然后通过 keyof GetMutations<Module>,即可轻松拿到 'add' | 'remove' 这个类型,我们再实现一个拼接 Key 的类型,注意这里就用到了 TS 4.1 的字符串模板类型了

type AddPrefix<Prefix, Keys> = `${Prefix}/${Keys}`

这里会自动把联合类型展开并分配,${'cart'}/${'add' | 'remove'} 会被推断成 'cart/add' | 'cart/remove',不过由于我们传入的是 keyof GetMutations<Module> 它还有可能是 symbol | number 类型,所以用 Keys & string 来取其中的 string 类型,这个技巧也是老爷子在 Template string types MR 中提到的:

Above, a keyof T & string intersection is required because keyof T could contain symbol types that cannot be transformed using template string types.
type AddPrefix<Prefix, Keys> = `${Prefix & string}/${Keys & string}`

那么,利用 AddPrefix<Key, keyof GetMutations<Module>> 就可以轻松的把 cart 模块下的 mutations 拼接出来了。

推断嵌套 Module Keys

cart 模块下还可能有别的 Modules,比如这样:

cart: {
   mutations: {
      add() { },
      remove() { }
   }
   modules: {
      subCart: {
          mutations: {
          add() { },
        }
      }
   }
},

其实很简单,我们刚刚已经定义好了从 Modules 中提取 Keys 的工具类型,也就是 GetModulesMutationKeys,只需要递归调用即可,不过这里我们需要做一层预处理,把 modules 不存在的情况给排除掉:

type GetModuleMutationKeys<Module, Key> =
  // 这里直接拼接 key/mutation
  | AddPrefix<Key, keyof GetMutations<Module>>
  // 这里对子 modules 做 keys 的提取
  | GetSubModuleKeys<Module, Key>

利用 extends 去判断类型结构,对不存在 modules 的结构直接返回 never,再用 infer 去提取出 Modules 的结构,并且把前一个模块的 key 拼接在刚刚写好的 GetModulesMutationKeys 返回的结果之前:

type GetSubModuleKeys<Module, Key> = Module extends { modules: infer SubModules }
  ? AddPrefix<Key, GetModulesMutationKeys<SubModules>>
  : never

以这个 cart 模块为例,分解一下每个工具类型得到的结果:

cart: {
   mutations: {
      add() { },
      remove() { }
   }
   modules: {
      subCart: {
          mutations: {
          add() { },
        }
      }
   }
},

type GetModuleMutationKeys<Module, Key> =
    // 'cart/add' | 'cart | remove'
    AddPrefix<Key, keyof GetMutations<Module>> |
    // 'cart/subCart/add'
    GetSubModuleKeys<Module, Key>

type GetSubModuleKeys<Module, Key> = Module extends { modules: infer SubModules }
   ? AddPrefix<
       // 'cart'
       Key,
       // 'subCart/add'
       GetModulesMutationKeys<SubModules>
   >
   : never

这样,就巧妙的利用递归把无限层级的 modules 拼接实现了。

完整代码

type GetMutations<Module> = Module extends { mutations: infer M } ? M : never

type AddPrefix<Prefix, Keys> = `${Prefix & string}/${Keys & string}`

type GetSubModuleKeys<Module, Key> = Module extends { modules: infer SubModules }
   ? AddPrefix<Key, GetModulesMutationKeys<SubModules>>
   : never

type GetModuleMutationKeys<Module, Key> = AddPrefix<Key, keyof GetMutations<Module>> | GetSubModuleKeys<Module, Key>

type GetModulesMutationKeys<Modules> = {
   [K in keyof Modules]: GetModuleMutationKeys<Modules[K], K>
}[keyof Modules]

type Action<Mutations, Modules> = keyof Mutations | GetModulesMutationKeys<Modules>

type Store<Mutations, Modules> = {
   dispatch(action: Action<Mutations, Modules>): void
}

type VuexOptions<Mutations, Modules> = {
   mutations: Mutations,
   modules: Modules
}

declare function Vuex<Mutations, Modules>(options: VuexOptions<Mutations, Modules>): Store<Mutations, Modules>

const store = Vuex({
   mutations: {
      root() { },
   },
   modules: {
      cart: {
         mutations: {
            add() { },
            remove() { }
         }
      },
      user: {
         mutations: {
            login() { }
         },
         modules: {
            admin: {
               mutations: {
                  login() { }
               },
            }
         }
      }
   }
})

store.dispatch("root")
store.dispatch("cart/add")
store.dispatch("user/login")
store.dispatch("user/admin/login")

前往 TypeScript Playground 体验。

结语

这个新特性给 TS 库开发的作者带来了无限可能性,有人用它实现了 URL Parser 和 HTML parser,有人用它实现了 JSON parse 甚至有人用它实现了简单的正则,这个特性让类型体操的爱好者以及框架的库作者可以进一步的大展身手,期待他们写出更加强大的类型库来方便业务开发的童鞋吧~

谢谢大家

关注公众号「前端从进阶到入院」,后台回复 TS,送几本「TypeScript项目实战」了,非常棒的一本实战书。

查看原文

赞 9 收藏 5 评论 5

ssh_晨曦时梦见兮 赞了文章 · 2020-08-24

详解,从后端导出文件到前端(Blob)下载过程

前言

对于不是从事音视频方面的同学来说,很多情况下都是通过 window.location.href 来下载文件。这种方式,一般是前后端的登录态是基于 Cookie + Session 的方式,由于浏览器默认会将本地的 cookie 塞到 HTTP 请求首部字段的 Set-Cookie 中,从而实现来带用户的 SessionId,所以,我们也就可以用 window.location.href 来打开一个链接下载文件。

当然,还有一种情况,不需要登录态的校验(比较che)。

众所周知,还有另一种登录态的处理方式 JWT (JSON Web Token)。这种情况,一般会要求,前端在下载文件的时候在请求首部字段中添加 Token 首部字段。那么,这样一来,我们就不能直接通过 window.location.href 来下载文件。

不过,幸运的是我们有 Blob,它是浏览器端的类文件对象,基于二进制数据,我们可以通过它来优雅地处理文件下载,不限于音视频、PDF、Excel 等等。所以,今天我们就从后端导出文件到 HTTP 协议、非简单请求下的预检请求、以及最后的 Blob 处理文件,了解一番何为其然、如何使其然?

后端(Koa2)导出文件(Excel)

首先,我们从后端导出文件讲起。这里,我选择 Koa2 来实现 Excel 的导出,然后搭配 node-xlsx 这个库,从而实现 Excel 的二进制数据的导出。它看起来会是这样:

const xlsx = require("node-xlsx")

router.get("/excelExport", async function (ctx, next) {
    // 数据查询的结果
    const res = [
      ["name", "age"],
      ["五柳", "22"],
    ];
    // 生成 excel 对应的 buffer 二进制文件
    const excelFile = xlsx.build([{name: "firstSheet", data: res}])
    // 设置文件名相关的响应首部字段
    ctx.set("Content-Disposition", "attachment;filename=test.xlsx;filename*=UTF-8")
    // 返回给前端
    ctx.body = buffer;
  });
这里就不对数据库查询做展开,只是模拟了一下查询后的结果 res

然后我们用浏览器请求一下这个接口,我们会看到在响应首部(Response Headers)字段中的 Content-Typeapplication/octet-stream,它是二进制文件默认的 MIME 类型。

Connection: keep-alive
Content-Disposition: attachment;filename=test.xlsx;filename*=UTF-8
Content-Length: 14584
Content-Type: application/octet-stream
Date: Sun, 23 Aug 2020 11:33:16 GMT
MIME 类型,即 Multipurpose Internal Mail Extension,用于表示文件、文档或字节流。

HTTP 协议认识二进制文件流

如果,我们没有参与后端返回 Excel 的这个过程。那么,HTTP 协议可以帮助我们减少交流,并且懂得我们前端需要如何进行相应的处理。这里会涉及到三个 HTTP 实体首部字段:

  • Content-Type
  • Content-Length
  • Content-Disposition

那么,我们分别来看看它们在 HTTP 文件传输过程中的特殊意义

Content-Type

Content-Type 我想这个老生常谈的实体首部字段,大家不会陌生。它用来说明实体主体内容对象的媒体类型,遵循 type/subtype 的结构。常见的有 text/plaintext/htmlimage/jpegapplication/jsonapplication/javascript 等等。

在我们这里二进制文件,它没有特定的 subtype,即都是以 application/octet-stream 作为 Content-Type 的值。即如上面我们所看到:

Content-Type: application/octet-stream
所以,只要我们熟悉 Content-Type,那么在开发中的交流成本就可以减少。

Content-Length

Content-Length 又是一个眼熟的实体首部字段,它表示传输的实体主体的大小,单位为字节。而在我们这个栗子,表示传输的 Excel 二进制文件大小为 14584

Content-Disposition

Content-Disposition 这个实体首部字段,我想前端同学大多数是会有陌生感。它用来表示实体主体内容是用于显示在浏览器内作为文件下载。它对应的 value 有这么几个内容:

  • formdata,表示实体主体是 formdata 的形式。
  • inline,表示实体主体内容显示在浏览器内。
  • attachment,表示实体主体内容作为文件下载。
  • filename,表示文件编码格式或文件名,例如 filename*=UTF-8 表示文件的编码,filename=test.xlsx 表示下载时的文件名。
  • name,表示 formdata 上传文件时,对应 typefileinputname 值,例如 <input type="file" name="upload" />,此时对应的 name 则为 upload
需要注意的是,对于 Content-Dispositionformdata 它仅仅是一个信息提示的作用,并不是实现实体主体内容为 formdata,这是 Content-Type 负责的。

那么回到,今天这个栗子,它的 Content-Disposition 为:

Content-Disposition: attachment;filename=test.xlsx;filename*=UTF-8

所以,现在我们知道它主要做了这么几件事:

  • 告知浏览器需要将二进制文件作为附件下载
  • 附件的文件名为 test.xlsx
  • 附件对应的编码为 UTF-8

Blob 优雅地处理文件(Excel)下载

为什么说是优雅?因为,Blob 它可以处理很多类型文件,并且是受控的,你可以控制从接收到二进制文件流、到转化为 Blob、再到用其他 API 来实现下载文件。因为,如果是 window.location.href 下载文件,诚然也可以达到一样的效果,但是你无法在拿到二进制文件流到下载文件之间做个性化的操作。

并且,在复杂情况下的文件处理,Blob 必然是首要选择,例如分片上传下载音视频文件的拼接等等。所以,在这里我也推崇大家使用 Blob 处理文件下载。

并且,值得一提的是 XMLHttpRequest 默认支持了设置 responseType,通过设置 reposponseTypeblob,可以直接将拿到的二进制文件转化为 Blob

当然 axios 也支持设置 reponseType,并且我们也可以设置 responseTypearraybuffer,但是我想没这个必要拐弯抹角。

然后,在拿到二进制文件对应的 Blob 对象后,我们需要进行下载操作,这里我们来认识一下这两种使用 Blob 实现文件下载的方式。

URL.createObjectURL

在浏览器端,我们要实现下载文件,无非就是借助 a 标签来指向一个文件的下载地址。所以 window.location.href 的本质也是这样。也因此,在我们拿到了二进制文件对应的 Blob 对象后,我们需要为这个 Blob 对象创建一个指向它的下载地址 URL

URL.createObjectURL 方法则可以实现接收 FileBlob 对象,创建一个 DOMString,包含了对应的 URL,指向 BlobFile 对象,它看起来会是这样:

"blob:http://localhost:8080/a48aa254-866e-4c66-ba79-ae71cf5c1cb3"

完整的使用 BlobURL.createObjectURL 下载文件的 util 函数:

export const downloadFile = (fileStream, name, extension, type = "") => {
  const blob = new Blob([fileStream], {type});
  const fileName = `${name}.${extension}`;
  if ("download" in document.createElement("a")) {
    const elink = document.createElement("a");
    elink.download = fileName;
    elink.style.display = "none";
    elink.href = URL.createObjectURL(blob);
    document.body.appendChild(elink);
    elink.click();
    URL.revokeObjectURL(elink.href);
    document.body.removeChild(elink);
  } else {
    navigator.msSaveBlob(blob, fileName);
  }
};

FileReader

同样地,FileReader 对象也可以使得我们对 Blob 对象生成一个下载地址 URL,它和 URL.createObject 一样可以接收 FileBlob 对象。

这个过程,主要由两个函数完成 readAsDataURLonload,前者用于将 BlobFile 对象转为对应的 URL,后者用于接收前者完成后的 URL,它会在 e.target.result 上。

完整的使用 BlobFileReader 下载文件的 util 函数:

const readBlob2Url  =  (blob, type) =>{
  return new Promise(resolve => {
    const reader = new FileReader()
    reader.onload = (e) => {
      resolve(e.target.result)
    }
    reader.readAsDataURL(blob)
  })
}

写在最后

如果,仅仅是用一个 Blob 这个浏览器 API 处理文件下载,可能带给你的收益并没有多少。但是,通过了解从后端文件导出、HTTP 协议、Blob 处理文件下载这整个过程,就可以构建一个完整的技术思维体系,从而获取其中的收益。唯有知其然,方能使其然。 这也是前段时间看到的很符合我们作为一个不断学习的从业者的态度。也因此,良好的技术知识储备,能让我们拥有很好的编程思维和设计思想。

文章对应的 DEMO,我已经上传到 GitHub 上了,有兴趣的同学可以去 clone 下来了解。

往期文章回顾

❤️爱心三连击

通过阅读,如果你觉得有收获的话,可以爱心三连击!!!

查看原文

赞 33 收藏 28 评论 4

ssh_晨曦时梦见兮 发布了文章 · 2020-08-24

Vue3 + TS 实现递归菜单组件

前言

小伙伴们好久不见,最近刚入职新公司,需求排的很满,平常是实在没时间写文章了,更新频率会变得比较慢。

周末在家闲着无聊,突然小弟过来紧急求助,说是面试腾讯的时候,对方给了个 Vue 的递归菜单要求实现,回来找我复盘。

正好这周是小周,没想着出去玩,就在家写写代码吧,我看了一下需求,确实是比较复杂,需要利用好递归组件,正好趁着这个机会总结一篇 Vue3 + TS 实现递归组件的文章。

需求

可以先在 Github Pages 中预览一下效果。

需求是这样的,后端会返回一串可能有无限层级的菜单,格式如下:

[
  {
    id: 1,
    father_id: 0,
    status: 1,
    name: '生命科学竞赛',
    _child: [
      {
        id: 2,
        father_id: 1,
        status: 1,
        name: '野外实习类',
        _child: [{ id: 3, father_id: 2, status: 1, name: '植物学' }],
      },
      {
        id: 7,
        father_id: 1,
        status: 1,
        name: '科学研究类',
        _child: [
          { id: 8, father_id: 7, status: 1, name: '植物学与植物生理学' },
          { id: 9, father_id: 7, status: 1, name: '动物学与动物生理学' },
          { id: 10, father_id: 7, status: 1, name: '微生物学' },
          { id: 11, father_id: 7, status: 1, name: '生态学' },
        ],
      },
      { id: 71, father_id: 1, status: 1, name: '添加' },
    ],
  },
  {
    id: 56,
    father_id: 0,
    status: 1,
    name: '考研相关',
    _child: [
      { id: 57, father_id: 56, status: 1, name: '政治' },
      { id: 58, father_id: 56, status: 1, name: '外国语' },
    ],
  },
]
  1. 每一层的菜单元素如果有 _child 属性,这一项菜单被选中以后就要继续展示这一项的所有子菜单,预览一下动图:

Kapture 2020-08-21 at 18 49 46

  1. 并且点击其中的任意一个层级,都需要把菜单的 完整的 id 链路 传递到最外层,给父组件请求数据用。比如点击了 科学研究类。那么向外 emit 的时候还需要带上它的第一个子菜单 植物学与植物生理学id,以及它的父级菜单 生命科学竞赛 的 id,也就是 [1, 7, 8]
  2. 每一层的样式还可以自己定制。

实现

这很显然是一个递归组件的需求,在设计递归组件的时候,我们要先想清楚数据到视图的映射。

在后端返回的数据中,数组的每一层可以分别对应一个菜单项,那么数组的层则就对应视图中的一行,当前这层的菜单中,被点击选中 的那一项菜单的 child 就会被作为子菜单数据,交给递归的 NestMenu 组件,直到某一层的高亮菜单不再有 child,则递归终止。

image

由于需求要求每一层的样式可能是不同的,所以再每次调用递归组件的时候,我们都需要从父组件的 props 中拿到一个 depth 代表层级,并且把这个 depth + 1 继续传递给递归的 NestMenu 组件。

重点主要就是这些,接下来编码实现。

先看 NestMenu 组件的 template 部分的大致结构:

<template>
  <div class="wrap">
    <div class="menu-wrap">
      <div
        class="menu-item"
        v-for="menuItem in data"
      >{{menuItem.name}}</div>
    </div>
    <nest-menu
      :key="activeId"
      :data="subMenu"
      :depth="depth + 1"
    ></nest-menu>
  </div>
</template>

和我们预想设计中的一样, menu-wrap 代表当前菜单层, nest-menu 则就是组件本身,它负责递归的渲染子组件。

首次渲染

在第一次获取到整个菜单的数据的时候,我们需要先把每层菜单的选中项默认设置为第一个子菜单,由于它很可能是异步获取的,所以我们最好是 watch 这个数据来做这个操作。

// 菜单数据源发生变化的时候 默认选中当前层级的第一项
const activeId = (ref < number) | (null > null)

watch(
  () => props.data,
  (newData) => {
    if (!activeId.value) {
      if (newData && newData.length) {
        activeId.value = newData[0].id
      }
    }
  },
  {
    immediate: true,
  }
)

现在我们从最上层开始讲起,第一层的 activeId 被设置成了 生命科学竞赛 的 id,注意我们传递给递归子组件的 data ,也就是 生命科学竞赛child,是通过 subMenu 获取到的,它是一个计算属性:

const getActiveSubMenu = () => {
  return data.find(({ id }) => id === activeId.value)._child
}
const subMenu = computed(getActiveSubMenu)

这样,就拿到了 生命科学竞赛child,作为子组件的数据传递下去了。

点击菜单项

回到之前的需求设计,在点击了菜单项后,无论点击的是哪层,都需要把完整的 id 链路通过 emit 传递到最外层去,所以这里我们需要多做一些处理:

/**
 * 递归收集子菜单第一项的 id
 */
const getSubIds = (child) => {
  const subIds = []
  const traverse = (data) => {
    if (data && data.length) {
      const first = data[0]
      subIds.push(first.id)
      traverse(first._child)
    }
  }
  traverse(child)
  return subIds
}

const onMenuItemClick = (menuItem) => {
  const newActiveId = menuItem.id
  if (newActiveId !== activeId.value) {
    activeId.value = newActiveId
    const child = getActiveSubMenu()
    const subIds = getSubIds(child)
    // 把子菜单的默认第一项 ids 也拼接起来 向父组件 emit
    context.emit('change', [newActiveId, ...subIds])
  }
}

由于我们之前定的规则是,点击了新的菜单以后默认选中子菜单的第一项,所以这里我们也递归去找子菜单数据里的第一项,放到 subIds 中,直到最底层。

注意这里的 context.emit("change", [newId, ...subIds]);,这里是把事件向上 emit,如果这个菜单是中间层级的菜单,那么它的父组件也是 NestMenu,我们需要在父层级递归调用 NestMenu 组件的时候监听这个 change 事件。

<nest-menu
    :key="activeId"
    v-if="activeId !== null"
    :data="getActiveSubMenu()"
    :depth="depth + 1"
    @change="onSubActiveIdChange"
></nest-menu>

在父层级的菜单接受到了子层级的菜单的 change 事件后,需要怎么做呢?没错,需要进一步的再向上传递:

const onSubActiveIdChange = (ids) => {
  context.emit('change', [activeId.value].concat(ids))
}

这里就只需要简单的把自己当前的 activeId 拼接到数组的最前面,再继续向上传递即可。

这样,任意一层的组件点击了菜单后,都会先用自己的 activeId 拼接好所有子层级的默认 activeId,再一层层向上 emit。并且向上的每一层父菜单都会把自己的 activeId 拼在前面,就像接力一样。

最后,我们在应用层级的组件里,就可以轻松的拿到完整的 id 链路:

<template>
  <nest-menu :data="menu" @change="activeIdsChange" />
</template>

export default {
  methods: {
    activeIdsChange(ids) {
      this.ids = ids;
      console.log("当前选中的id路径", ids);
  },
},

样式区分

由于我们每次调用递归组件的时候,都会把 depth + 1,那么就可以通过把这个数字拼接到类名后面来实现样式区分了。

<template>
  <div class="wrap">
    <div class="menu-wrap" :class="`menu-wrap-${depth}`">
      <div class="menu-item">{{menuItem.name}}</div>
    </div>
    <nest-menu />
  </div>
</template>

<style>
.menu-wrap-0 {
  background: #ffccc7;
}

.menu-wrap-1 {
  background: #fff7e6;
}

.menu-wrap-2 {
  background: #fcffe6;
}
</style>

默认高亮

上面的代码写完后,应对没有默认值时的需求已经足够了,这时候面试官说,产品要求这个组件能通过传入任意一个层级的 id 来默认展示高亮。

其实这也难不倒我们,稍微改造一下代码,在父组件里假设我们通过 url 参数或者任意方式拿到了一个 activeId,先通过深度优先遍历的方式查找到这个 id 的所有父级。

const activeId = 7

const findPath = (menus, targetId) => {
  let ids

  const traverse = (subMenus, prev) => {
    if (ids) {
      return
    }
    if (!subMenus) {
      return
    }
    subMenus.forEach((subMenu) => {
      if (subMenu.id === activeId) {
        ids = [...prev, activeId]
        return
      }
      traverse(subMenu._child, [...prev, subMenu.id])
    })
  }

  traverse(menus, [])

  return ids
}

const ids = findPath(data, activeId)

这里我选择在递归的时候带上上一层的 id,在找到了目标 id 以后就能轻松的拼接处完整的父子 id 数组。

然后我们把构造好的 ids 作为 activeIds 传递给 NestMenu,此时这时候 NestMenu 就要改变一下设计,成为一个「受控组件」,它的渲染状态是受我们外层传递的数据控制的。

所以我们需要在初始化参数的时候改变一下取值逻辑,优先取 activeIds[depth] ,并且在点击菜单项的时候,要在最外层的页面组件中,接收到 change 事件时,把 activeIds 的数据同步改变。这样继续传递下去才不会导致 NestMenu 接收到的数据混乱。

<template>
  <nest-menu :data="data" :defaultActiveIds="ids" @change="activeIdsChange" />
</template>

NestMenu 初始化的时候,对有默认值的情况做一下处理,优先使用数组中取到的 id 值。

setup(props: IProps, context) {
  const { depth = 0, activeIds } = props;

  /**
   * 这里 activeIds 也可能是异步获取到的 所以用 watch 保证初始化
   */
  const activeId = ref<number | null | undefined>(null);
  watch(
    () => activeIds,
    (newActiveIds) => {
      if (newActiveIds) {
        const newActiveId = newActiveIds[depth];
        if (newActiveId) {
          activeId.value = newActiveId;
        }
      }
    },
    {
      immediate: true,
    }
  );
}

这样,如果 activeIds 数组中取不到的话,默认还是 null,在 watch 到菜单数据变化的逻辑中,如果 activeIdnull 的话,会被初始化为第一个子菜单的 id

watch(
  () => props.data,
  (newData) => {
    if (!activeId.value) {
      if (newData && newData.length) {
        activeId.value = newData[0].id
      }
    }
  },
  {
    immediate: true,
  }
)

在最外层页面容器监听到 change 事件的时候,要把数据源同步一下:

<template>
  <nest-menu :data="data" :activeIds="ids" @change="activeIdsChange" />
</template>

<script>
import { ref } from "vue";

export default {
  name: "App",
  setup() {
    const activeIdsChange = (newIds) => {
      ids.value = newIds;
    };

    return {
      ids,
      activeIdsChange,
    };
  },
};
</script>

如此一来,外部传入 activeIds 的时候,就可以控制整个 NestMenu 的高亮选中逻辑了。

数据源变动引发的 bug。

这时候,面试官对着你的 App 文件稍作改动,然后演示了这样一个 bug:

App.vue 的 setup 函数中加了这样的一段逻辑:

onMounted(() => {
  setTimeout(() => {
    menu.value = [data[0]].slice()
  }, 1000)
})

也就是说,组件渲染完成后过了一秒,菜单的最外层只剩下一项了,这时候面试官在一秒之内点击了最外层的第二项,这个组件在数据源改变之后,会报错:

Kapture 2020-08-23 at 18 30 44

这是因为数据源已经改变了,但是组件内部的 activeId 状态依然停留在了一个已经不存在了的 id 上。

这会导致 subMenu 这个 computed 属性在计算时出错。

我们对 watch data 观测数据源的这段逻辑稍加改动:

watch(
  () => props.data,
  (newData) => {
    if (!activeId.value) {
      if (newData && newData.length) {
        activeId.value = newData[0].id
      }
    }
    // 如果当前层级的 data 中遍历无法找到 `activeId` 的值 说明这个值失效了
    // 把它调整成数据源中第一个子菜单项的 id
    if (!props.data.find(({ id }) => id === activeId.value)) {
      activeId.value = props.data?.[0].id
    }
  },
  {
    immediate: true,
    // 在观测到数据变动之后 同步执行 这样会防止渲染发生错乱
    flush: 'sync',
  }
)

Kapture 2020-08-23 at 18 34 35

注意这里的 flush: "sync" 很关键,Vue3 对于 watch 到数据源变动之后触发 callback 这一行为,默认是以 post 也就是渲染之后再执行的,但是在当前的需求下,如果我们用错误的 activeId 去渲染,就会直接导致报错了,所以我们需要手动把这个 watch 变成一个同步行为。

这下再也不用担心数据源变动导致渲染错乱了。

完整代码

App.vue

<template>
  <nest-menu :data="data" :activeIds="ids" @change="activeIdsChange" />
</template>

<script>
import { ref } from "vue";
import NestMenu from "./components/NestMenu.vue";
import data from "./menu.js";
import { getSubIds } from "./util";

export default {
  name: "App",
  setup() {
    // 假设默认选中 id 为 7
    const activeId = 7;

    const findPath = (menus, targetId) => {
      let ids;

      const traverse = (subMenus, prev) => {
        if (ids) {
          return;
        }
        if (!subMenus) {
          return;
        }
        subMenus.forEach((subMenu) => {
          if (subMenu.id === activeId) {
            ids = [...prev, activeId];
            return;
          }
          traverse(subMenu._child, [...prev, subMenu.id]);
        });
      };

      traverse(menus, []);

      return ids;
    };

    const ids = ref(findPath(data, activeId));

    const activeIdsChange = (newIds) => {
      ids.value = newIds;
      console.log("当前选中的id路径", newIds);
    };

    return {
      ids,
      activeIdsChange,
      data,
    };
  },
  components: {
    NestMenu,
  },
};
</script>

NestMenu.vue

<template>
  <div class="wrap">
    <div class="menu-wrap" :class="`menu-wrap-${depth}`">
      <div
        class="menu-item"
        v-for="menuItem in data"
        :class="getActiveClass(menuItem.id)"
        @click="onMenuItemClick(menuItem)"
        :key="menuItem.id"
      >{{menuItem.name}}</div>
    </div>
    <nest-menu
      :key="activeId"
      v-if="subMenu && subMenu.length"
      :data="subMenu"
      :depth="depth + 1"
      :activeIds="activeIds"
      @change="onSubActiveIdChange"
    ></nest-menu>
  </div>
</template>

<script lang="ts">
import { watch, ref, onMounted, computed } from "vue";
import data from "../menu";

interface IProps {
  data: typeof data;
  depth: number;
  activeIds?: number[];
}

export default {
  name: "NestMenu",
  props: ["data", "depth", "activeIds"],
  setup(props: IProps, context) {
    const { depth = 0, activeIds, data } = props;

    /**
     * 这里 activeIds 也可能是异步获取到的 所以用 watch 保证初始化
     */
    const activeId = ref<number | null | undefined>(null);
    watch(
      () => activeIds,
      (newActiveIds) => {
        if (newActiveIds) {
          const newActiveId = newActiveIds[depth];
          if (newActiveId) {
            activeId.value = newActiveId;
          }
        }
      },
      {
        immediate: true,
        flush: 'sync'
      }
    );

    /**
     * 菜单数据源发生变化的时候 默认选中当前层级的第一项
     */
    watch(
      () => props.data,
      (newData) => {
        if (!activeId.value) {
          if (newData && newData.length) {
            activeId.value = newData[0].id;
          }
        }
        // 如果当前层级的 data 中遍历无法找到 `activeId` 的值 说明这个值失效了
        // 把它调整成数据源中第一个子菜单项的 id
        if (!props.data.find(({ id }) => id === activeId.value)) {
          activeId.value = props.data?.[0].id;
        }
      },
      {
        immediate: true,
        // 在观测到数据变动之后 同步执行 这样会防止渲染发生错乱
        flush: "sync",
      }
    );

    const onMenuItemClick = (menuItem) => {
      const newActiveId = menuItem.id;
      if (newActiveId !== activeId.value) {
        activeId.value = newActiveId;
        const child = getActiveSubMenu();
        const subIds = getSubIds(child);
        // 把子菜单的默认第一项 ids 也拼接起来 向父组件 emit
        context.emit("change", [newActiveId, ...subIds]);
      }
    };
    /**
     * 接受到子组件更新 activeId 的同时
     * 需要作为一个中介告知父组件 activeId 更新了
     */
    const onSubActiveIdChange = (ids) => {
      context.emit("change", [activeId.value].concat(ids));
    };
    const getActiveSubMenu = () => {
      return props.data?.find(({ id }) => id === activeId.value)._child;
    };
    const subMenu = computed(getActiveSubMenu);

    /**
     * 样式相关
     */
    const getActiveClass = (id) => {
      if (id === activeId.value) {
        return "menu-active";
      }
      return "";
    };

    /**
     * 递归收集子菜单第一项的 id
     */
    const getSubIds = (child) => {
      const subIds = [];
      const traverse = (data) => {
        if (data && data.length) {
          const first = data[0];
          subIds.push(first.id);
          traverse(first._child);
        }
      };
      traverse(child);
      return subIds;
    };

    return {
      depth,
      activeId,
      subMenu,
      onMenuItemClick,
      onSubActiveIdChange,
      getActiveClass,
    };
  },
};
</script>

<style>
.wrap {
  padding: 12px 0;
}

.menu-wrap {
  display: flex;
  flex-wrap: wrap;
}

.menu-wrap-0 {
  background: #ffccc7;
}

.menu-wrap-1 {
  background: #fff7e6;
}

.menu-wrap-2 {
  background: #fcffe6;
}

.menu-item {
  margin-left: 16px;
  cursor: pointer;
  white-space: nowrap;
}

.menu-active {
  color: #f5222d;
}
</style>

源码地址

https://github.com/sl1673495/...

总结

一个递归的菜单组件,说简单也简单,说难也有它的难点。如果我们不理解 Vue 的异步渲染和观察策略,可能中间的 bug 就会困扰我们许久。所以适当学习原理还是挺有必要的。

在开发通用组件的时候,一定要注意数据源的传入时机(同步、异步),对于异步传入的数据,要利用好 watch 这个 API 去观测变动,做相应的操作。并且要考虑数据源的变化是否会和组件内原来保存的状态冲突,在适当的时机要做好清理操作。

另外留下一个小问题,我在 NestMenu 组件 watch 数据源的时候,选择这样去做:

watch((() => props.data);

而不是解构后再去观测:

const { data } = props;
watch(() => data);

这两者之间有区别吗?这又是一道考察深度的面试题。

开发优秀组件的路还是很漫长的,欢迎各位也在评论区留下你的看法~

招聘

字节跳动内推啦,Client Infrastructure是字节跳动终端基础架构团队,面向字节跳动全业务线的移动端、Web、Desktop等终端业务的基础架构部门,为公司业务的高效迭代、质量保证、研发效率和体验提供平台、工具、框架和专项技术能力支撑。
研发领域包括但不限于APP框架和基础组件、研发体系、自动化测试、APM、跨平台框架、端智能解决方案、Web开发引擎、Node.js基建以及下一代移动开发技术的预研等,目前在北上广深杭五地均设有研发中心。

上海的同学点这里一键投递,来我们部门和我做同事吧~

https://job.toutiao.com/s/JhR...

其他地区(北上广深杭)也可以自己搜索你想要的业务线和工作地点,通过我的下方内推链接直接投递即可。

https://job.toutiao.com/s/JhR...

校招的同学看这里:

投递链接: https://job.toutiao.com/s/JhR...

❤️ 感谢大家

1.如果本文对你有帮助,就点个赞支持下吧,你的「赞」是我创作的动力。

2.关注公众号「前端从进阶到入院」即可加我好友,我拉你进「前端进阶交流群」,大家一起共同交流和进步。

查看原文

赞 15 收藏 11 评论 4

ssh_晨曦时梦见兮 发布了文章 · 2020-07-21

React Hook + TS 购物车实战(性能优化、闭包陷阱、自定义hook)

前言

本文由一个基础的购物车需求展开,一步一步带你深入理解 React Hook 中的坑和优化

通过本篇文章你可以学到:

✨React Hook + TypeScript 编写业务组件的实践

✨ 如何利用 React.memo优化性能

✨ 如何避免 Hook 带来的闭包陷阱

✨ 如何抽象出简单好用的自定义hook

预览地址

https://sl1673495.github.io/r...

代码仓库

本文涉及到的代码已经整理到 github 仓库中,用 cra 搭建了一个示例工程,关于性能优化的部分可以打开控制台查看重渲染的情况。

https://github.com/sl1673495/...

需求分解

作为一个购物车需求,那么它必然涉及到几个需求点:

  1. 勾选、全选与反选。
  2. 根据选中项计算总价。

gif1

需求实现

获取数据

首先我们请求到购物车数据,这里并不是本文的重点,可以通过自定义请求 hook 实现,也可以通过普通的 useState + useEffect 实现。

const getCart = () => {
  return axios('/api/cart')
}
const {
  // 购物车数据
  cartData,
  // 重新请求数据的方法
  refresh,
} = useRequest < CartResponse > getCart

勾选逻辑实现

我们考虑用一个对象作为映射表,通过checkedMap这个变量来记录所有被勾选的商品 id:

type CheckedMap = {
  [id: number]: boolean,
}
// 商品勾选
const [checkedMap, setCheckedMap] = useState < CheckedMap > {}
const onCheckedChange: OnCheckedChange = (cartItem, checked) => {
  const { id } = cartItem
  const newCheckedMap = Object.assign({}, checkedMap, {
    [id]: checked,
  })
  setCheckedMap(newCheckedMap)
}

计算勾选总价

再用 reduce 来实现一个计算价格总和的函数

// cartItems的积分总和
const sumPrice = (cartItems: CartItem[]) => {
  return cartItems.reduce((sum, cur) => sum + cur.price, 0)
}

那么此时就需要一个过滤出所有选中商品的函数

// 返回已选中的所有cartItems
const filterChecked = () => {
  return (
    Object.entries(checkedMap)
      // 通过这个filter 筛选出所有checked状态为true的项
      .filter((entries) => Boolean(entries[1]))
      // 再从cartData中根据id来map出选中列表
      .map(([checkedId]) => cartData.find(({ id }) => id === Number(checkedId)))
  )
}

最后把这俩函数一组合,价格就出来了:

// 计算礼享积分
const calcPrice = () => {
  return sumPrice(filterChecked())
}

有人可能疑惑,为什么一个简单的逻辑要抽出这么几个函数,这里我要解释一下,为了保证文章的易读性,我把真实需求做了简化。

在真实需求中,可能会对不同类型的商品分别做总价计算,因此filterChecked这个函数就不可或缺了,filterChecked 可以传入一个额外的过滤参数,去返回勾选中的商品的子集,这里就不再赘述。

全选反选逻辑

有了filterChecked函数以后,我们也可以轻松的计算出派生状态checkedAll,是否全选:

// 全选
const checkedAll =
  cartData.length !== 0 && filterChecked().length === cartData.length

写出全选和反全选的函数:

const onCheckedAllChange = (newCheckedAll) => {
  // 构造新的勾选map
  let newCheckedMap: CheckedMap = {}
  // 全选
  if (newCheckedAll) {
    cartData.forEach((cartItem) => {
      newCheckedMap[cartItem.id] = true
    })
  }
  // 取消全选的话 直接把map赋值为空对象
  setCheckedMap(newCheckedMap)
}

如果是

  • 全选 就把checkedMap的每一个商品 id 都赋值为 true。
  • 反选 就把checkedMap赋值为空对象。

渲染商品子组件

{
  cartData.map((cartItem) => {
    const { id } = cartItem
    const checked = checkedMap[id]
    return (
      <ItemCard
        key={id}
        cartItem={cartItem}
        checked={checked}
        onCheckedChange={onCheckedChange}
      />
    )
  })
}

可以看出,是否勾选的逻辑就这样轻松的传给了子组件。

React.memo 性能优化

到了这一步,基本的购物车需求已经实现了。

但是现在我们有了新的问题。

这是 React 的一个缺陷,默认情况下几乎没有任何性能优化。

我们来看一下动图演示:

gif2

购物车此时有 5 个商品,看控制台的打印,每次都是以 5 为倍数增长每点击一次 checkbox,都会触发所有子组件的重新渲染。

如果我们有 50 个商品在购物车中,我们改了其中某一项的checked状态,也会导致 50 个子组件重新渲染。

我们想到了一个 api: React.memo,这个 api 基本等效于 class 组件中的shouldComponentUpdate,如果我们用这个 api 让子组件只有在 checked 发生改变的时候再重新渲染呢?

好,我们进入子组件的编写:

// memo优化策略
function areEqual(prevProps: Props, nextProps: Props) {
  return prevProps.checked === nextProps.checked
}

const ItemCard: FC<Props> = React.memo((props) => {
  const { checked, onCheckedChange } = props
  return (
    <div>
      <checkbox
        value={checked}
        onChange={(value) => onCheckedChange(cartItem, value)}
      />
      <span>商品</span>
    </div>
  )
}, areEqual)

在这种优化策略下,我们认为只要前后两次渲染传入的 props 中的checked相等,那么就不去重新渲染子组件。

React Hook 的陈旧值导致的 bug

到这里就完成了吗?其实,这里是有 bug 的。

我们来看一下 bug 还原:

gif3

如果我们先点击了第一个商品的勾选,再点击第二个商品的勾选,你会发现第一个商品的勾选状态没了。

在勾选了第一个商品后,我们此时的最新的checkedMap其实是

{ 1: true }

而由于我们的优化策略,第二个商品在第一个商品勾选后没有重新渲染,

注意 React 的函数式组件,在每次渲染的时候都会重新执行,从而产生一个闭包环境。

所以第二个商品拿到的onCheckedChange还是前一次渲染购物车这个组件的函数闭包中的,那么checkedMap自然也是上一次函数闭包中的最初的空对象。

const onCheckedChange: OnCheckedChange = (cartItem, checked) => {
  const { id } = cartItem
  // 注意,这里的checkedMap还是最初的空对象!!
  const newCheckedMap = Object.assign({}, checkedMap, {
    [id]: checked,
  })
  setCheckedMap(newCheckedMap)
}

因此,第二个商品勾选后,没有按照预期的计算出正确的checkedMap

{
  1: true,
  2: true
}

而是计算出了错误的

{ 2: true }

这就导致了第一个商品的勾选状态被丢掉了。

这也是 React Hook 的闭包带来的臭名昭著陈旧值的问题。

那么此时有一个简单的解决方案,在父组件中用React.useRef把函数通过一个引用来传递给子组件。

由于ref在 React 组件的整个生命周期中只存在一个引用,因此通过 current 永远是可以访问到引用中最新的函数值的,不会存在闭包陈旧值的问题。

  // 要把ref传给子组件 这样才能保证子组件能在不重新渲染的情况下拿到最新的函数引用
  const onCheckedChangeRef = React.useRef(onCheckedChange)
  // 注意要在每次渲染后把ref中的引用指向当次渲染中最新的函数。
  useEffect(() => {
    onCheckedChangeRef.current = onCheckedChange
  })

  return (
    <ItemCard
      key={id}
      cartItem={cartItem}
      checked={checked}
+     onCheckedChangeRef={onCheckedChangeRef}
    />
  )

子组件

// memo优化策略
function areEqual(prevProps: Props, nextProps: Props) {
  return prevProps.checked === nextProps.checked
}

const ItemCard: FC<Props> = React.memo((props) => {
  const { checked, onCheckedChangeRef } = props
  return (
    <div>
      <checkbox
        value={checked}
        onChange={(value) => onCheckedChangeRef.current(cartItem, value)}
      />
      <span>商品</span>
    </div>
  )
}, areEqual)

到此时,我们的简单的性能优化就完成了。

自定义 hook 之 useChecked

那么下一个场景,又遇到这种全选反选类似的需求,难道我们再这样重复写一套吗?这是不可接受的,我们用自定义 hook 来抽象这些数据以及行为。

并且这次我们通过 useReducer 来避免闭包旧值的陷阱(dispatch 在组件的生命周期中保持唯一引用,并且总是能操作到最新的值)。

import { useReducer, useEffect, useCallback } from 'react'

interface Option {
  /** 用来在map中记录勾选状态的key 一般取id */
  key?: string
}

type CheckedMap = {
  [key: string]: boolean
}

const CHECKED_CHANGE = 'CHECKED_CHANGE'

const CHECKED_ALL_CHANGE = 'CHECKED_ALL_CHANGE'

const SET_CHECKED_MAP = 'SET_CHECKED_MAP'

type CheckedChange<T> = {
  type: typeof CHECKED_CHANGE
  payload: {
    dataItem: T
    checked: boolean
  }
}

type CheckedAllChange = {
  type: typeof CHECKED_ALL_CHANGE
  payload: boolean
}

type SetCheckedMap = {
  type: typeof SET_CHECKED_MAP
  payload: CheckedMap
}

type Action<T> = CheckedChange<T> | CheckedAllChange | SetCheckedMap
export type OnCheckedChange<T> = (item: T, checked: boolean) => any

/**
 * 提供勾选、全选、反选等功能
 * 提供筛选勾选中的数据的函数
 * 在数据更新的时候自动剔除陈旧项
 */
export const useChecked = <T extends Record<string, any>>(
  dataSource: T[],
  { key = 'id' }: Option = {}
) => {
  const [checkedMap, dispatch] = useReducer(
    (checkedMapParam: CheckedMap, action: Action<T>) => {
      switch (action.type) {
        case CHECKED_CHANGE: {
          const { payload } = action
          const { dataItem, checked } = payload
          const { [key]: id } = dataItem
          return {
            ...checkedMapParam,
            [id]: checked,
          }
        }
        case CHECKED_ALL_CHANGE: {
          const { payload: newCheckedAll } = action
          const newCheckedMap: CheckedMap = {}
          // 全选
          if (newCheckedAll) {
            dataSource.forEach((dataItem) => {
              newCheckedMap[dataItem.id] = true
            })
          }
          return newCheckedMap
        }
        case SET_CHECKED_MAP: {
          return action.payload
        }
        default:
          return checkedMapParam
      }
    },
    {}
  )

  /** 勾选状态变更 */
  const onCheckedChange: OnCheckedChange<T> = useCallback(
    (dataItem, checked) => {
      dispatch({
        type: CHECKED_CHANGE,
        payload: {
          dataItem,
          checked,
        },
      })
    },
    []
  )

  type FilterCheckedFunc = (item: T) => boolean
  /** 筛选出勾选项 可以传入filter函数继续筛选 */
  const filterChecked = useCallback(
    (func: FilterCheckedFunc = () => true) => {
      return (
        Object.entries(checkedMap)
          .filter((entries) => Boolean(entries[1]))
          .map(([checkedId]) =>
            dataSource.find(({ [key]: id }) => id === Number(checkedId))
          )
          // 有可能勾选了以后直接删除 此时id虽然在checkedMap里 但是dataSource里已经没有这个数据了
          // 先把空项过滤掉 保证外部传入的func拿到的不为undefined
          .filter(Boolean)
          .filter(func)
      )
    },
    [checkedMap, dataSource, key]
  )
  /** 是否全选状态 */
  const checkedAll =
    dataSource.length !== 0 && filterChecked().length === dataSource.length

  /** 全选反选函数 */
  const onCheckedAllChange = (newCheckedAll: boolean) => {
    dispatch({
      type: CHECKED_ALL_CHANGE,
      payload: newCheckedAll,
    })
  }

  // 数据更新的时候 如果勾选中的数据已经不在数据内了 就删除掉
  useEffect(() => {
    filterChecked().forEach((checkedItem) => {
      let changed = false
      if (!dataSource.find((dataItem) => checkedItem.id === dataItem.id)) {
        delete checkedMap[checkedItem.id]
        changed = true
      }
      if (changed) {
        dispatch({
          type: SET_CHECKED_MAP,
          payload: Object.assign({}, checkedMap),
        })
      }
    })
    // eslint-disable-next-line react-hooks/exhaustive-deps
  }, [dataSource])

  return {
    checkedMap,
    dispatch,
    onCheckedChange,
    filterChecked,
    onCheckedAllChange,
    checkedAll,
  }
}

这时候在组件内使用,就很简单了:

const {
  checkedAll,
  checkedMap,
  onCheckedAllChange,
  onCheckedChange,
  filterChecked,
} = useChecked(cartData)

我们在自定义 hook 里把复杂的业务逻辑全部做掉了,包括数据更新后的无效 id 剔除等等。快去推广给团队的小伙伴,让他们早点下班吧。

自定义 hook 之 useMap

有一天,突然又来了个需求,我们需要用一个 map 来根据购物车商品的 id 来记录另外的一些东西,我们突然发现,上面的自定义 hook 把 map 的处理等等逻辑也都打包进去了,我们只能给 map 的值设为true / false,灵活性不够。

我们进一步把useMap也抽出来,然后让useCheckedMap基于它之上开发。

useMap

import { useReducer, useEffect, useCallback } from 'react'

export interface Option {
  /** 用来在map中作为key 一般取id */
  key?: string
}

export type MapType = {
  [key: string]: any
}

export const CHANGE = 'CHANGE'

export const CHANGE_ALL = 'CHANGE_ALL'

export const SET_MAP = 'SET_MAP'

export type Change<T> = {
  type: typeof CHANGE
  payload: {
    dataItem: T
    value: any
  }
}

export type ChangeAll = {
  type: typeof CHANGE_ALL
  payload: any
}

export type SetCheckedMap = {
  type: typeof SET_MAP
  payload: MapType
}

export type Action<T> = Change<T> | ChangeAll | SetCheckedMap
export type OnValueChange<T> = (item: T, value: any) => any

/**
 * 提供map操作的功能
 * 在数据更新的时候自动剔除陈旧项
 */
export const useMap = <T extends Record<string, any>>(
  dataSource: T[],
  { key = 'id' }: Option = {}
) => {
  const [map, dispatch] = useReducer(
    (checkedMapParam: MapType, action: Action<T>) => {
      switch (action.type) {
        // 单值改变
        case CHANGE: {
          const { payload } = action
          const { dataItem, value } = payload
          const { [key]: id } = dataItem
          return {
            ...checkedMapParam,
            [id]: value,
          }
        }
        // 所有值改变
        case CHANGE_ALL: {
          const { payload } = action
          const newMap: MapType = {}
          dataSource.forEach((dataItem) => {
            newMap[dataItem[key]] = payload
          })
          return newMap
        }
        // 完全替换map
        case SET_MAP: {
          return action.payload
        }
        default:
          return checkedMapParam
      }
    },
    {}
  )

  /** map某项的值变更 */
  const onMapValueChange: OnValueChange<T> = useCallback((dataItem, value) => {
    dispatch({
      type: CHANGE,
      payload: {
        dataItem,
        value,
      },
    })
  }, [])

  // 数据更新的时候 如果map中的数据已经不在dataSource内了 就删除掉
  useEffect(() => {
    dataSource.forEach((checkedItem) => {
      let changed = false
      if (
        // map中包含此项
        // 并且数据源中找不到此项了
        checkedItem[key] in map &&
        !dataSource.find((dataItem) => checkedItem[key] === dataItem[key])
      ) {
        delete map[checkedItem[key]]
        changed = true
      }
      if (changed) {
        dispatch({
          type: SET_MAP,
          payload: Object.assign({}, map),
        })
      }
    })
    // eslint-disable-next-line react-hooks/exhaustive-deps
  }, [dataSource])

  return {
    map,
    dispatch,
    onMapValueChange,
  }
}

这是一个通用的 map 操作的自定义 hook,它考虑了闭包陷阱,考虑了旧值的删除。

在此之上,我们实现上面的useChecked

useChecked

import { useCallback } from 'react'
import { useMap, CHANGE_ALL, Option } from './use-map'

type CheckedMap = {
  [key: string]: boolean;
}

export type OnCheckedChange<T> = (item: T, checked: boolean) => any

/**
 * 提供勾选、全选、反选等功能
 * 提供筛选勾选中的数据的函数
 * 在数据更新的时候自动剔除陈旧项
 */
export const useChecked = <T extends Record<string, any>>(
  dataSource: T[],
  option: Option = {}
) => {
  const { map: checkedMap, onMapValueChange, dispatch } = useMap(
    dataSource,
    option
  )
  const { key = 'id' } = option

  /** 勾选状态变更 */
  const onCheckedChange: OnCheckedChange<T> = useCallback(
    (dataItem, checked) => {
      onMapValueChange(dataItem, checked)
    },
    [onMapValueChange]
  )

  type FilterCheckedFunc = (item: T) => boolean
  /** 筛选出勾选项 可以传入filter函数继续筛选 */
  const filterChecked = useCallback(
    (func?: FilterCheckedFunc) => {
      const checkedDataSource = dataSource.filter(item =>
        Boolean(checkedMap[item[key]])
      )
      return func ? checkedDataSource.filter(func) : checkedDataSource
    },
    [checkedMap, dataSource, key]
  )
  /** 是否全选状态 */
  const checkedAll =
    dataSource.length !== 0 && filterChecked().length === dataSource.length

  /** 全选反选函数 */
  const onCheckedAllChange = (newCheckedAll: boolean) => {
    // 全选
    const payload = !!newCheckedAll
    dispatch({
      type: CHANGE_ALL,
      payload,
    })
  }

  return {
    checkedMap: checkedMap as CheckedMap,
    dispatch,
    onCheckedChange,
    filterChecked,
    onCheckedAllChange,
    checkedAll,
  }
}

总结

本文通过一个真实的购物车需求,一步一步的完成优化、踩坑,在这个过程中,我们对 React Hook 的优缺点一定也有了进一步的认识。

在利用自定义 hook 把通用逻辑抽取出来后,我们业务组件内的代码量大大的减少了,并且其他相似的场景都可以去复用。

React Hook 带来了一种新的开发模式,但是也带来了一些陷阱,它是一把双刃剑,如果你能合理使用,那么它会给你带来很强大的力量。

感谢你的阅读,希望这篇文章可以给你启发。

查看原文

赞 11 收藏 7 评论 0

ssh_晨曦时梦见兮 发布了文章 · 2020-07-09

写给前端的算法进阶指南,我是如何两个月零基础刷200题

前言

最近国内大厂面试中,出现 LeetCode 真题考察的频率越来越高了。我也观察到有越来越多的前端同学开始关注算法这个话题。

但是算法是一个门槛很高的东西,在一个算法新手的眼里,它的智商门槛要求很高。事实上是这个样子的吗?如果你怀疑自己的智商不够去学习算法,那么你一定要先看完这篇文章:《天生不聪明》,也正是这篇文章激励了我开始了算法之路。

这篇文章,我会先总结几个必学的题目分类,给出这个分类下必做例题的详细题解,并且在文章的末尾给出每个分类下必刷的题目的获取方式。

一定要耐心看到底,会有重磅干货。

心路

我从 5 月份准备离职的时候开始学习算法,在此之前对于算法我是零基础,在最开始我对于算法的感受也和大家一样,觉得自己智商可能不够,望而却步。但是看了一些大佬对于算法和智商之间的关系,我发现算法好像也是一个通过练习可以慢慢成长的学科,而不是只有智商达到了某个点才能有入场券,所以我开始了我的算法之路。通过视频课程 + 分类刷题 + 总结题解 + 回头复习的方式,我在两个月的时间里把力扣的解题数量刷到了200题。对于一个算法新人来说,这应该算是一个还可以的成绩,这篇文章,我把我总结的一些学习心得,和一些经典例题分享给大家。

学习方式

  1. 分类刷题:很多第一次接触力扣的同学对于刷题的方法不太了解,有的人跟着题号刷,有的人跟着每日一题刷,但是这种漫无目的的刷题方式一般都会在中途某一天放弃,或者刷了很久但是却发现没什么沉淀。这里不啰嗦,直接点明一个所有大佬都推荐的刷题方法:把自己的学习阶段分散成几个时间段去刷不同分类的题型,比如第一周专门解链表相关题型,第二周专门解二叉树相关题型。这样你的知识会形成一个体系,通过一段时间的刻意练习把这个题型相关的知识点强化到你的脑海中,不容易遗忘。
  2. 适当放弃:很多同学遇到一个难题,非得埋头钻研,干他 2 个小时。最后挫败感十足,久而久之可能就放弃了算法之路。要知道算法是个沉淀了几十年的领域,题解里的某个算法可能是某些教授研究很多年的心血,你想靠自己一个新手去想出来同等优秀的解法,岂不是想太多了。所以要学会适当放弃,一般来说,比较有目的性(面试)刷题的同学,他面对一道新的题目毫无头绪的话,会在 10 分钟之内直接放弃去看题解,然后记录下来,反复复习,直到这个解法成为自己的知识为止。这是效率最高的学习办法。
  3. 接受自己是新手:没错,说的难听一点,接受自己不是天才这个现实。你在刷题的过程中会遇到很多困扰你的时候,比如相同的题型已经看过例题,稍微变了条件就解不出来。或者对于一个 easy 难度的题毫无头绪。或者甚至看不懂别人的题解(没错我经常)相信我,这很正常,不能说明你不适合学习算法,只能说明算法确实是一个博大精深的领域,把自己在其他领域的沉淀抛开来,接受自己是新手这个事实,多看题解,多请教别人。

分类大纲

  1. 算法的复杂度分析。
  2. 排序算法,以及他们的区别和优化。
  3. 数组中的双指针、滑动窗口思想。
  4. 利用 Map 和 Set 处理查找表问题。
  5. 链表的各种问题。
  6. 利用递归和迭代法解决二叉树问题。
  7. 栈、队列、DFS、BFS。
  8. 回溯法、贪心算法、动态规划。

题解

接下来我会放出几个分类的经典题型,以及我对应的讲解,当做开胃菜,并且在文章的末尾我会给出获取每个分类推荐你去刷的题目的合集,记得看到底哦。

查找表问题

两个数组的交集 II-350

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


为两个数组分别建立 map,用来存储 num -> count 的键值对,统计每个数字出现的数量。

然后对其中一个 map 进行遍历,查看这个数字在两个数组中分别出现的数量,取出现的最小的那个数量(比如数组 1 中出现了 1 次,数组 2 中出现了 2 次,那么交集应该取 1 次),push 到结果数组中即可。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
let intersect = function (nums1, nums2) {
  let map1 = makeCountMap(nums1)
  let map2 = makeCountMap(nums2)
  let res = []
  for (let num of map1.keys()) {
    const count1 = map1.get(num)
    const count2 = map2.get(num)

    if (count2) {
      const pushCount = Math.min(count1, count2)
      for (let i = 0; i < pushCount; i++) {
        res.push(num)
      }
    }
  }
  return res
}

function makeCountMap(nums) {
  let map = new Map()
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i]
    let count = map.get(num)
    if (count) {
      map.set(num, count + 1)
    } else {
      map.set(num, 1)
    }
  }
  return map
}

双指针问题

最接近的三数之和-16

给定一个包括  n 个整数的数组  nums  和 一个目标值  target。找出  nums  中的三个整数,使得它们的和与  target  最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/probl...

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


先按照升序排序,然后分别从左往右依次选择一个基础点 i0 <= i <= nums.length - 3),在基础点的右侧用双指针去不断的找最小的差值。

假设基础点是 i,初始化的时候,双指针分别是:

  • lefti + 1,基础点右边一位。
  • right: nums.length - 1 数组最后一位。

然后求此时的和,如果和大于 target,那么可以把右指针左移一位,去试试更小一点的值,反之则把左指针右移。

在这个过程中,不断更新全局的最小差值 min,和此时记录下来的和 res

最后返回 res 即可。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let threeSumClosest = function (nums, target) {
  let n = nums.length
  if (n === 3) {
    return getSum(nums)
  }
  // 先升序排序 此为解题的前置条件
  nums.sort((a, b) => a - b)

  let min = Infinity // 和 target 的最小差
  let res

  // 从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个
  for (let i = 0; i <= nums.length - 3; i++) {
    let basic = nums[i]
    let left = i + 1 // 左指针先从 i 右侧的第一位开始尝试
    let right = n - 1 // 右指针先从数组最后一项开始尝试

    while (left < right) {
      let sum = basic + nums[left] + nums[right] // 三数求和
      // 更新最小差
      let diff = Math.abs(sum - target)
      if (diff < min) {
        min = diff
        res = sum
      }
      if (sum < target) {
        // 求出的和如果小于目标值的话 可以尝试把左指针右移 扩大值
        left++
      } else if (sum > target) {
        // 反之则右指针左移
        right--
      } else {
        // 相等的话 差就为0 一定是答案
        return sum
      }
    }
  }

  return res
}

function getSum(nums) {
  return nums.reduce((total, cur) => total + cur, 0)
}

滑动窗口问题

无重复字符的最长子串-3

给定一个字符串,请你找出其中不含有重复字符的   最长子串   的长度。

示例  1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


这题是比较典型的滑动窗口问题,定义一个左边界 left 和一个右边界 right,形成一个窗口,并且在这个窗口中保证不出现重复的字符串。

这需要用到一个新的变量 freqMap,用来记录窗口中的字母出现的频率数。在此基础上,先尝试取窗口的右边界再右边一个位置的值,也就是 str[right + 1],然后拿这个值去 freqMap 中查找:

  1. 这个值没有出现过,那就直接把 right ++,扩大窗口右边界。
  2. 如果这个值出现过,那么把 left ++,缩进左边界,并且记得把 str[left] 位置的值在 freqMap 中减掉。

循环条件是 left < str.length,允许左边界一直滑动到字符串的右界。

/**
 * @param {string} s
 * @return {number}
 */
let lengthOfLongestSubstring = function (str) {
  let n = str.length
  // 滑动窗口为s[left...right]
  let left = 0
  let right = -1
  let freqMap = {} // 记录当前子串中下标对应的出现频率
  let max = 0 // 找到的满足条件子串的最长长度

  while (left < n) {
    let nextLetter = str[right + 1]
    if (!freqMap[nextLetter] && nextLetter !== undefined) {
      freqMap[nextLetter] = 1
      right++
    } else {
      freqMap[str[left]] = 0
      left++
    }
    max = Math.max(max, right - left + 1)
  }

  return max
}

链表问题

两两交换链表中的节点-24

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

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

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/probl...

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


这题本意比较简单,1 -> 2 -> 3 -> 4 的情况下可以定义一个递归的辅助函数 helper,这个辅助函数对于节点和它的下一个节点进行交换,比如 helper(1) 处理 1 -> 2,并且把交换变成 2 -> 1 的尾节点 1next继续指向 helper(3)也就是交换后的 4 -> 3

边界情况在于,如果顺利的作了两两交换,那么交换后我们的函数返回出去的是 交换后的头部节点,但是如果是奇数剩余项的情况下,没办法做交换,那就需要直接返回 原本的头部节点。这个在 helper函数和主函数中都有体现。

let swapPairs = function (head) {
  if (!head) return null
  let helper = function (node) {
    let tempNext = node.next
    if (tempNext) {
      let tempNextNext = node.next.next
      node.next.next = node
      if (tempNextNext) {
        node.next = helper(tempNextNext)
      } else {
        node.next = null
      }
    }
    return tempNext || node
  }

  let res = helper(head)

  return res || head
}

深度优先遍历问题

二叉树的所有路径-257

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明:  叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/probl...

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


用当前节点的值去拼接左右子树递归调用当前函数获得的所有路径。

也就是根节点拼上以左子树为根节点得到的路径,加上根节点拼上以右子树为根节点得到的所有路径。

直到叶子节点,仅仅返回包含当前节点的值的数组。

let binaryTreePaths = function (root) {
  let res = []
  if (!root) {
    return res
  }

  if (!root.left && !root.right) {
    return [`${root.val}`]
  }

  let leftPaths = binaryTreePaths(root.left)
  let rightPaths = binaryTreePaths(root.right)

  leftPaths.forEach((leftPath) => {
    res.push(`${root.val}->${leftPath}`)
  })
  rightPaths.forEach((rightPath) => {
    res.push(`${root.val}->${rightPath}`)
  })

  return res
}

广度优先遍历(BFS)问题

在每个树行中找最大值-515

https://leetcode-cn.com/probl...

您需要在二叉树的每一行中找到最大的值。

输入:

          1
         / \
        3   2
       / \   \
      5   3   9

输出: [1, 3, 9]

这是一道典型的 BFS 题目,BFS 的套路其实就是维护一个 queue 队列,在读取子节点的时候同时把发现的孙子节点 push 到队列中,但是先不处理,等到这一轮队列中的子节点处理完成以后,下一轮再继续处理的就是孙子节点了,这就实现了层序遍历,也就是一层层的去处理。

但是这里有一个问题卡住我了一会,就是如何知道当前处理的节点是哪个层级的,在最开始的时候我尝试写了一下二叉树求某个 index 所在层级的公式,但是发现这种公式只能处理「平衡二叉树」。

后面看题解发现他们都没有专门维护层级,再仔细一看才明白层级的思路:

其实就是在每一轮 while 循环里,再开一个 for 循环,这个 for 循环的终点是「提前缓存好的 length 快照」,也就是进入这轮 while 循环时,queue 的长度。其实这个长度就恰好代表了「一个层级的长度」。

缓存后,for 循环里可以安全的把子节点 push 到数组里而不影响缓存的当前层级长度。

另外有一个小 tips,在 for 循环处理完成后,应该要把 queue 的长度截取掉上述的缓存长度。一开始我使用的是 queue.splice(0, len),结果速度只击败了 33%的人。后面换成 for 循环中去一个一个shift来截取,速度就击败了 77%的人。

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
let largestValues = function (root) {
  if (!root) return []
  let queue = [root]
  let maximums = []

  while (queue.length) {
    let max = Number.MIN_SAFE_INTEGER
    // 这里需要先缓存length 这个length代表当前层级的所有节点
    // 在循环开始后 会push新的节点 length就不稳定了
    let len = queue.length
    for (let i = 0; i < len; i++) {
      let node = queue[i]
      max = Math.max(node.val, max)

      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }

    // 本「层级」处理完毕,截取掉。
    for (let i = 0; i < len; i++) {
      queue.shift()
    }

    // 这个for循环结束后 代表当前层级的节点全部处理完毕
    // 直接把计算出来的最大值push到数组里即可。
    maximums.push(max)
  }

  return maximums
}

栈问题

有效的括号-20

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

https://leetcode-cn.com/probl...


提前记录好左括号类型 (, {, [和右括号类型), }, ]的映射表,当遍历中遇到左括号的时候,就放入栈 stack 中(其实就是数组),当遇到右括号时,就把 stack 顶的元素 pop 出来,看一下是否是这个右括号所匹配的左括号(比如 () 是一对匹配的括号)。

当遍历结束后,栈中不应该剩下任何元素,返回成功,否则就是失败。

/**
 * @param {string} s
 * @return {boolean}
 */
let isValid = function (s) {
  let sl = s.length
  if (sl % 2 !== 0) return false
  let leftToRight = {
    "{": "}",
    "[": "]",
    "(": ")",
  }
  // 建立一个反向的 value -> key 映射表
  let rightToLeft = createReversedMap(leftToRight)
  // 用来匹配左右括号的栈
  let stack = []

  for (let i = 0; i < s.length; i++) {
    let bracket = s[i]
    // 左括号 放进栈中
    if (leftToRight[bracket]) {
      stack.push(bracket)
    } else {
      let needLeftBracket = rightToLeft[bracket]
      // 左右括号都不是 直接失败
      if (!needLeftBracket) {
        return false
      }

      // 栈中取出最后一个括号 如果不是需要的那个左括号 就失败
      let lastBracket = stack.pop()
      if (needLeftBracket !== lastBracket) {
        return false
      }
    }
  }

  if (stack.length) {
    return false
  }
  return true
}

function createReversedMap(map) {
  return Object.keys(map).reduce((prev, key) => {
    const value = map[key]
    prev[value] = key
    return prev
  }, {})
}

递归与回溯

直接看我写的这两篇文章即可,递归与回溯甚至是平常业务开发中最常见的算法场景之一了,所以我重点总结了两篇文章。

《前端电商 sku 的全排列算法很难吗?学会这个套路,彻底掌握排列组合。》

前端「N 皇后」递归回溯经典问题图解

动态规划

打家劫舍 - 198

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
  偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
  偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


动态规划的一个很重要的过程就是找到「状态」和「状态转移方程」,在这个问题里,设 i 是当前屋子的下标,状态就是 以 i 为起点偷窃的最大价值

在某一个房子面前,盗贼只有两种选择:偷或者不偷

  1. 偷的话,价值就是「当前房子的价值」+「下两个房子开始盗窃的最大价值」
  2. 不偷的话,价值就是「下一个房子开始盗窃的最大价值」

在这两个值中,选择最大值记录在 dp[i]中,就得到了i 为起点所能偷窃的最大价值。

动态规划的起手式,找基础状态,在这题中,以终点为起点的最大价值一定是最好找的,因为终点不可能再继续往后偷窃了,所以设 n 为房子的总数量, dp[n - 1] 就是 nums[n - 1],小偷只能选择偷窃这个房子,而不能跳过去选择下一个不存在的房子。

那么就找到了动态规划的状态转移方程:

// 抢劫当前房子
robNow = nums[i] + dp[i + 2] // 「当前房子的价值」 + 「i + 2 下标房子为起点的最大价值」

// 不抢当前房子,抢下一个房子
robNext = dp[i + 1] //「i + 1 下标房子为起点的最大价值」

// 两者选择最大值
dp[i] = Math.max(robNow, robNext)

,并且从后往前求解。

function (nums) {
  if (!nums.length) {
    return 0;
  }
  let dp = [];

  for (let i = nums.length - 1; i >= 0; i--) {
    let robNow = nums[i] + (dp[i + 2] || 0)
    let robNext = dp[i + 1] || 0

    dp[i] = Math.max(robNow, robNext)
  }

  return dp[0];
};

最后返回 以 0 为起点开始打劫的最大价值 即可。

贪心算法问题

分发饼干-455

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值  gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

注意:

你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。

示例 1:

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

输出: 1

解释:
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:

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

输出: 2

解释:
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


把饼干和孩子的需求都排序好,然后从最小的饼干分配给需求最小的孩子开始,不断的尝试新的饼干和新的孩子,这样能保证每个分给孩子的饼干都恰到好处的不浪费,又满足需求。

利用双指针不断的更新 i 孩子的需求下标和 j饼干的值,直到两者有其一达到了终点位置:

  1. 如果当前的饼干不满足孩子的胃口,那么把 j++ 寻找下一个饼干,不用担心这个饼干被浪费,因为这个饼干更不可能满足下一个孩子(胃口更大)。
  2. 如果满足,那么 i++; j++; count++ 记录当前的成功数量,继续寻找下一个孩子和下一个饼干。
/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
let findContentChildren = function (g, s) {
  g.sort((a, b) => a - b)
  s.sort((a, b) => a - b)

  let i = 0
  let j = 0

  let count = 0
  while (j < s.length && i < g.length) {
    let need = g[i]
    let cookie = s[j]

    if (cookie >= need) {
      count++
      i++
      j++
    } else {
      j++
    }
  }

  return count
}

必做题目

其实写了这么多,以上分类所提到的题目,只是当前分类下比较适合作为例题来讲解的题目而已,在整个 LeetCode 学习过程中只是冰山一角。这些题可以作为你深入这个分类的一个入门例题,但是不可避免的是,你必须去下苦功夫刷每个分类下的其他经典题目

如果你信任我,你也可以点击这里 获取各个分类下必做题目的详细题解,我跟着一个ACM 亚洲区奖牌获得者给出的提纲,整理了100+道必做题目的详细题解

那么什么叫必做题目呢?

  1. 它核心考察算法思想,而不是奇巧淫技。
  2. 它考察的知识点,可以举一反三的应用到很多相似题目上。
  3. 面试热门题,大厂喜欢考这个题目,说明这个知识点很重要。

当然你也可以去知乎等平台搜索相关的问题,也会有很多人总结,但是比我总结的全的不多见。100 多题说多也不多,说少也不少。认真学习、解答、吸收这些题目大概要花费1 个月左右的时间。但是相信我,1 个月以后你在算法方面会脱胎换骨,应对国内大厂的算法面试也会变得游刃有余。

总结

关于算法在工程方面有用与否的争论,已经是一个经久不衰的话题了。这里不讨论这个,我个人的观念是绝对有用的,只要你不是一个甘于只做简单需求的人,你一定会在后续开发架构、遇到难题的过程中或多或少的从你的算法学习中受益。

再说的功利点,就算是为了面试,刷算法能够进入大厂也是你职业生涯的一个起飞点,大厂给你带来的的环境、严格的 Code Review、完善的导师机制和协作流程也是你作为工程师所梦寐以求的。

希望这篇文章能让你不再继续害怕算法面试,跟着我一起攻下这座城堡吧,大家加油!

❤️ 感谢大家

1.如果本文对你有帮助,就点个赞支持下吧,你的「赞」是我创作的动力。

2.关注公众号「前端从进阶到入院」即可加我好友,我拉你进「前端进阶交流群」,大家一起共同交流和进步。

查看原文

赞 26 收藏 19 评论 1

ssh_晨曦时梦见兮 发布了文章 · 2020-06-26

前端电商 sku 的全排列算法很难吗?学会这个套路,彻底掌握排列组合。

前言

前段时间在掘金看到一个热帖 今天又懒得加班了,能写出这两个算法吗?带你去电商公司写商品中心,里面提到了一个比较有意思故事,大意就是一个看似比较简单的电商 sku 的全排列组合算法,但是却有好多人没能顺利写出来。有一个毕业生小伙子在面试的时候给出了思路,但是进去以后还是没写出来,羞愧跑路~

其实排列组合是一个很经典的算法,也是对递归回溯法的一个实践运用,本篇文章就以带你学习一个标准「排列组合求解模板」,耐心看完,你会有更多收获。

需求

需求描述起来很简单,有这样三个数组:

let names = ["iPhone X", "iPhone XS"]

let colors = ["黑色", "白色"]

let storages = ["64g", "256g"]

需要把他们的所有组合穷举出来,最终得到这样一个数组:

[
  ["iPhone X", "黑色", "64g"],
  ["iPhone X", "黑色", "256g"],
  ["iPhone X", "白色", "64g"],
  ["iPhone X", "白色", "256g"],
  ["iPhone XS", "黑色", "64g"],
  ["iPhone XS", "黑色", "256g"],
  ["iPhone XS", "白色", "64g"],
  ["iPhone XS", "白色", "256g"],
]

由于这些属性数组是不定项的,所以不能简单的用三重的暴力循环来求解了。

思路

如果我们选用递归回溯法来解决这个问题,那么最重要的问题就是设计我们的递归函数。

思路分解

以上文所举的例子来说,比如我们目前的属性数组就是:namescolorsstorages,首先我们会处理 names 数组,很显然对于每个属性数组,都需要去遍历它,然后一个一个选择后再去和 下一个数组的每一项进行组合。

我们设计的递归函数接受两个参数:

  • index 对应当前正在处理的下标,是 names 还是 colors 或是 storage
  • prev 上一次递归已经拼接成的结果,比如 ['iPhone X', '黑色']

进入递归函数:

  1. 处理属性数组的下标0:假设我们在第一次循环中选择了 iPhone XS,那此时我们有一个未完成的结果状态,假设我们叫它 prev,此时 prev = ['iPhone XS']
  2. 处理属性数组的下标1:那么就处理到 colors 数组的了,并且我们拥有 prev,在遍历 colors 的时候继续递归的去把 prev 拼接成 prev.concat(color),也就是 ['iPhone XS', '黑色'] 这样继续把这个 prev 交给下一次递归。
  3. 处理属性数组的下标2:那么就处理到 storages 数组的了,并且我们拥有了 name + colorprev,在遍历 storages 的时候继续递归的去把 prev 拼接成 prev.concat(storage),也就是 ['iPhone XS', '黑色', '64g'],并且此时我们发现处理的属性数组下标已经到达了末尾,那么就放入全局的结果变量 res 中,作为一个结果。

编码实现

let names = ["iPhone X", "iPhone XS"]

let colors = ["黑色", "白色"]

let storages = ["64g", "256g"]

let combine = function (...chunks) {
  let res = []

  let helper = function (chunkIndex, prev) {
    let chunk = chunks[chunkIndex]
    let isLast = chunkIndex === chunks.length - 1
    for (let val of chunk) {
      let cur = prev.concat(val)
      if (isLast) {
        // 如果已经处理到数组的最后一项了 则把拼接的结果放入返回值中
        res.push(cur)
      } else {
        helper(chunkIndex + 1, cur)
      }
    }
  }

  // 从属性数组下标为 0 开始处理
  // 并且此时的 prev 是个空数组
  helper(0, [])

  return res
}

console.log(combine(names, colors, storages))

递归树图

画出以 iPhone X 这一项为起点的递归树图,当然这个问题是一个多个根节点的树,请自行脑补 iPhone XS 为起点的树,子结构是一模一样的。

万能模板

为什么说这种接法是排列组合的「万能模板呢」?来看一下 LeetCode 上的真题。

组合-77

77. 组合 这是一道难度为 medium 的问题,其实算是比较有难度的问题了:

问题

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解答

let combine = function (n, k) {
  let ret = []

  let helper = (start, prev) => {
    let len = prev.length
    if (len === k) {
      ret.push(prev)
      return
    }

    for (let i = start; i <= n; i++) {
      helper(i + 1, prev.concat(i))
    }
  }
  helper(1, [])
  return ret
}

可以看出这题和我们求解电商排列组合的代码竟然如此相似。只需要设计一个接受 start排列起始位置、prev上一次拼接结果为参数的递归 helper函数,

然后对于每一个起点下标 start,先拼接上 start位置对应的值,再不断的再以其他剩余的下标作为起点去做下一次拼接。当 prev 这个中间状态的拼接数组到达题目的要求长度 k后,就放入结果数组中。

优化

在这个解法中,有一些递归分支是明显不可能获取到结果的,我们每次递归都会循环尝试 <= n的所有项去作为start,假设我们要求的数组长度 k = 3,最大值 n = 4

而我们以 prev = [1],再去以 n = 4start 作为递归的起点,那么显然是不可能得到结果的,因为 n = 4 的话就只剩下 4这一项可以拼接了,最多也就拼接成 [1, 4],不可能满足 k = 3 的条件。

所以在进入递归之前,就果断的把这些“废枝”给减掉。这就叫做「剪枝」

let combine = function (n, k) {
  let ret = []

  let helper = (start, prev) => {
    let len = prev.length
    if (len === k) {
      ret.push(prev)
      return
    }

    // 还有 rest 个位置待填补
    let rest = k - prev.length
    for (let i = start; i <= n; i++) {
      if (n - i + 1 < rest) {
        continue
      }
      helper(i + 1, prev.concat(i))
    }
  }
  helper(1, [])
  return ret
}

相似题型

当然,力扣中可以套用这个模板的相似题型还有很多,而且大多数难度都是 medium的,比如快手的面试题子集 II-90,可以看出排列组合的递归解法还是有一定的难度的。

我在维护的 LeetCode 题解仓库 中已经按标签筛选好 「递归与回溯」类型的几道题目和解答了,感兴趣的小伙伴也可以一起攻破它们。

总结

排列组合问题并不是空中楼阁,在实际工作中也会经常遇到这种场景,掌握了递归回溯的标准模板当然不是为了让你死记硬背套公式,而是真正的理解它。遇到需要递归解决的问题。

  1. 画出递归树状图,找出递归公式。
  2. 对于不可能达成条件的分支递归,进行合理的「剪枝」。

希望阅读完本篇文章的你,能对递归和排列组合问题有进一步的理解和收获。

❤️ 感谢大家

1.如果本文对你有帮助,就点个赞支持下吧,你的「赞」是我创作的动力。

2.关注公众号「前端从进阶到入院」即可加我好友,我拉你进「前端进阶交流群」,大家一起共同交流和进步。

查看原文

赞 18 收藏 11 评论 0

ssh_晨曦时梦见兮 发布了文章 · 2020-06-12

这个前端竟然用动态规划写瀑布流布局?给我打死他!

前言

瀑布流布局是前端领域中一个很常见的需求,由于图片的高度是不一致的,所以在多列布局中默认布局下很难获得满意的排列。

我们的需求是,图片高度不规律的情况下,在两列布局中,让左右两侧的图片总高度尽可能的接近,这样的布局会非常的美观。

注意,本文的目的仅仅是讨论算法在前端中能如何运用,而不是说瀑布流的最佳解法是动态规划,可以仅仅当做学习拓展来看。

本文的图片节选自知乎问题《有个漂亮女朋友是种怎样的体验?》,我先去看美女了,本文到此结束。(逃

预览

分析

从预览图中可以看出,虽然图片的高度是不定的,但是到了这个布局的最底部,左右两张图片是正好对齐的,这就是一个比较美观的布局了。

那么怎么实现这个需求呢?从头开始拆解,现在我们能拿到一组图片数组 [img1, img2, img3],我们可以通过一些方法得到它对应的高度 [1000, 2000, 3000],那么现在我们的目标就是能够计算出左右两列 left: [1000, 2000]right: [3000] 这样就可以把一个左右等高的布局给渲染出来了。

准备工作

首先准备好小姐姐数组 SISTERS

let SISTERS = [
  'https://pic3.zhimg.com/v2-89735fee10045d51693f1f74369aaa46_r.jpg',
  'https://pic1.zhimg.com/v2-ca51a8ce18f507b2502c4d495a217fa0_r.jpg',
  'https://pic1.zhimg.com/v2-c90799771ed8469608f326698113e34c_r.jpg',
  'https://pic1.zhimg.com/v2-8d3dd83f3a419964687a028de653f8d8_r.jpg',
  ... more 50 items
]

准备好一个工具方法 loadImages,这个方法的目的就是把所有图片预加载以后获取对应的高度,放到一个数组里返回。并且要对外通知所有图片处理完成的时机,有点类似于 Promise.all 的思路。

这个方法里,我们把图片按照 宽高比 和屏幕宽度的一半进行相乘,得到缩放后适配屏宽的图片高度。

let loadImgHeights = (imgs) => {
  return new Promise((resolve, reject) => {
    const length = imgs.length
    const heights = []
    let count = 0
    const load = (index) => {
      let img = new Image()
      const checkIfFinished = () => {
        count++
        if (count === length) {
          resolve(heights)
        }
      }
      img.onload = () => {
        const ratio = img.height / img.width
        const halfHeight = ratio * halfInnerWidth
        // 高度按屏幕一半的比例来计算
        heights[index] = halfHeight
        checkIfFinished()
      }
      img.onerror = () => {
        heights[index] = 0
        checkIfFinished()
      }
      img.src = imgs[index]
    }
    imgs.forEach((img, index) => load(index))
  })
}

有了图片高度以后,我们就开始挑选适合这个需求的算法了。

贪心算法

在人的脑海中最直观的想法是什么样的?在每装一个图片前都对比一下左右数组的高度和,往高度较小的那个数组里去放入下一项。

这就是贪心算法,我们来简单实现下:

let greedy = (heights) => {
  let leftHeight = 0
  let rightHeight = 0
  let left = []
  let right = []

  heights.forEach((height, index) => {
    if (leftHeight >= rightHeight) {
      right.push(index)
      rightHeight += height
    } else {
      left.push(index)
      leftHeight += height
    }
  })

  return { left, right }
}

我们得到了 leftright 数组,对应左右两列渲染图片的下标,并且我们也有了每个图片的高度,那么渲染到页面上就很简单了:

<div class="wrap" v-if="imgsLoaded">
  <div class="half">
    <img
      class="img"
      v-for="leftIndex in leftImgIndexes"
      :data-original="imgs[leftIndex]"
      :style="{ width: '100%', height: imgHeights[leftIndex] + 'px' }"
    />
  </div>
  <div class="half">
    <img
      class="img"
      v-for="rightIndex in rightImgIndexes"
      :data-original="imgs[rightIndex]"
      :style="{ width: '100%', height: imgHeights[rightIndex] + 'px' }"
    />
  </div>
</div>

效果如图:

预览地址:
https://sl1673495.github.io/d...

可以看出,贪心算法只寻求局部最优解(只在考虑当前图片的时候找到一个最优解),所以最后左右两边的高度差还是相对较大的,局部最优解很难成为全局最优解。

再回到文章开头的图片去看看,对于同样的一个图片数组,那个预览图里的高度差非常的小,是怎么做到的呢?

动态规划

和局部最优解对应的是全局最优解,而说到全局最优解,我们很难不想到动态规划这种算法。它是求全局最优解的一个利器。

如果你还没有了解过动态规划,建议你看一下海蓝大佬的 一文搞懂动态规划,也是这篇文章让我入门了最基础的动态规划。

动态规划中有一个很著名的问题:「01 背包问题」,题目的意思是这样的:

有 n 个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

关于 01 背包问题的题解,网上不错的教程似乎不多,我推荐看慕课网 bobo 老师的玩转算法面试 从真题到思维全面提升算法思维 中的第九章,会很仔细的讲解背包问题,对于算法思维有很大的提升,这门课的其他部分也非常非常的优秀。

我也有在我自己维护的题解仓库中对老师的 01 背包解法做了一个js 版的改写

那么 01 背包问题和这个瀑布流算法有什么关系呢?这个思路确实比较难找,但是我们仔细想一下,假设我们有 [1, 2, 3] 这 3 个图片高度的数组,我们怎么通过转化成 01 背包问题呢?

由于我们要凑到的是图片总高度的一半,也就是 (1 + 2 + 3) / 2 = 3,那么我们此时就有了一个 容量为3 的背包,而由于我们装进左列中的图片高度需要低于总高度的一半,待装进背包的物体的总重量和高度是相同的 [1, 2, 3]

那么这个问题也就转化为了,在 容量为3的背包 中,尽可能的从重量为 [1, 2, 3],并且价值也为 [1, 2, 3] 的物品中,尽可能的挑选出总价值最大的物品集合装进背包中。

也就是 总高度为3,在 [1, 2, 3] 这几种高度的图片中,尽可能挑出 总和最大,但是又小于3 的图片集合,装进数组中。

可以分析出 状态转移方程

dp[heights][height] = max(
  // 选择当前图片放入列中
  currentHeight + dp[heights - 1][height - currnetHeight], 
  // 不选择当前图片
  dp[heights - 1][height]
)

注意这里的纵坐标命名为 heights,代表它的意义是「可选择图片的集合」,比如 dp[0] 意味着只考虑第一张图片,dp[1] 则意味着既考虑第一张图片又考虑第二张图片,以此类推。

二维数组结构

我们构建的二维 dp 数组

纵坐标 y 是:当前可以考虑的图片,比如 dp[0] 是只考虑下标为 0 的图片,dp[1] 是考虑下标为 0 的图片,并且考虑下标为 1 的图片,以此类推,取值范围是 0 ~ 图片数组的长度 - 1

横坐标 x 是:用当前考虑的图片集合,去尽可能凑到总高度为 y 时,所能凑成的最大高度 max,以及当前所使用的图片下标集合 indexes,取值范围是 0 ~ 高度的一半

小问题拆解

就以 [1, 4, 5, 4] 这四张图片高度为例,高度的一半是 7,用肉眼可以看出最接近 7 的子数组是[1, 5],我们来看看动态规划是怎么求出这个结果的。

我们先看纵坐标为 0,也就是只考虑图片 1 的情况:

  1. 首先去尝试凑高度 1:我们知道图片 1 的高度正好是 1,所以此时dp[0][0]所填写的值是 { max: 1, indexes: [0] },也就代表用总高度还剩 1,并且只考虑图片 1 的情况下,我们的最优解是选用第一张图片。
  2. 凑高度2 ~ 7:由于当前只有 1 可以选择,所以最优解只能是选择第一张图片,它们都是 { max: 1, indexes: [0] }
高度       1  2  3  4  5  6  7
图片1(h=1) 1  1  1  1  1  1  1

这一层在动态规划中叫做基础状态,它是最小的子问题,它不像后面的纵坐标中要考虑多张图片,而是只考虑单张图片,所以一般来说都会在一层循环中单独把它求解出来。

这里我们还要考虑第一张图片的高度大于我们要求的总高度的情况,这种情况下需要把 max 置为 0,选择的图片项也为空。

let mid = Math.round(sum(heights) / 2)
let dp = []
// 基础状态 只考虑第一个图片的情况
dp[0] = []
for (let cap = 0; cap <= mid; cap++) {
  dp[0][cap] =
    heights[0] > cap
      ? { max: 0, indexes: [] }
      : { max: heights[0], indexes: [0] }
}

有了第一层的基础状态后,我们就可以开始考虑多张图片的情况了,现在来到了纵坐标为 1,也就是考虑图片 1 和考虑图片 2 时求最优解:

高度       1  2  3  4  5  6  7
图片1(h=1) 1  1  1  1  1  1  1
图片2(h=2)

此时问题就变的有些复杂了,在多张图片的情况下,我们可以有两种选择:

  1. 选择当前图片,那么假设当前要凑的总高度为 3,当前图片的高度为 2,剩余的高度就为 1,此时我们可以用剩余的高度去「上一个纵坐标」里寻找「只考虑前面几种图片」的情况下,高度为 1 时的最优解。并且记录 当前图片的高度 + 前几种图片凑剩余高度的最优解max1
  2. 不选择当前图片,那么就直接去「只考虑前面几种图片」的上一个纵坐标里,找到当前高度下的最优解即可,记为 max2
  3. 比较 max1max2,找出更大的那个值,记录为当前状态下的最优解。

有了这个前置知识,来继续分解这个问题,在纵坐标为 1 的情况下,我们手上可以选择的图片有图片 1 和图片 2:

  1. 凑高度 1:由于图片 2 的高度为 2,相当于是容量超了,所以这种情况下不选择图片 2,而是直接选择图片 1,所以 dp[1][0] 可以直接沿用 dp[0][0]的最优解,也就是 { max: 1, indexes: [0] }
  2. 凑高度 2:

    1. 选择图片 2,图片 2 的高度为 4,能够凑成的高度为 4,已经超出了当前要凑的高度 2,所以不能选则图片 2。
    2. 不选择图片 2,在只考虑图片 1 时的最优解数组 dp[0] 中找到高度为 2 时的最优解: dp[0][2],直接沿用下来,也就是 { max: 1, indexes: [0] }
    3. 这种情况下只能不选择图片 2,而沿用只选择图片 1 时的解, { max: 1, indexes: [0] }
  3. 省略凑高度 3 ~ 4 的情况,因为得出的结果和凑高度 2 是一样的。
  4. 凑高度 5:高度为 5 的情况下就比较有意思了:

    1. 选择图片 2,图片 2 的高度为 4,能够凑成的高度为 4,此时剩余高度是 1,再去只考虑图片 1 的最优解数组 dp[0]中找高度为 1 时的最优解dp[0][1],发现结果是 { max: 1, indexes: [0] },这两个高度值 4 和 1 相加后没有超出高度的限制,所以得出最优解:{ max: 5, indexes: [0, 1] }
    2. 不选择图片 2,在图片 1 的最优解数组中找到高度为 5 时的最优解: dp[0][5],直接沿用下来,也就是 { max: 1, indexes: [0] }
    3. 很明显选择图片 2 的情况下,能凑成的高度更大,所以 dp[1][2] 的最优解选择 { max: 5, indexes: [0, 1] }

仔细理解一下,相信你可以看出动态规划的过程,从最小的子问题 只考虑图片1出发,先求出最优解,然后再用子问题的最优解去推更大的问题 考虑图片1、2考虑图片1、2、3的最优解。

画一下[1,4,5,4]问题的 dp 状态表吧:

可以看到,和我们刚刚推论的结果一致,在考虑图片 1 和图片 2 的情况下,凑高度为 5,也就是dp[1][5]的位置的最优解就是 5。

最右下角的 dp[3][7] 就是考虑所有图片的情况下,凑高度为 7 时的全局最优解

dp[3][7] 的推理过程是这样的:

  1. 用最后一张高度为 4 的图片,加上前三张图片在高度为 7 - 4 = 3 时的最优解也就是 dp[2][3],得到结果 4 + 1 = 5。
  2. 不用最后一张图片,直接取前三张图片在高度为 7 时的最优解,也就是 dp[2][7],得到结果 6。
  3. 对比这两者的值,得到最优解 6。

至此我们就完成了整个动态规划的过程,得到了考虑所有图片的情况下,最大高度为 7 时的最优解:6,所需的两张图片的下标为 [0, 2],对应高度是 15

给出代码:

// 尽可能选出图片中高度最接近图片总高度一半的元素
let dpHalf = (heights) => {
  let mid = Math.round(sum(heights) / 2)
  let dp = []

  // 基础状态 只考虑第一个图片的情况
  dp[0] = []
  for (let cap = 0; cap <= mid; cap++) {
    dp[0][cap] =
      heights[0] > cap
        ? { max: 0, indexes: [] }
        : { max: heights[0], indexes: [0] }
  }

  for (
    let useHeightIndex = 1;
    useHeightIndex < heights.length;
    useHeightIndex++
  ) {
    if (!dp[useHeightIndex]) {
      dp[useHeightIndex] = []
    }
    for (let cap = 0; cap <= mid; cap++) {
      let usePrevHeightDp = dp[useHeightIndex - 1][cap]
      let usePrevHeightMax = usePrevHeightDp.max
      let currentHeight = heights[useHeightIndex]
      // 这里有个小坑 剩余高度一定要转化为整数 否则去dp数组里取到的就是undefined了
      let useThisHeightRestCap = Math.round(cap - heights[useHeightIndex])
      let useThisHeightPrevDp = dp[useHeightIndex - 1][useThisHeightRestCap]
      let useThisHeightMax = useThisHeightPrevDp
        ? currentHeight + useThisHeightPrevDp.max
        : 0

      // 是否把当前图片纳入选择 如果取当前的图片大于不取当前图片的高度
      if (useThisHeightMax > usePrevHeightMax) {
        dp[useHeightIndex][cap] = {
          max: useThisHeightMax,
          indexes: useThisHeightPrevDp.indexes.concat(useHeightIndex),
        }
      } else {
        dp[useHeightIndex][cap] = {
          max: usePrevHeightMax,
          indexes: usePrevHeightDp.indexes,
        }
      }
    }
  }

  return dp[heights.length - 1][mid]
}

有了一侧的数组以后,我们只需要在数组中找出另一半,即可渲染到屏幕的两列中:

this.leftImgIndexes = dpHalf(imgHeights).indexes
this.rightImgIndexes = omitByIndexes(this.imgs, this.leftImgIndexes)

得出效果:

优化 1

由于纵轴的每一层的最优解都只需要参考上一层节点的最优解,因此可以只保留两行。通过判断除 2 取余来决定“上一行”的位置。此时空间复杂度是 O(n)。

优化 2

由于每次参考值都只需要取上一行和当前位置左边位置的值(因为减去了当前高度后,剩余高度的最优解一定在左边),因此 dp 数组可以只保留一行,把问题转为从右向左求解,并且在求解的过程中不断覆盖当前的值,而不会影响下一次求解。此时空间复杂度是 O(n),但是其实占用的空间进一步缩小了。

并且在这种情况下对于时间复杂度也可以做优化,由于优化后,求当前高度的最优解是倒序遍历的,那么当发现求最优解的高度小于当前所考虑的那个图片的的高度时,说明本次求解不可能考虑当前图片了,此时左边的高度的最优解一定是「上一行的最优解」。

代码地址

预览地址

完整代码地址

总结

算法思想在前端中的应用还是可以见到不少的,本文只是为了演示动态规划在求解最优解问题时的威力,并不代表这种算法适用于生产环境(实际上性能非常差)。

在实际场景中我们可能一定需要最优解,而只是需要左右两侧的高度不要相差的过大就好,那么这种情况下简单的贪心算法完全足够。

在业务工程中,我们需要结合当前的人力资源,项目周期,代码可维护性,性能等各个方面,去选择最适合业务场景的解法,而不一定要去找到那个最优解。

但是算法对于前端来说还是非常重要的,想要写出 bug free 的代码,在复杂的业务场景下也能游刃有余的想出优化复杂度的方法,学习算法是一个非常棒的途径,这也是工程师必备的素养。

推荐

我维护了一个 LeetCode 的题解仓库,这里会按照标签分类记录我平常刷题时遇到的一些比较经典的问题,并且也会经常更新 bobo 老师的力扣算法课程中提到的各个分类的经典算法,把他 C++ 的解法改写成 JavaScript 解法。欢迎关注,我会持续更新。

参考资料

一文搞懂动态规划

玩转算法面试 从真题到思维全面提升算法思维

❤️ 感谢大家

1.如果本文对你有帮助,就点个赞支持下吧,你的「赞」是我创作的动力。

2.关注公众号「前端从进阶到入院」即可加我好友,我拉你进「前端进阶交流群」,大家一起共同交流和进步。

查看原文

赞 25 收藏 14 评论 5

认证与成就

  • 获得 433 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2019-07-22
个人主页被 2k 人浏览