面试算法题

发表于2024-10-10更新于2024-10-10

webpack和vite在开发和生产环境中的作用

在开发环境中，webpack将代码和依赖打包成浏览器可以运行的文件；vite则在浏览器原生的ES模块按需加载，避免预先打包带来的长时间等待
在生产环境中，Webpack 的主要功能是将所有的资源文件（JavaScript、CSS、图片等）打包、压缩、合并，并进行代码分割（Code Splitting）和按需加载（Lazy Loading）等优化操作，打包后，生成的静态文件可以部署到服务器上，用户访问时加载这些优化后的资源；vite在生产环境中也需要进行打包优化，Vite 使用 Rollup 作为其生产环境的打包器，它可以对代码进行类似的压缩、合并和优化。因此，Vite 也会在生产阶段生成静态文件，以便上线时部署到服务器。

webPack和vite的底层逻辑

webpack

依赖关系在打包中解决

模块打包：Webpack 的核心是将所有资源（JavaScript、CSS、图片等）作为模块，通过一个依赖图（Dependency Graph）进行解析，最终将这些模块打包成一个或多个文件。它采用了静态分析（Static Analysis）的方式，在编译时就解析代码依赖。
打包后运行：Webpack 的设计初衷是为了优化生产环境，最终生成的结果是打包后的静态文件。这意味着开发时需要进行编译和打包，项目启动速度可能较慢。
HMR（Hot Module Replacement）：Webpack 的热模块替换依赖于打包和构建后的文件，它通过 WebSocket 与浏览器通信，当源代码发生变化时，Webpack 会对变化的模块进行重编译，然后将更新后的模块发送到客户端进行替换。

Vite

根据依赖关系按需加载

基于 ES 模块：Vite 是基于浏览器的原生 ES Modules 机制进行开发的。它通过浏览器原生的模块解析能力，实现按需加载模块，而不是像 Webpack 一样先把模块全部打包成一个文件再加载。Vite 在启动时不需要预先打包，只需转换被请求的文件。
即时编译：Vite 使用 ESBuild 来进行快速的依赖解析，编译速度极快，因为 ESBuild 是用 Go 语言编写的，编译效率远高于 JavaScript 工具。它只会编译当前正在使用的文件，大幅缩短了开发环境的启动时间。
HMR（Hot Module Replacement）：Vite 的 HMR 通过 ESModules 的动态加载特性来实现，变化的模块会即时更新，不需要整个项目的重新构建。因此 HMR 反应速度更快。

webPack和vite的构建速度

Webpack：在 Webpack 中，构建大型项目时可能会出现性能瓶颈，尤其是依赖较多或模块化复杂的项目。Webpack 的构建优化主要依赖插件系统和缓存机制来提升打包效率。
Vite：Vite 的生产环境构建仍然依赖于 Rollup，它在生产环境的打包效率更高，但没有 Webpack 那么多的插件和扩展性。不过 Vite 对于现代前端开发的需求提供了较快的构建体验，尤其是其 ESBuild 的使用使得构建速度非常快。

社区生态与插件系统

Webpack：Webpack 的配置较为复杂，对于新手来说学习成本较高，需要理解模块解析、插件、Loader 等概念。尽管有 Webpack 5 的优化和简化，复杂的项目仍然需要较多的自定义配置。
Vite：Vite 的配置非常简单，开箱即用。默认配置可以满足大多数开发需求，几乎不需要额外的复杂配置。Vite 的配置文件 vite.config.js 也更加简洁，尤其是在开发现代化框架（如 Vue、React）时，Vite 提供了友好的集成。

使用场景

Webpack：Webpack 适合大型项目和复杂项目，它的打包机制和强大的插件系统能够处理多种文件格式、兼容旧版浏览器，并且具备良好的扩展性。
Vite：Vite 更适合现代化开发，尤其是现代框架如 Vue、React 等。它适合中小型项目或需要高效开发体验的项目，在开发环境下的表现尤为出色。

webpack配置

Webpack 配置是通过一个名为 webpack.config.js 的文件来完成的，这个配置文件定义了 Webpack 的入口、输出、加载器、插件以及其他打包过程中的各种选项。下面是 Webpack 配置的一些常见结构和示例：

const path = require('path');

module.exports = {
  // 入口文件
  entry: './src/index.js',

  // 输出
  output: {
    path: path.resolve(__dirname, 'dist'),  // 输出目录
    filename: 'bundle.js',                 // 输出文件名
  },

  // 模块加载器配置
  module: {
    rules: [
      {
        test: /\.js$/,                    // 匹配 .js 文件
        exclude: /node_modules/,          // 排除 node_modules 目录
        use: 'babel-loader',              // 使用 babel-loader 进行编译
      },
      {
        test: /\.css$/,                   // 匹配 .css 文件
        use: ['style-loader', 'css-loader'], // 使用 style-loader 和 css-loader
      },
      {
        test: /\.(png|jpg|gif)$/,         // 匹配图片文件
        use: [
          {
            loader: 'file-loader',
            options: {
              name: '[name].[ext]',
              outputPath: 'images/',     // 图片输出目录
            },
          },
        ],
      },
    ],
  },

  // 插件配置
  plugins: [
    // 插件实例，如 HtmlWebpackPlugin
  ],

  // 开发服务器配置
  devServer: {
    contentBase: path.join(__dirname, 'dist'),
    compress: true,
    port: 9000,                          // 服务器端口
  },

  // 模式（development、production）
  mode: 'development',
};

插件和babel的差别

Webpack 中的插件（Plugins）和 Babel 是两个不同的概念，它们在功能、用途和作用范围上都有显著区别。

插件

插件是 Webpack 提供的一种扩展功能，用于在打包的不同生命周期阶段对打包过程进行增强和扩展。它可以执行更复杂的任务，例如生成 HTML 文件、压缩代码、环境变量注入、清理输出目录等。插件的使用范围较广，作用不仅限于处理代码本身，还涉及文件生成、环境管理、构建过程控制等。

插件的主要功能
- 打包优化：压缩和混淆代码、代码分割、去除冗余代码。
- 生成额外文件：如生成 HTML 文件、CSS 文件、资产管理等。
- 清理目录：在打包之前自动清理输出目录。
- 管理环境变量：通过插件注入环境变量（如 DefinePlugin）。
- 其他功能：如生成文件报告、自动刷新浏览器、构建进度提示等。

常见的插件

HtmlWebpackPlugin：生成 HTML 文件并自动引入打包后的资源。
CleanWebpackPlugin：在打包之前清理输出目录。
MiniCssExtractPlugin：将 CSS 文件从 JS 中提取到单独的文件。
TerserPlugin：用于压缩和混淆 JavaScript 代码。

Babel

Babel 是一个 JavaScript 编译器，用于将现代 JavaScript 代码（ES6+）转换为向后兼容的版本（如 ES5），以便在老旧的浏览器或运行环境中也能正常工作。它主要解决的是代码语法和兼容性问题，例如将箭头函数、类、模块等新的 JavaScript 语法转换为旧版本浏览器支持的语法。

Babel 通常通过 Webpack 的加载器（Loader）来集成，它通过 babel-loader 在打包过程中将 JavaScript 文件进行编译。Babel 的作用是处理代码的转码，转换成兼容性更好的代码。

Babel 的主要功能

语法转换：将 ES6+ 语法转换为 ES5，例如箭头函数、let、const、类（class）等。
Polyfills：通过插件为新 API（如 Promise、Map）提供 Polyfill（垫片）。
模块化：支持模块化系统（import/export）的转换。

对比项	插件（Plugins）	Babel
功能范围	扩展 Webpack 构建的功能，控制构建生命周期	处理 JavaScript 代码的语法转换
主要用途	优化构建流程，生成额外文件、压缩代码、管理环境	将现代 JavaScript 代码转换为向后兼容的版本
作用范围	作用于整个构建过程，包括 HTML、CSS、JS、图片等资源	仅作用于 JavaScript 代码本身
使用方式	通过 plugins 配置项在 Webpack 配置中使用	通过 babel-loader 加载器在 Webpack 中使用
常见任务	HTML 文件生成、压缩、清理目录、代码分割、环境变量注入等	语法转换、Polyfill、模块转换

面试算法题

发表于2024-10-10更新于2024-10-11

用与渲染或服务端渲染

现在我们的项目大多数都是spa（单页面应用），感觉单页面应用比之前的模板渲染要好很多，首先单页面应用是前后端分离，架构清晰，前端负责交互逻辑，后端负责数据，前后端单独开发，独立测试。

但是，SPA不利于SEO（搜索引擎优化）。

那么为什么要做SEO？做SEO有什么好处？简单来说SEO是一种利用技术手段提升网站在搜索引擎之中的排名的方式，让搜索引擎更为信任网站，通过提升排名获得更多网站流量。

目前大部分的Vue项目本质是 SPA 应用，React、Angular也都是SPA应用。SPA应用广泛用于对SEO要求不高的场景中。

在我们开发的过程中，我们有 SEO 的需求，我们需要搜索引擎更多地抓取到我们的项目内容，此时我们需要SSR。SSR保证用户尽快看到基本的内容，也使得用户体验性更好。

SSR：服务端渲染（Server Side Render），即：网页是通过服务端渲染生成后输出给客户端。比如JSP、PHP、JavaWeb等都是SSR架构，也就是服务端取出数据和模板组合生成 html 输出给前端，前端发生请求时，重新向服务端请求 html 资源，路由也由服务端来控制。

预渲染：prerender-spa-plugin插件

prerender-spa-plugin是一个webpack的插件，在webpack的配置文件中配置该插件即可，在vue程序上有广泛的应用。

这种实现方式并不叫 SSR，而是预渲染。不过效果上是一样的，甚至某种程度上来说可能要比 SSR 更好。相比官方提供的 SSR 繁琐配置，prerender 配置更简单快捷，如无特殊要求只需在 webpack 中加一个 plugin 的配置。

这种方法简单、易上手、无需配置就能满足基本的 SEO 要求，但是不适合频繁变动的页面，因为预渲染只是类似于快照的概念。适用于静态页面，如博客、产品页面等不需要频繁更新的内容。它能够在构建时生成静态文件，因此加载速度非常快，尤其是在 CDN 上托管时效果更佳。

基于vue的预渲染

1、安装预渲染插件：
对于 Vite，你可以使用 vite-plugin-ssr 插件来实现预渲染。首先，需要安装该插件：

1	npm install vite-plugin-ssr --save-dev

对于 Webpack，你可以使用 prerender-spa-plugin 插件

1	npm install prerender-spa-plugin --save-dev

2、配置预渲染插件和构建项目：

基于vite
在 vite.config.js 中配置预渲染：

import { defineConfig } from 'vite';
import vue from '@vitejs/plugin-vue';
import { ssr } from 'vite-plugin-ssr/plugin';

// https://vitejs.dev/config/
export default defineConfig({
  plugins: [
    vue(),
    ssr({
      prerender: true, // 启用预渲染
      partial: true, // 只预渲染部分页面
      routes: ['/home'], // 指定预渲染的路由
    }),
  ],
});

使用npm run build构建项目，预渲染页面将生成在dist/client目录下
将 dist/client 目录下的内容部署到静态文件服务器上。对于非预渲染的页面，你需要一个 Node.js 服务器来处理动态路由。

基于webpack
在 Webpack 中，可以在 vue.config.js 或 webpack.config.js 中配置 prerender-spa-plugin：

const PrerenderSPAPlugin = require('prerender-spa-plugin');
const Renderer = PrerenderSPAPlugin.PuppeteerRenderer;
module.exports = {
  plugin: {
    new PrerenderSPAPlugin({
      staticDir: path.join(__dirname, 'dist'),
      routes: ['/home'], // 只预渲染首页
      renderer: new Renderer({
        inject: {
          foo: 'bar'
        },
        headless: true,
        renderAfterDocumentEvent: 'render-event'
      })
    })
  }
};

触发预渲染事件：在 Vue 应用中，可能需要在特定的生命周期钩子中触发一个事件，以告诉预渲染插件何时开始渲染页面。例如，在 mounted 钩子中触发一个事件：

new Vue({
  el: '#app',
  router,
  render: h => h(App),
  mounted () {
    document.dispatchEvent(new Event('render-event'));
  }
});

构建项目：npm run build

SSR

1、官方提供的轮子在node端做SSR，vue-SSR，上手复杂。

Nuxt.js

Nuxt.js是使用 Webpack 和 Node.js 进行封装的基于Vue的SSR框架，不需要自己搭建一套 SSR 程序，而是通过其约定好的文件结构和API就可以实现一个首屏渲染的 Web 应用。

学习视频

是什么

1、提供了前端和后端的全栈开发框架，前端基于vue，后端基于nitro
2、单页应用是客户端渲染，多页应用是服务端渲染

图 0

图 1

轨迹展示与展示

发表于2024-09-26更新于2024-10-08

背景介绍

基于PM2.5的健康路径规划项目，需要轨迹记录和轨迹展示功能。帮助用户记录出行轨迹，并提供分析PM2.5的吸入剂量。
图 0

图 1

主要涉及功能如下

实时采集用户轨迹并可视化在主页面地图中，点击开始按钮，采集开始，点击结束按钮采集结束，采集过程中支持暂停/继续
轨迹展示功能，点击轨迹在地图中生成轨迹图

亮点

定期推送功能
轨迹展示的灵活统计功能

设计思路

轨迹采集

两种策略：一种是暂存起来，定量推动到服务器。另外基于websocket实时推送

第一种策略实时性差，但是如果只是推送到服务器，不需要共享到其他用户，实时性不重要。前端可视化也不依赖于服务器的数据。第二种策略的实时性强，但是要保持持久连接较耗时。因此选择第一种。但是本文会给出两者的实现方法。

定量推送

主逻辑

定量推送数据：当 localStorage 中的数据量达到设定的阈值就推送到服务器。
因为网络异常推送失败或其他原因，localStorage 数据不断增加，导致容量接近上限时，上限是容量的2/3，将数据转移到 IndexedDB，继续保持数据采集。
顺序问题：当恢复网络时，必须优先推送 IndexedDB 中的数据，随后再推送 localStorage 中的数据，确保数据按时间顺序上传。
检测网络状态：navigator.onLine用于判断当前网络状态是否在线。online 和 offline 事件：分别在网络恢复和网络断开时触发。online 事件触发后立即尝试发送缓存数据，确保及时上传未发送的数据。
为保证上传顺序使用任务队列和互斥锁，避免上传任务的冲突。

采用互斥锁

在上传过程中引入一种互斥锁的机制，确保在上传过程中不会重复访问同一份数据。这样在上传过程中，即使有新的数据加入到 localStorage，也不会与当前正在上传的数据发生冲突。避免了多个上传任务可能同时进行，导致并发冲突，比如数据重复上传、数据上传顺序错乱等问题

如何实现：在 JavaScript 的单线程环境中，虽然没有直接的互斥锁机制，但我们可以通过标志位（flag）的方式实现互斥锁的效果。

在我们的实现中，isUploading 就相当于一个互斥锁，它用来标记当前是否有上传任务正在进行：

1
2

let isUploading = false; // 标志是否正在上传数据
锁定（加锁）：当开始执行上传任务时，我们将 isUploading 设为 true，这就相当于上了锁，表示系统正在上传数据。

1
2

isUploading = true; // 加锁，表示系统正在执行上传任务
解锁：上传任务完成后，记得将 isUploading 设为 false，解锁表示上传任务完成，允许下一次上传开始。

1
2
3


isUploading = false; // 解锁，表示上传任务完成
在上传任务的开始处，我们通过判断 isUploading 来决定是否执行上传任务。如果 isUploading 为 true，则跳过当前任务，以避免多个上传任务同时进行：

1	if (isUploading) return; // 如果已加锁（正在上传），直接返回，不执行新的上传任务

实现

1. 数据采集与存储
- 使用 navigator.geolocation 进行轨迹点的实时采集。每次采集到一个点后，立即将其存入 localStorage 中。
- 在 localStorage 达到容量的 2/3 时，将数据转移到 IndexedDB 中以防止 localStorage 的存储容量不足。
- 轨迹点数据的采集频率不依赖于网络状态，数据始终保持持续采集。
1. 任务队列与上传机制
- 使用任务队列来管理数据上传过程，确保即使有多个任务并发执行时，上传操作不会发生冲突。
- 每次采集到的数据会在 localStorage 中暂存。当数据量达到一定的阈值（如 500 个点），或者网络恢复时，系统会尝试将数据上传到服务器。
- 如果当前已有正在执行的上传任务，则新的上传任务会被添加到任务队列中，等待前一个任务完成后依次执行。这样可以避免同时多个上传任务导致的冲突。
1. 网络状态检测与数据传输
- 系统实时监控网络状态，当网络断开时，数据会继续存储到 localStorage 或 IndexedDB 中，而不会尝试上传。
- 当网络恢复时，会优先处理任务队列中的上传任务，将缓存中的数据（优先从 IndexedDB，然后是 localStorage）上传至服务器。
1. 上传过程与冲突管理
- 通过任务队列机制来防止并发上传冲突：当一个上传任务正在进行时，新的上传任务不会立即执行，而是加入队列等待当前任务完成。
- 在上传成功后，系统会清理已上传的数据（从 localStorage 或 IndexedDB 中删除），并继续处理下一个上传任务，直到所有缓存的数据都上传完成。
1. 数据传输与顺序维护
- 当网络恢复时，系统首先检查 IndexedDB 中的数据。由于 IndexedDB 保存的是 localStorage 中超过容量的数据，因此 IndexedDB 中的数据应优先上传。
- 在 IndexedDB 的数据上传完成后，系统会继续处理 localStorage 中的数据，保证传输顺序的正确性。

实时推送

主逻辑

获取到一个点数据就备份到localStorage中，然后推送到服务端，同送成功将备份删除。
遇到websocket断开的的情况，将数据保存如localStorage，链接回复，将localStorage的数据推送到服务端，推送成功就删除localStorage中的数据。

推送顺序问题

点的顺序对轨迹来说是重要的，因此需要确保数据库中存储的点的数据是正确的，每一个点数据有时间戳，可以在后端进行排序。也可以在前端控制推送顺序，使用双队列。从复杂度上说前端复杂度较小，因此选择前端处理的方式。

实现

1. 数据采集与存储
- 使用 navigator.geolocation 进行轨迹点的实时采集，每次采集到一个点后，立即将其存入实时队列，并将该数据缓存到 localStorage 中。
- 实时队列用于存储采集到的新数据，实时发送给服务端；localStorage 则作为本地缓存，防止断网或其他异常情况下数据丢失。
1. WebSocket 连接与重连机制
- WebSocket 建立后，若连接成功，会开始发送实时数据，并检查是否有缓存的轨迹数据（localStorage 中）。
- 若WebSocket 连接断开，会进入重连模式，在重连成功后立即尝试将缓存中的数据发送到服务器。
1. 双队列管理
  实时队列：存储正在采集的数据，WebSocket 连接正常时，直接发送数据给服务端。
- 缓存队列（localStorage）：当 WebSocket 连接断开时，实时队列中的数据存储到 localStorage 中；当连接恢复时，发送缓存队列的数据。
1. 数据传输与顺序维护
- 当网络恢复时，先将 localStorage 中的数据传输到服务端，随后再发送实时队列中的新数据，确保传输顺序不乱。
1. localStorage 清空与缓存清理
- 在 WebSocket 连接恢复后，成功发送缓存队列的数据后，立即从localStorage 中删除已成功推送的数据。
- 避免重复发送数据，确保只发送最新数据。

历史轨迹展示

可以根据年、月、周、日来统计和显示轨迹，对后端传来的数据进行处理统计，统计原则根据用户的设置决定，生成用于渲染的数据。点击每一条数据在地图上生成轨迹。

亮点

轨迹数据的层次化管理，需要对后端返回的扁平数据进行处理，将数据转化为多层次的树状结构。这样可以让前端在展示时按年、月、周、日等不同粒度进行分组。

图 2

图 3

图 4

图 5

图 6

vue模拟抖音

发表于2024-09-20更新于2024-09-24

自适应调整页面-rem和vh/vw

简介使用rem适应不同终端的变化，调整页面元素的大小。
使用动态计算vh的目的是，因为移动端的地址栏的出现与消失会影响也页面视窗的高度即vh。因此需要动态计算。
图 2

核心问题是移动浏览器（Chrome 和 Safari）有一个“有用”的功能，地址栏有时可见，有时隐藏，从而改变视口的可见大小。这些浏览器并没有随着视口高度的变化而将高度调整100vh为屏幕的可见部分，而是将100vh地址栏设置为隐藏地址的浏览器高度。结果是，当地址栏可见时，屏幕的底部将被切断，从而违背了100vh最初的目的。

rem

rem 的值是根据根元素 html 字体大小的来计算的，即1rem = html font-szie，
如果 html 元素没有指定字体大小，那么浏览器默认的字体大小是 16px ，所以 1rem = 16px
如果 html 元素指定 font-size: 1px ，那么 1rem = 1px
同理 html 元素指定 font-size: 3px ，那么 1rem = 3px
同理 html 元素指定 font-size: 1000000px ，那么 1rem = 1000000px
同理 html 元素指定 font-size: 0.000001px ，那么 1rem = 0.000001px

rem和em的区别

em 是以父元素的字体大小来计算; rem 顾名思义,就是 root 的 em，所以它是以html的字体大小来计算

不同屏幕自适应

不同用户的设备屏幕宽度不同，若每个用户对应的 html 元素 font-size 值相同的话，用户看到的显示效果也是不同的。

可以用 JavaScript 来根据用户的屏幕宽度，动态更改 html 元素上的 font-size 值，从而使实际显示的内容比例始终保持不变，不同用户看到的效果也会保持一致。

比如，设计稿的宽度为 400px ，里面显示了一个宽度为 40px 的盒子。某用户以 800px 宽度的设备来访问，看到的盒子宽度应该为 80px。那么此时在 html 元素的 font-size 值设置为 2px ，然后盒子的宽度采用 rem 单位，设置为 40rem ，那么就能显示出 80px 的盒子了。保持用户看到的和设计稿中的效果比例一致。

所以，html元素的font-size计算公式为：

1 2	// 用户设备宽度 / 设计稿标准宽度 document.documentElement.style.fontSize = document.documentElement.clientWidth / 375 + 'px'

vh

vh 和 vw 都是相对于视窗的宽高度，“视窗”所指为浏览器内部的可视区域大小，即window.innerWidth/window.innerHeight大小，不包含任务栏标题栏以及底部工具栏的浏览器区域大小。可以简单理解为屏幕百分比，1vh = 屏幕的1%

移动端 100vh 显示 bug

vh 在移动端的Chrome 和 Safari上会显示溢出，如下图

图 3

当地址栏处于视图中时，元素底部被裁剪（右），但我们想要的是元素能完整的占据一屏（左）。
造成这种现象的原因就在于移动端浏览器对于 vh 单位的计算，是不包含地址栏的，也就是说 100vh 的高度会使带有地址栏的视图溢出。

解决方法

使用 window.innerHeight 获取当前视窗的的高度，将高度按 100 份等分，得到视窗的单位高度, 然后通过 js 设置成一个 css 的变量 --vh。

1	document.documentElement.style.setProperty('--vh', `${vh}px`)

css中使用

//表示100vh
height: calc(var(--vh, 1vh) * 100);

//100vh - 60rem
height: calc(var(--vh, 1vh) * 100 - 60rem);

代码

function resetVhAndPx() {
  let vh = window.innerHeight * 0.01
  document.documentElement.style.setProperty('--vh', `${vh}px`)
  document.documentElement.style.fontSize = document.documentElement.clientWidth / 375 + 'px'
}

onMounted(() => {
  resetVhAndPx()
  // 监听resize事件 视图大小发生变化就重新计算1vh的值
  window.addEventListener('resize',resetVhAndPx)
})

实现原理

无限滑动的原理和虚拟滚动的原理差不多，要保持 SlideList 里面永远只有 N 个 SlideItem，就要在滑动时不断的删除和增加 SlideItem。
滑动时调整 SlideList 的偏移量 translateY 的值，以及列表里那几个 SlideItem 的 top 值，就可以了

为什么要调整 SlideList 的偏移量 translateY 的值同时还要调整 SlideItem 的 top 值呢？
因为 translateY 只是将整个列表移动，如果我们列表里面的元素是固定的，不会变多和减少，那么没关系，只调整　translateY 值就可以了，上滑了几页就减几页的高度，下滑同理

但是如果整个列表向前移动了一页，同时前面的 SlideItem 也少了一个，，那么最终效果就是移动了两页…因为塌陷了一页
这显然不是我们想要的，所以我们还需要同时调整 SlideItem 的 top 值，加上前面少的 SlideItem 的高度，这样才能显示出正常的内容

大文件续传

发表于2024-09-20更新于2024-09-28

是什么

针对问题：
在同一个请求中，要上传大量的数据，导致整个过程会比较漫长，且失败后需要重头开始上传。
解决思路：
将这个请求拆分成多个请求，每个请求的时间就会缩短，且如果某个请求失败，只需要重新发送这一次请求即可，无需从头开始，这样是否可以解决大文件上传的问题呢？
要求
- 支持拆分上传文件请求
- 支持断点续传
- 支持显示上传进度和暂定进度
技术
- webWorker:
  是一种在后台线程中运行脚本的技术，允许开发者在不阻塞用户界面的情况下执行复杂和耗时的任务。Web Worker 提供了一个独立的执行环境，与主线程（UI 线程）隔离开来，避免了长时间运行的脚本导致的页面卡顿。

逻辑

1、将上传的文件切片，并对每个切片标上记号，是哪个文件的切片是切片的那一部分（用hash实现标记）
2、后端把成功的标记记录下来，上传每个文件时，都判断一下标记是否存在，如果存在不上传，如果存在就上传。
3、后端对上传完整的文件切片进行拼接。

细节

webworker 处理对文件的切片

webWorker的特点

独立线程：Web Worker 在独立的线程中运行，与主线程并行执行。
无阻塞：由于在独立线程中运行，Web Worker 不会阻塞主线程的执行。
通信机制：主线程和 Worker 线程之间通过消息传递（postMessage 和 onmessage）进行通信。
受限环境：Worker 线程不能访问 DOM，也不能调用一些特定的 Web API，如 alert 和 localStorage。

基本用法

监听消息事件

self.addEventListener('message', async e => {
  console.log(e)
  const { file, chunkSize } = e.data
  const fileChunkList = await createFileChunk(file, chunkSize)
  await calculateChunksHash(fileChunkList)
})

监听错误事件

self.addEventListener('error', function (e) {
  console.log("%cWorker 线程 error 监听事件: ", 'color: red', e)
  // worker 线程关闭
  self.close()
})

切片实现

1、文件切片

//第一个参数是file，第二个是切片大小
function createFileChunk(file, chunkSize) {
  // new Promise 的基本用法：来创建一个新的 Promise 对象,该函数有两个参数：resolve 和 reject。
  //resolve 用于在异步操作成功时返回结果，reject 用于在异步操作失败时返回错误。
  return new Promise(resolve => {
    let fileChunkList = []
    let cur = 0
    while (cur < file.size) {
      fileChunkList.push({ chunkFile: file.slice(cur, cur + chunkSize) })
      cur += chunkSize
    }
    resolve(fileChunkList)
  })
}

切片标记

每个切片有自己的MD5哈希值，所有切片的哈希值保存在SparkMD5.ArrayBuffer 实例spark中，在切片完成后，spark值传递给fileHash，webWork将fileHash和fileChunkList文件切片传给了主线程。

// 记载并计算文件切片的 md5
async function calculateChunksHash(fileChunkList = []) {
  // 创建一个 SparkMD5.ArrayBuffer 实例，用于计算 MD5 哈希值。
  const spark = new SparkMD5.ArrayBuffer()

  // 计算切片进度
  let percentage = 0

  try {
    const fileHash = await loadNext()
    self.postMessage({ percentage: 100, fileHash, fileChunkList })
    self.close()
  } catch (err) {
    self.postMessage({ name: 'error', data: err })
    self.close()
  }

  // 递归函数，处理文件的切片
  async function loadNext(index = 0) {
    // 所有的切片都已处理完毕
    if (index >= fileChunkList.length) {
      // 返回这个文件的MD5哈希值
      return spark.end()
    }
    return new Promise((resolve, reject) => {
      const reader = new FileReader()
      reader.readAsArrayBuffer(fileChunkList[index].chunkFile)
      reader.onload = (e) => {
        spark.append(e.target.result)
        percentage += 100 / fileChunkList.length
        self.postMessage({
          percentage
        })
        resolve(loadNext(index + 1))
      }
      reader.onerror = (err) => reject(err)
    })
  }
}

主线程任务

该方法能依次上传多个文件。
切片大小设置为5MB
多个文件输入处理逻辑：
- 如果输入框有change事件，判断是否有文件传入，如果有将每个文件进行切片处理，并上传
- 对每个文件绑定响应式对象，对象包括文件名、文件大小、文件状态、所有需要上传的切片、文件hash、最大报错次数、上传进度等属性。
- 根据文件的状态来确定，当前文件需要进行的流程。
- 需要切片上传的文件，交给webworker切片，并将结果返回。作为参数传给开始上传函数
- 多个文件并行上传
开始上传文件的逻辑：
- 需要参数，file，inTaskArrItem（初始化的一个对象，包含单个文件的属性）， fileChunkList（单个文件的切片）
- 判断文件是否已经存在于服务器，如果存在直接return，如果不存在执行上传的逻辑
- 将每个切片的信息写入inTaskArrItem的allChunList（所有需要上传的切片）中
- 对allChunkList进行过滤，过滤掉已经上传成功的切片（判断是否上传成功，由checkfile函数完成）
- 如果没有需要上传的切片，但是前面判断服务器中没有此文件，说明需要合并，再次执行文件合并函数
每一个文件的处理逻辑
- 如果没有需要上传的切片或者状态为正在被上传，不做处理
- 找出需要上传的文件，并将入待处理文件的列表中。根据列表长度计算每个文件的并发请求数量。（chrome浏览器同域名同一时间请求的最大并发数限制为 6，如果有三个文件需要上传，那么每个文件上传只能同时并发2个请求）
- 从需要上传的切片尾部拿2个切片，放入请求数组中。并将其从allChunkList中删除
- 开始上传切片
切片上传逻辑
- 首先判断文件状态，如果文件状态为暂停或终端就什么都不错
- 每个切片由三次机会，如果三次都失败，则文件上传失败

图片懒加载

发表于2024-09-20更新于2024-09-20

图片懒加载

简介

图片懒加载是一种前端性能优化技术，它通过延迟非关键资源（如图片）的加载时机，直到这些资源即将被用户看到内或者经过一定的延迟后，才开始加载，从而减少初次页面加载的时间和数据使用量，提高用户体验。
本文总结的图片懒加载技术依赖vue，并将其封装为一个插件
支持组件可见或即将可见时懒加载
支持加载真实组件前展示骨架组件，提高用户体验

涉及的属性

非响应式

1.timeout:

类型：Number
作用：指定延迟加载的时间（以毫秒为单位）。如果设置了这个属性，组件将在指定时间后初始化。

2、tagName:

类型：String
默认值：’div’
作用：指定包裹内容的 HTML 标签名称。默认是 div，可以根据需要更改为其他标签。

3、viewport:

类型：HTMLElement 或 Object
默认值：null
作用：指定视口元素，用于 IntersectionObserver。如果没有指定，默认是 null，表示使用浏览器的视口。

4、threshold:

类型：String
默认值：’0px’
作用：指定触发懒加载的阈值。可以设置为像素值或百分比，例如 ‘100px’ 或 ‘50%’。

5、direction:

类型：String
默认值：’vertical’
作用：指定滚动方向。可以是 ‘vertical’（垂直方向）或 ‘horizontal’（水平方向）。

6、maxWaitingTime:

类型：Number
默认值：50
作用：指定最大等待时间（以毫秒为单位），用于 requestAnimationFrame 回调，防止主线程卡顿。

这些属性允许用户在使用 VueLazyComponent 时进行灵活配置，以满足不同的需求。

响应式

1、isInit:

类型：Boolean
默认值：false
作用：表示组件是否已经初始化。当组件完成初始化时，这个值会被设置为 true。

2、timer:

类型：null 或 Number
默认值：null
作用：用于存储定时器的引用。如果设置了 timeout 属性，组件会在指定时间后初始化，这个定时器用于实现这个功能。

3、io:

类型：null 或 IntersectionObserver
默认值：null
作用：用于存储 IntersectionObserver 的实例。IntersectionObserver 用于检测组件是否进入视口，以便延迟加载内容。

4、loading:

类型：Boolean
默认值：false
作用：表示组件是否正在加载内容。当组件开始加载内容时，这个值会被设置为 true。

这些数据属性用于管理组件的状态和行为。通过响应式的数据属性，Vue.js 可以在数据变化时自动更新视图，从而实现动态和交互式的用户界面。

功能详解

懒加载内容

IntersectionObserver是浏览器内置API，用于异步观察一个目标元素与其祖先元素或顶级文档视口（viewport）交叉状态的变化。它可以用于实现懒加载、无限滚动、广告曝光监测等功能。
IntersectionObserver 构造函数用于创建一个新的 IntersectionObserver 实例。它接受两个参数：
- 回调函数（callback）：当目标元素的可见性发生变化时，这个回调函数会被调用。
- 选项对象（options）：用于配置 IntersectionObserver 的行为。
  可选参数，用于配置 IntersectionObserver 的行为。包含以下属性：
  - root：指定用作视口的元素，必须是目标元素的祖先元素。默认是浏览器的视口。
  - rootMargin：用于扩展或缩小 root 元素的边界，类似于 CSS 的 margin 属性。可以使用像素值或百分比。
  - threshold：一个数值或数值数组，表示目标元素的可见比例达到这些值时，回调函数会被触发。

骨架展示

模板中的条件渲染：

使用 v-if 和 v-else-if 指令根据 isInit 状态渲染实际内容或骨架屏。
isInit 为 false 时显示骨架屏，为 true 时显示实际内容。

<template>
  <transition-group :tag="tagName" name="lazy-component" style="position: relative;"
    @before-enter="(el) => $emit('before-enter', el)"
    @before-leave="(el) => $emit('before-leave', el)"
    @after-enter="(el) => $emit('after-enter', el)"
    @after-leave="(el) => $emit('after-leave', el)"
  >
    <div v-if="isInit" key="component">
      <slot :loading="loading"></slot>
    </div>
    <div v-else-if="$slots.skeleton" key="skeleton">
      <slot name="skeleton"></slot>
    </div>
    <div v-else key="loading">
    </div>
  </transition-group>
</template>

过渡动画

transition-group：

使用 transition-group 包裹内容，实现内容切换时的过渡动画。
通过 @before-enter、@before-leave、@after-enter 和 @after-leave 事件触发父组件的相应事件。

事件通知

在组件生命周期的不同阶段触发事件，通知父组件。

逻辑

首先搞清楚，这里的懒加载是指以显示骨架内容代替真实数据，，等到有需要的时候再加载真实数据。
在视口加载和超过设定时长自动加载，两者通过timeout属性决定，timeout为true使用延时加载，否则使用视口加载模式
初始化是指加载真实数据的组件，即将loading指改为true。
在挂载时，如果timeout值为加假，说明要使用视口交叉来懒加载图片。需要初始化视口交叉监视API：IntersectionObserver
在创建阶段，如果指定timeout则无论可见与否都是在timeout之后初始化
销毁：在组件销毁前取消观察
然后这里还定义了一些自定义函数，供插件使用者监听组件的状况。

数组

发表于2024-09-20更新于2024-10-08

数组

移除元素

图 0

首先数组在计算机中的存储实在连续的内存空间内，因此删除数组中的数据，其实是用后面的数据覆盖被删除的数据，然后修改数组的长度。

方法有暴力破解和双指针法

双指针原理使用一对快慢指针将，慢指针质量需要被移除的位置，快指针指向替代移除元素的元素。

var removeElement = function(nums, val) {
    let slow = 0
    for(let fast=0;fast<nums.length;fast++){
      //元素不等于val时，快慢指针一同增加，
      //一旦有元素等于val，说明这个元素需要被覆盖,那就让快指针去找不等于val的元素
        if (nums[fast]!=val){
            nums[slow++] = nums[fast]
        }
    }
    nums.length = slow
    console.log(nums)
    // return nums
};

大文件续传

发表于2024-09-20更新于2024-10-09

回调函数

回调函数（callback function）是一种函数，它作为参数传递给另一个函数，并在某个特定时间点被调用。
回调函数是以函数作为参数传递并在调用者中执行的函数。它允许程序在异步任务完成时执行特定的操作。

语法

有名的回调函数语法

function mainFun(callback){
  callback()  //调用
}

//定义回调函数
function afun(){
  console.log('这是一个回调函数')
}

mainFun(afun)   //输出：这是一个回调函数

匿名回调函数语法

function mainFun(callback){
  // 调用回调函数并传递参数
  callback()
}

mainFun(()=>{
  console.log('hello,我是个回调函数哈')
})
//

回调函数的参数

function mainFun(callback){
  callback('hello','我是一个回调函数')
}

function myCallback(param1,param2){
  console.log(param1+param2)
}

mainFun()

应用

事件处理

事件处理在浏览器环境中，事件处理器是回调函数的一个常见应用。例如，监听按钮的点击事件时，可以传入一个回调函数来定义当按钮被点击时要执行的逻辑。

1
2
3

document.getElementById("mybutton").addEventListener('click',function(){
  console.log("button clicked")
})

定时器

定时器 setTimeout 和 setInterval 是 JavaScript 中定时器的两个函数，它们都会接受一个回调函数。该回调函数会在指定的时间后执行。

1
2
3

setTimeout(function(){
  console.log('三秒后执行该函数')
},3000)

异步操作

异步操作（例如 AJAX 请求）回调函数在处理异步操作时非常有用。通过回调函数，可以在服务器返回数据后进行处理，而无需阻塞代码的执行

function fetchData(url,callback){
  fetch(url)
  .then(response=>response.json())
  .then(data=>callback(data))
  .catch(erro=>console.error('Error',error))
}

fetchData('https://api.example.com/data',function(){
  console.log('Received data:', data)
})

数组中的回调函数

数组方法中的回调数组的 map、filter、reduce 等高阶函数都使用回调函数来对数组中的每个元素进行处理。

let numbers = [1,2,3,4,5,6]
let squares = numbers.map(function(num){
  return num*num
})
console.log(squares)  // [1, 4, 9, 16, 25, 36]

回调地狱

当回调函数嵌套得过深时，代码会变得难以维护和阅读，这被称为回调地狱。

function firstFunction(callback) {
  setTimeout(function() {
    console.log("First function done");
    callback();
  }, 1000);
}

function secondFunction(callback) {
  setTimeout(function() {
    console.log("Second function done");
    callback();
  }, 1000);
}

firstFunction(function() {
  secondFunction(function() {
    console.log("All done!");
  });
});

关于回调的困惑

一直以来我都觉得回调函数执行是有顺序的为什么说是异步操作。

回调函数的执行顺序确实会让人误以为它们是同步操作。但实际上，JavaScript 的回调函数在很多情况下是用于异步操作的，而这正是区分回调函数同步与异步执行的关键。

函数内部的回调执行是同步的：当我们在某个函数内部调用回调函数时，它是按照正常的函数调用顺序执行的。比如，当我们直接调用一个回调函数，它的执行过程和普通函数是一样的，是同步进行的。
回调函数在异步操作中显得是异步的：如果回调函数被用于处理异步操作（如定时器、网络请求、事件监听等），那么它的执行不会阻塞主线程，JavaScript 会先继续执行后面的代码。等到异步操作完成后，再执行回调函数，这种情况下回调函数相对于外面的代码是异步的。

异步执行的原因

JavaScript 是单线程的，这意味着它一次只能做一件事。但是，现代应用中有很多耗时的任务，比如：

读取文件
发送网络请求
数据库查询
定时操作（setTimeout 或 setInterval）

如果 JavaScript 是阻塞式的（即同步操作），它就无法同时处理多个任务。为了避免这种情况，JavaScript 引入了异步编程模型，通过回调函数、Promise 或 async/await 来处理那些需要较长时间完成的任务。

当异步操作执行时，JavaScript 引擎并不会阻塞主线程。相反，它会继续执行后续代码，直到异步操作完成。等到异步操作完成时，事件循环（event loop）将回调函数放入执行队列中，这时回调函数才会被执行。

事件循环（Event Loop）与回调函数

JavaScript 的事件循环是异步回调背后的核心机制。简单来说，JavaScript 的运行时环境由调用栈和任务队列组成：

调用栈：用来执行同步代码，函数按照调用顺序依次入栈和出栈。
任务队列：异步操作完成后，回调函数会被放入任务队列中等待执行。

当调用栈中的任务执行完毕（即同步代码全部完成），事件循环会从任务队列中取出回调函数，放到调用栈上执行。

面试算法题

发表于2024-09-18更新于2024-09-18

面试算法题

发表于2024-09-10更新于2024-10-08

双指针系列

合并两个有序数组

图 0

解决思路

逆向双指针，从后往前比较两个数组的元素大小。大的填入应在的位置，然后指针前移，小的不作操作。

代码

// 逆向双指针的方法
var merge = function(nums1, m, nums2, n) {
  let p1 = m-1,p2 = n-1,p = m+n-1  //三个指针，第一个用来遍历数组1中的每个值。
  //第二个用来遍历数组2中的每一个值，第三个用来存数据，从数组1的最后一个位置开始。
  while(p1>=0 && p2>=0){ // 双指针，从两个数组的最后一个数开始，倒着比较值的大小。
    if (nums2[p2]>=nums1[p1]){
      nums1[p] = nums2[p2]
      p2--
    }
    else{
      nums1[p] = nums1[p1]
      p1--
    }
    p--
  }
  while(p2>=0){//如果数组2中还有剩余的元素，全部放在数组1的前面
    nums1[p] = nums2[p2]
    p2--
    p--
  }
};

最长无重复子串

图 5

解题思路

滑动窗口

1、使用left和right两个指针，分别表示滑动窗口的左右边界，初始时都指向字符串的开头。
2、使用一个哈希表（或者数组）来记录字符是否出现过以及字符出现的位置。
3、不断移动右指针 right，每次移动时判断当前字符是否出现过：
- 如果当前字符已经出现过，并且在当前窗口内（即其位置大于等于 left），则更新 left 指针的位置为该字符上次出现的位置的下一个位置。
- 如果当前字符没有出现过，或者虽然出现过但不在当前窗口内，则更新最长子字符串的长度。
不断更新最长子字符串的长度，并返回结果。

代码

var lengthOfLongestSubstring = function(s) {
  let l=0,r=0,max=0
  let map = new Map()
  while(r<s.length){
    //判断map的记录中，这个字符的值是否在滑动窗口内
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      //如果在窗口内l指针指向当前记录值的后一位
      l = map.get(s[r])+1
    }
    //如果map中没有当前字符得记录或者有记录但是不在滑动窗口范围内
    map.set(s[r], r)
    max = Math.max(max, r - l + 1)
    r++
  }
  return max
}

判断子序列

图 6

解题思路

初始化指针i，j分别指向字符串是，和t的起始位置；其中s是子串，t是较长的字符串
遍历比较s[i]和t[j]的情况
- 如果s[i]==t[j]，那么指向子串的指针+1，即i++；且j++
- 如果不想等j++
判断子序列：如果 i 移动到了 s 的末尾，则说明 s 是 t 的子序列，返回 true；否则返回 false。

代码

var isSubsequence = function(s, t) {
  let i=0,j=0
  //处理两个字符串都是空字符串的情况
  if (s==t) return true
  while (j<t.length){
    if (s[i]===t[j]) i++
    j++
  }
  if (i==s.length) return true
  else return false
};

两数之和

图 1

解题思路

使用字典,判断目标值减去当前值的结果是否，存在于字典中。

代码

var twoSum = function(nums, target) {
  let map = new Map()
  // 判断target-当前元素的结果是否存在于map中，如果存在返回下标
  for (let i=0;i<nums.length;i++){
    if (map.has(target-nums[i])){
      return [map.get(target-nums[i]),i]
    }
    //如果不存在，设置当前元素为键，当前元素下表为值
    else{
      map.set(nums[i],i)
    }
  }
}

三数之和

图 2

解决思路回溯算法：

1、回溯的三部曲，参数确定，确定终止条件，单层递归逻辑。提升效率要剪枝
2、双指针法：对数组进行排序，先确定第一个数字，然后使用双指针分别总数组的第一个和第最后一个开始，判断当前总和，综合大，右边指针前移，否者左边指针后移。

去重逻辑：第一个数字的去重，和后面两个数字的去重。

代码

var threeSum = function (nums) {
  let res = []
  nums = nums.sort((a,b)=>a-b) //首先要进行排序
  for (let i = 0; i < nums.length-2; i++) {  //减2是因为求得是三个元素的和。
    if (i > 0 && nums[i] == nums[i - 1]) continue //a去重
    let left = i + 1,right = nums.length - 1 //指定双指针
    while (left < right) {
      let sum = nums[i]+nums[left]+nums[right]
      if (sum>0) right--
      if (sum<0) left++
      if(sum===0){
        res.push([nums[i],nums[left],nums[right]])
        //后两个数去重逻辑，如果指针指向下一个元素与当前相同，跳过该元素
        while(left<right && nums[left] === nums[left+1]) left++
        while(left<right && nums[right] === nums[right-1]) right--
        left++     //忘记调整这两个了
        right--
      }
    }
  }
  return res
}

反转链表

图 3

自定义链表

解题代码

var reverseList = function(head) {
  let prev = null
  let cur = head
  while(cur){
    // 这一步我忘记了，没有把next的值保存下来，直接给cur.next赋值了
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev //最后一个cur是null，他前面一个才是第一个有值的节点
};

排序算法

快速排序

其核心思想是分治，选择一个基准元素，将比基准小的元素放在左边，比基准大的元素放在右边。然后地柜对左右两个部分，分别进行快速排序。

快速排序复杂度
平均时间复杂度（Onlogn）、最坏情况O(n^2)

function quickSort(arr) {
  //终止条件
  if (arr.length <= 1) return arr
  //找基准,选择最后一个元素作为基准
  let std = arr.length - 1
  //用来存储左右两个数组
  let leftArr = [],
    rightArr = []
  for (let i = 0; i < std && i != std; i++) {
    if (arr[i] <= arr[std]) leftArr.push(arr[i])
    else rightArr.push(arr[i])
  }
  //分别处理左右两个子数组
  return [...quickSort(leftArr), arr[std], ...quickSort(rightArr)]
}
console.log(quickSort([5, 2, 9, 1, 7, 6,3,80,34]))

选择排序

选择最大的数，放在数组的最右边，然后再选择第二大的数，放在数组的右边第二的位置，以此类推。

选择排序复杂度
平均时间复杂度（Onlogn）、最坏情况O(n^2)

function selectSort(arr){
  const n = arr.length-1
  // 从后往前排好arr的顺序，所以遍历从后往前
  for (let i=n;i>0;i--){
    let maxIndex = i
    // 将没排好序的过一遍
    for (let j=0;j<=i;j++){
      if (arr[j]>arr[maxIndex]) maxIndex = j
    }
    if (maxIndex != i){
      [arr[maxIndex],arr[i]] = [arr[i],arr[maxIndex]]
    }
  }
  return arr
}

冒泡排序

冒泡排序通过重复遍历要排序的列表，每次比较相邻的两个元素。如果顺序不正确，就交换它们的位置。这个过程会重复直到整个列表有序。

每一轮遍历会将一个最大的元素“冒泡”到末尾。

复杂度：时间复杂度：O(n²)

function populeSort(arr){
  let len = arr.length-1
  for(let i=0;i<len;i++){
    // 每一轮遍历都会将一个最大的元素“冒泡”到末尾，所以下一轮遍历就不用再遍历最后一个元素
    for(let j=0;j<len-1;j++){
      if(arr[j]>arr[j+1]) [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
    }
  }
  return arr
}

插入排序

插入排序将数组划分为已排序和未排序部分，从未排序部分取出元素，并将其插入到已排序部分的适当位置。这个过程会反复执行，直到所有元素都被插入到正确的位置。

复杂度：时间复杂度：O(n²) 最好情况（数组本身有序）：O(n)

function insertSort(arr){
  //有序无序两部分，从无序的数据中一次拿数据，插入到有序部分
  let len = arr.length
  // 第一个元素是有序部分，从第二个数据开始拿数据
  for(let i=1;i<len;i++){
    let curr = arr[i]
    let j=i-1
    //从有序数据的后面开始往前遍历，直到找到合适插入的位置
    while(j>=0 && curr<arr[j]){
      // 给将来要插入元素的地方腾位置
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = curr
  }
  return arr
}

归并排序

归并排序是另一种分治算法，它将数组递归地拆分为两个子数组，直到每个子数组只有一个元素。然后将这些子数组有序地合并，直到所有元素合并成一个有序数组。

归并排序是一种稳定排序，而且它的最坏情况复杂度和平均复杂度都是 O(n log n)。

function mergeSort(arr){
  //终止条件，就是arr长度
  if (arr.length<=1) return arr
  //首先将数组分为二部分
  let mid = Math.floor(arr.length/2)
  let leftArr = arr.slice(0,mid)
  let rightArr = arr.slice(mid)
  return merge(mergeSort(leftArr),mergeSort(rightArr))
}

function merge(left,right){
  let result =[]
  let i=0,j=0
  while(i<left.length && j<right.length){
    if (left[i]<right[j]){
      result.push(left[i])
      i++
    }
    else{
      result.push(right[j])
      j++
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j))
}

堆排序

堆排序利用了堆这种数据结构。堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。堆排序的核心思想是：首先将数组构造成一个最大堆，然后依次将堆顶元素（最大值）与最后一个元素交换，再将剩下的元素重新调整为堆，直到排序完成。

复杂度：时间复杂度：O(n log n)

二叉树系列

层序遍历

前序遍历

递归法

var preorderTraversal = function (root) {
  const res = []
  const preorder = (rt)=>{
    if (!rt) return
    res.push(rt.val)
    preorder(rt.left)
    preorder(rt.right)
  }
  preorder(root)
  return res
}

迭代法

var preorderTraversal = function (root) {
  let res = []
  if (!root) return res   // 应对空二叉树
  let queue = [root]
  while(queue.length){
    //每次从队列里去一个节点，把该节点的值添加到result，
    let cur = queue.pop()
    res.push(cur.val) //该节点的右孩子和左孩子依次加入节点，
    if (cur.right) queue.push(cur.right) //等到下一轮，就会分别依次遍历左孩子和有孩子了
    if (cur.left) queue.push(cur.left)
  }
return res
}

后序遍历

递归法

var postorderTraversal = function (root) {
  let res = []
  const postorder = (rt) => {
    if (!rt) return    //不要忘了这个条件
    postorder(rt.left)
    postorder(rt.right)
    res.push(rt.val)
  }
  postorder(root)
  return res
}

迭代法

中序遍历

递归法

var inorderTraversal = function (root) {
  let res =[]
  const inorder = (rt)=>{
    if (!rt) return
    rt.left && inorder(rt.left)
    res.push(rt.val)
    rt.right && inorder(rt.right)
  }
  inorder(root)
  return res
}

迭代法

var inorderTraversal = function (root) {
  // 入栈:左->右
  // 出栈:左 中 右
  let res = []
  const stack = []
  if (root) stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    if (!node) {
      res.push(stack.pop().val)
      continue
    }
    if (node.right) stack.push(node.right) // 右
    stack.push(node) // 中
    stack.push(null)
    if (node.left) stack.push(node.left) // 左
  }
  return res
}